Church-Turing Theses

18 04 2006

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.




7 responses

19 04 2006

An interesting read: the CT thesis from a philosopher’s perspective. As a computer scientist, I have a couple of nitpicks with your post.

Regarding CT thesis II, I don’t know if it’s *just* an empirical matter of verifying whether relativity or quantum physics can simulate non-Turing computations. Even with explicit physical systems like quantum computers, it is not trivial to figure out how powerful they are (and a quantum computer can be simulated by a Turing machine without changing any notions of computability.

You rightly argue that CT III (the “effective” CT thesis is what we often call it) is what people often believe, and is threatened by quantum computing. However, contrary to what you indicate, it is NOT the case that quantum computers can solve NP-hard problems, at least not yet.

as an aside, it’s not so much whether a quantum computer can solve an “NP” problem. Since P is contained in NP, this is always true. what is relevant is whether a quantum computer can solve an NP-complete problem in polynomial time, where an NP-complete problem is one that is in a formal sense the hardest problem in NP, and one that can be used to solve all problems in NP.

Finally, you are absolutely right that one can’t willy-nilly define any model of computation, since oracles are an easy way of subverting the effective CT thesis. However, the strength of this last thesis is that any physically realizable model we have been able to come up with (i.e all steps can be “implemented”) is polytime reducible to every other model. Quantum computing is fascinating precisely because it doesn’t seem to behave this way. But we have developed very sophisticated notions of time and space complexity to “stratify” these classes so to speak.

P, the class of poly-time solvable problems, is really the class that some believe captures effective computations. BPP, the class of efficient randomized algorithms, is probably a better choice, but one could nitpick ever so slightly about random sources, and I won’t get into that.

PSPACE, on the other hand, the class of poly-space computations, appears to be quite a bit more powerful. Again, we just don’t know how much more. So there is a good deal of stratification in complexity classes, but for effective computations, it really boils down to P (or BPP) vs NP.

19 04 2006
Kenny Easwaran

Thanks for the computational perspective on this!

You’re right that just because it’s an empirical question doesn’t make it easy.

Thanks for the clarification on quantum computation – I thought they already knew how to do NP-hard problems on a quantum computer, except that they just don’t have the physical machines working beyond four or five qubits or whatever.

Is BPP slightly larger than P, or slightly smaller? Because it seems that in some other sense of effective, P is too large. Though maybe there’s no principled way to cut it down.

PSPACE includes NP, right?

Anyway, thanks for your comment!

19 04 2006

BPP, as defined here,

is the class of all problems for which a randomized poly-time algorithm correctly identifies membership with a probability bounded away from 0.5 i.e usually 2/3 prob. of being correct, and a 1/3 prob. of being wrong.

Since the algorithm may choose not to use random coins, BPP contains P. The question P =? BPP, also unknown, can be paraphrased as “Does randomness help in computation”. Probably people if polled, will suspect that P = BPP, but we don’t know what the true situation is.

I am not sure what you mean when you say that P is “too large”. is it because it includes problems with running times of n^100, that are not efficient in practice ?

PSPACE includes NP, yes. The inclusion goes

P \subseteq NP \subseteq PSPACE. it is possible that P = PSPACE, just as it is possible that P = NP, although i suspect P = PSPACE is believed with a lot less certitude.

22 04 2006

It is also worth noting, as computer scientist Peter Wegner has been saying for years, that these notions of “computation” do not describe most of the actual computation we see around us. For example, they assume inputs to a computational process occur prior to the processing, which then occurs prior to any delivery of outputs; they assume inputs are batched, and do not arrive piecemeal; and likewise, for outputs; they assume processing happens in one machine, and is not distributed.

Nearly all of us, everyday, are using operating systems which violate these assumptions. Increasingly, with service-oriented computing, agent-oriented and P2P systems, we use applications which also violate these assumptions.

IMO, the interesting question is sociological rather than philosophical: Why do so many computer scientists still cling to a model of computation which is violated by their own everyday experience?

22 04 2006
Kenny Easwaran

That’s also quite a good point. However, can’t one model this as some sort of Turing computation from an oracle? That is, just treat getting an input from the user as a basic step.

But perhaps more importantly, the reason these notions are of any use is to say what sorts of functions can be computed with them (and how fast). The fact that we use computers to do all sorts of things other than computing functions just means that other abstract models will be useful for those purposes, not that these models are useless.

24 04 2006

these notions of “computation” do not describe most of the actual computation we see around us

I suspect that most of the time there is little distinction between these notions, that’s why no distinction is made. I expect that most questions about processes that start before their inputs have arrived can be rephrased in terms of conventional computing machines. However, this isn’t necessarily the case for all types of computation.

Processes that start before heir inputs are received typically involve multiple agents and such processes are usually known as ‘protocols’. And quantum protocols appear to be different from classical protocols because quantum encryption, an example of a quantum protocol, allows you to be provably “almost certain” that nobody could have eavesdropped on your message. When asking questions about ordinary computations we’re often asking “with these assumptions about our universe, does there exist an algorithm such that…”. Classical and quantum computing give essentially the same answers because a quantum computer can be simulated by a classical one. But with encryption protocols we’re asking questions like “does there exist an algorithm such that there is no algorithm such that…”. And here we see appear to see a big difference between classical and quantum computing.

28 04 2006

Kenny — I’m not saying that the limited models of computation studied by most theoretical computer scientists these last 50 years are useless. I’m saying that anyone who studies something they call “computation” ought to do so using a model (or models) which accurately represents the activities which computers do. Otherwise, they may as well be studying the metaphysics of angels on pinheads.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: