On my way back from Austin, I visited my friend Bob McGrew in Palo Alto, and we caught up with each other a bit. At a certain point, when we were talking about our respective research, the subject of the Church-Turing Thesis came up (I don’t remember how, because it’s not really directly related to what either of us does, though not terribly far from either). In our discussion, we both clarified distinct versions of the CT Thesis that the other hadn’t realized.
The basic idea is that the CT thesis is an analysis of the pre-theoretic notion of computability – in this version the thesis approximately states: A problem is intuitively computable iff it can be solved by a Turing machine. However, it’s easy to forget that this is a conceptual analysis claim (especially if one isn’t a philosopher, and thus exposed to conceptual analyses all the time). There are only a few other equally widely accepted conceptual analyses – perhaps Tarski’s account of logical consequence (which has been disputed by John Etchemendy), and maybe one or two others. But in general, these are highly contentious claims, that are often disputed, the way Gettier disputed the justified true belief account of knowledge.
Because this particular analysis has been so successful, it’s easy for computer scientists to forget that it is one, and instead think the CT thesis is the following: A problem is physically computable iff it can be solved by a Turing machine. Now that we’re used to physical computers doing this sort of stuff all the time, it seems that this is what we’re talking about – but there was a notion of what an algorithm was, or an effective process, long before we had machines to carry them out. And people can still intuively recognize whether a sequence of instructions is algorithmic without trying to reduce it to a physically programmable algorithm. However, CS texts very often say something like, “the CT thesis is a statement that is not amenable to proof or verification, but is just a matter of faith”. This statement doesn’t accurately describe this second thesis though – after all, it’s a matter of empirical physical investigation whether relativity or quantum mechanics allow for any processes that are not Turing-computable. Perhaps more relevantly, it may also be an empirical matter whether a physical device with the full strength of a Turing machine can be created! After all, a Turing machine needs an unbounded tape, and actual computers have finite memory space – and every device that can only accept or reject finitely many strings is automatically computable on just about every sense of the word (including ones much weaker than Turing-computable, like finite-state-machine recognizable, and the like).
At any rate, one might want to make the three-way identity claim: The pre-theoretic notion of computability, Turing’s account of computability, and physical computability all coincide.
What Bob pointed out to me was that many computer scientists actually subscribe to a claim that’s much stronger than these ones. Rather than focusing on the general notion of what is computable, it deals with the speed of the computability. Roughly speaking, this thesis says: Every physically realistic model of computation is polynomially reducible to every other one. I believe that this thesis has lately been threatened by the feasibility of quantum computation – although it preserves the absolute notion of computability, quantum computation allows computations that could only be done in non-deterministic polynomial time (NP) to be done in deterministic polynomial time (P). I suppose if P=NP turns out to be true, then this doesn’t damage this thesis, but since most people believe that it’s false, this seems to be evidence against this thesis.
However, there is a slightly weaker version available, that is still much stronger than the earlier ones, saying: Every mathematical model of computation from a certain list is polynomially reducible to every other one. This seems to be true with register machines, Turing machines, and apparently lots of the other formalisms that have been developed, both in the 1930’s and later. Of course, the claim can’t be strengthened too much, because an oracle for Turing computability could solve all computable problem in constant time. We also need to specify an appropriate notion of time and/or space complexity for each notion of computing. But so far, the most natural-seeming notions have ended up having this feature. Which is really quite interesting when you think about it.