Church Turing Thesis

From <http://plato.stanford.edu/entries/church-turing/>:

The Church-Turing thesis concerns the notion of an effective or mechanical method in logic and mathematics. 'Effective' and its synonym 'mechanical' are terms of art in these disciplines: they do not carry their everyday meaning. A method, or procedure, M, for achieving some desired result is called 'effective' or 'mechanical' just in case

M is set out in terms of a finite number of exact instructions (each instruction being expressed by means of a finite number of symbols);
M will, if carried out without error, produce the desired result in a finite number of steps;
M can (in practice or in principle) be carried out by a human being unaided by any machinery save paper and pencil;
M demands no insight or ingenuity on the part of the human being carrying it out.

A well-known example of an effective method is the truth table test for tautologousness. In practice, of course, this test is unworkable for formulae containing a large number of propositional variables, but in principle one could apply it successfully to any formula of the propositional calculus, given sufficient time, tenacity, paper, and pencils.

Statements that there is an effective method for achieving such-and-such a result are commonly expressed by saying that there is an effective method for obtaining the values of such-and-such a mathematical function. For example, that there is an effective method for determining whether or not any given formula of the propositional calculus is a tautology -- e.g. the truth table method -- is expressed in function-speak by saying that there is an effective method for obtaining the values of a function, call it T, whose domain is the set of formulae of the propositional calculus and whose value for any given formula x, written T(x), is 1 or 0 according to whether x is, or is not, a tautology.

The notion of an effective method is an informal one, and attempts to characterise effectiveness, such as the above, lack rigour, for the key requirement that the method demand no insight or ingenuity is left unexplicated. One of Turing's achievements in his paper of 1936 [OnComputableNumbers] was to present a formally exact predicate with which the informal predicate 'can be calculated by means of an effective method' may be replaced. Church did the same (1936a). The replacement predicates that Turing and Church proposed were, on the face of it, very different from one another, but they turned out to be equivalent, in the sense that each picks out the same set of mathematical functions. The Church-Turing thesis is the assertion that this set contains every function whose values can be obtained by a method satisfying the above conditions for effectiveness. (Clearly, if there were functions of which the informal predicate, but not the formal predicate, were true, then the latter would be less general than the former and so could not reasonably be employed to replace it.) When the thesis is expressed in terms of the formal concept proposed by Turing, it is appropriate to refer to the thesis also as 'Turing's thesis'; and mutatis mutandis in the case of Church.

Church-Turing Thesis, Standard Version: Suppose there is a method which a sentient being follows in order to sort numbers into two classes. Suppose further that this method always yields an answer within a finite amount of time, and that it always gives the same answer for a given number. Then: Some terminating FlooP program (i.e., some general recursive function) exists which gives exactly the same answers as the sentient being's method does.

This is from DouglasHofstadter's book "GoedelEscherBach".

To amplify a bit, the ChurchTuringThesis is so called because both AlanTuring and AlonzoChurch independently developed formalisms for defining what constitutes an algorithm. The formalisms are equivalent (which is what the Hofstadter quote is saying). AlanTuring used the TuringMachine and AlonzoChurch used the LambdaCalculus. This allows you to prove that certain problems cannot be solved algorithmically. MichaelSipser? in IntroductionToTheTheoryOfComputation? gives as an example a problem posed by DavidHilbert?, that of determining whether or not a polynomial has an integral root. It turns out that this problem is not TuringDecidable?, although it is TuringRecognizable?. So no algorithm exists which is guaranteed to answer the question in a finite number of steps.

[From ChurchTuringHypothesis?]

"All computable functions are computable by Turing machine."

"certain functions are uncomputable in an absolute sense: uncomputable even by [Turing machine], and, therefore, uncomputable by any past, present, or future real machine." [Boolos, G.S., Jeffrey, R.C. 1980. Computability and Logic. 2nd edition. Cambridge: Cambridge University Press]

They are slightly different in formulation, but equivalent in result:

Turing's says: Anything that is computable can be computed by a Turing machine. If P then Q.

Church's says: Anything that isn't computable on a Turing machine isn't computable at all. If not Q then not P.

Thus, all models of computation possible are equivalent in scope. Because they can only compute the computable.

-- KatieLucas

(31/07/02) A quick (again) formulation:

The Church-Turing thesis states an equivalency between two realms: the realm of recursive functions and the realm of computable ones. "Recursive function" is a mathematical notion belonging to full-blown maths, and "computable function" is more of a constructivistic one.

To say that all recursive functions are computable is a truism. To say that all computable functions are recursive is a big assumption. In fact, that's why it's called a thesis.

Please consider that I did not use the word existence: a Turing machine is VERY, VERY strong. It has no time, nor memory limitation.

Hope this will help,

Benoit St-Pierre (benoitstpierre@internet.uqam.ca)

The above formulation is wrong. A recursive function (See PartialRecursiveFunctions) is a mathematical notion that I believe is provably equivalent to the notion of a TuringMachine (which BTW, can be mathematically defined). Turing's thesis says that all ModelsOfComputation are no stronger than the computational power of a TuringMachine. It is a thesis because one can't check all ModelsOfComputation. All the notions of computability Turing checked satisfied this.

(1-08-2002) I do not see that much a difference between the two formulations. Except perhaps when yours do not take into consideration the case where the computational power of a TuringMachine could get us outside the realm of RecursiveFunctions? (in that case, the two sets are certainly not equivalent).

At least have the decency to show where I erred. And take into consideration Church's view on the subject. Not just Turing's, like Boolos did. And, please, no more BTW's implying that I seem to know nothing about maths.

Just in case you are enticed to pass another harsh judgement, maybe we could clear up all we said by restating the "Ancillary Thesis" with Quine's formidably simple wording: "All effective classes of numbers are recursive". (Selected Logic Papers, p. 213).

(3-08-2002.) Rethinking about it, now I do see a difference between the two formulations. While you stated the Chuch-Turing thesis when you said "A recursive function (...) is (I believe) provably equivalent to the notion of a TuringMachine", the thesis you mentioned is not the ChurchTuringHypothesis?. It is a theorem Turing proved in his doctoral dissertation : a TuringMachine is the strongest deterministic machine.

The problem is that this thesis does not entail anything about ModelsOfComputation.

Turing also introduced another kind of machine, the OMachine, which is not deterministic this is wrong, an oracle must be deterministic, but it can answer any question, even ones that are not computable by a TM., for its computation is based on an Oracle. Since the O-machine can solve the HaltingProblem, it cannot be reduced to a mere TuringMachine. If we consider it's still a machine crunching computable numbers, some of them aren't in the recursive set anymore.

All in all, the problem resides in the fact that computability isn't a clear-cut notion, while recursive is. For example, there could be a more than one notion of computability. If we talk about "black-box computability" (a term coined by Anthony Galton), where we have no notion what has been going on inside the computation, we should then include the OMachine. Couldn't youd have recursively defined functions that use functions that are not recursively definable? Wouldn't that be the equivalent notion?

Considering that, my first formulation could be misleading : I should have talked about effective functions, not computable ones. Effectivity is a more solid notion, even if it's not rock-solid as recursivity.

Sorry folks, this emperor wears no clothes. "The Turing Machine" is one of 3 classes of machine identified by Turing: the A (automatic) machine, the C (choice) machine, and the O (oracle) machine.

The A machine, according to Turing, has no interaction with the outside world at all. It has no GUI. It has no patch panel. It has no ports, no I/O, nothing at all that allows it to receive signals from the world except its pre-formatted and pre-coded tape. It is this machine, and only this machine that is afflicted by the GeneralHaltingProblem. And so the class of "computable numbers" is defined by what limits this machine.

Turing's C machine has I/O and alters its function according to signals from the world outside it. Turing proved nothing about the class of numbers that can be computed by his C-machine. Yet all our real-world computers are at least equivalent to the C machine, and not the A machine. We may therefore legitimately inquire WhatDoesHaltingMean, or at least what does it mean to us?

Turing's O machine is essentially a C-machine hooked up to an interferometer or geiger counter. It's intended to model computations that symbolically encode the results of physical processes. Since we are physical creatures ourselves, and the interactions between ourselves and the entire universe are extremely subtle and co-evolutionary, we may legimately say that all our computers are actually O-machines.

So we really shouldn't call Turing's A-machine numbers "the computable numbers". We should just call them "the a-machine numbers" and see whether we can come up with a new way to describe what's computable with C/O machines. -- PeterMerel

(29-07-2003)

I think there are a lot of emperor's in this discussion! Which one do you aim at?

The problem tackled by the thesis is not about naming, it is about finding out an equivalence class. Either you uphold the strong interpretation (Turing's), or the soft one (Church's) : but you do not justify the strong interpretation by an argument for the weak interpretation !

Saying A is equivalent to B for A can be reduced to B, without considering the reduction from B to A. The anonymous folk previously proposed that, and it is preposterous.

***

This definition of the C-machine fits well the definition of a NondeterministicTuringMachine?. I contend that a choice is just a fork between two alternative states. You can see the states of the machines as a tree partially ordered over "time". If you do not have the possibility of multiple next states after a given state, the machine does not have any choice.

Besides, all nondeterministic Turing machines can be reduced to deterministic ones. (For any language accepted by a non-deterministic Turing-Machine is accepted by a Turing machine. And every Turing-acceptable language is Turing-decidable iff the particular Turing-acceptable language in question is Turing-decidable. The converse is not true.)

This is just another consequence of Turing-machines' nicest property : being 'universal'. And it implies that a Turing Machine suffices to express all a computer can do, with or without "big" GUI. All the GUI's aspects (I/O and what not) of a machine revert to adding more tapes or more heads, or what not. And all those tapes or heads can be reduced to 'one' head, to 'one' tape.

In a strong sense, a Turing machine is quite stronger than our 'beige' stuff! So the C-machine is just a way to illustrate a realistic application of a Turing-machine.

***

As for the fanthom interlocutor : we could not 'recursively define functions that use functions that are not recursively definable'. Turing did not (in any computational sense) defined the 'Oracle' function : he stipulated it. This machine helped him to study non Turing-enumerable processes.

***

All this is all but my personal distorted interpretation of computation theory. So please feel free to correct me, but please back up your opinions! As far as I understand it, all this can be found in a good introductory book. I can suggest (Lewis and Papadimitriou, 1981). There is also a good paper by B. Jack Copeland about Turing O-machine, that one can find over the net.

Benoit St-Pierre