5.7 Church's Thesis
In the previous sections of this chapter we have obtained two, no doubt remarkable, results. Namely, we have established that
| the class of Diophantine sets | |
| is identical to | (5.7.1) |
| the class of Turing semidecidable sets |
| Hilbert's Tenth Problem is Turing undecidable. | (5.7.2) |
However, these two rather technical results raise a number of new questions. While the definition of Diophantine set is quite natural, that of Turing semidecidable set is burdened by numerous technical details, many of which seem arbitrary. For example, we could use binary rather than unary notation to represent numbers. The tape could be infinite in both directions instead of in only one direction. Instead of a single head, there might be several, each executing its own set of instructions while sharing information about their respective scanned cells. Moreover, there might be several tapes. In fact, the memory need not even be linear; it could, for example, take the form of a plane divided into square cells. For each such modification of the notion of Turing machine, one can introduce a corresponding concept of semidecidability and pose the question of how that concept is related to Diophantine sets.
The reformulation of Hilbert's Tenth Problem used in Section 5.6 could be criticized as well, since it is based on a very special method for coding Diophantine equations. It would be more natural to write on the tape the number of unknowns, the degree, and the coefficients of an equation in unary or some positional notation. Hilbert did not impose any restrictions on the desired method for solving the Tenth Problem. Thus, if for some appropriate notation for polynomials, someone had succeeded in constructing a decision machine, that would certainly have provided a positive solution of Hilbert's Tenth Problem. So to what extent can the Turing undecidability established in Section 5.6 be considered as constituting a negative solution?
For every modification of the notion of Turing machine (or any other abstract computing device) and for every method of representing initial data on the tape, one could try to obtain results like (5.7.1) and (5.7.2). This could be done directly or indirectly. For the former, we would need to introduce suitable codings and to prove that the corresponding relations are Diophantine. For the latter, we can forget about Diophantine equations for the time being and prove that the class of semidecidable sets remains the same in spite of modifications in the definition (see, e.g., Exercises 5.6 and 5.7a). Such studies of relations between (semi)decidability on different abstract computing devices were in fact carried out quite apart from work on Hilbert's Tenth Problem, and long before its undecidability was established in any sense. These studies showed that the notions of semidecidable set and decidable set, which we introduced using Turing machines, are quite insensitive to the choice of a particular computing device and method of representing initial data. The very same classes arose for any "reasonable" choice. By "reasonable" we mean that the elementary steps of a computation should in fact be elementary, i.e., easily performable (for example, one cannot recognize in a single step whether a particular Diophantine equation has a solution).
Long before the appearance of the first mathematically rigorous notions of abstract computing devices such as Turing machines, there was the intuitive notion of an algorithm as a guaranteed method for the mechanical solution of problems of a definite kind. As a classical example, we can mention Euclid's algorithm for finding the greatest common divisor of two positive integers. Whenever an algorithm was proposed, it was clear that in fact it was a universal method for solving problems of the appropriate kind. However, such intuitive notions do not suffice for a proof that there is no algorithm for problems of the kind being considered.
The initial data for an algorithm (in the intuitive sense) are selected from some countable set, and, essentially without loss of generality, we are only going to consider situations in which the initial data consist of natural numbers or tuples of natural numbers of some fixed length. (The techniques of Chapter 4 indicate how one could code more complicated structures.)
The result of carrying out an algorithm is also an object of the appropriate kind. We could have chosen to consider only algorithms whose outputs are natural numbers, but it is more in the spirit of the subject of this book to consider instead algorithms with the two outputs "YES" and "NO". Correspondingly, along with the intuitive concept of algorithm, two related concepts arise, namely, the intuitive concepts of decidable and semidecidable set. A set M of n-tuples is decidable (in the intuitive sense) if there exists an algorithm (also in the intuitive sense) that halts on every n-tuple of natural numbers and reports "YES" or "NO" depending on whether the n-tuple belongs to the set or not. Similarly, for M to be semidecidable we would need an algorithm that would report "YES" for every n-tuple in M and that would either report "NO" or fail to halt if the tuple doesn't belong to M. Computability theory in its entirety could be expounded in terms of decidable and semidecidable sets, just as we can eliminate the notion of functions from mathematics and deal only with their graphs.
Between intuitive decidability and semidecidability there is the same relation as between Turing decidability and semidecidability: a set is decidable if and only if both it and its complement are semidecidable.
How is formal Turing (semi)decidability related to (semi)decidability in the intuitive sense? One relation is evident: Turing (semi)decidable sets are recognized by most mathematicians as (semi)decidable in the intuitive sense. The converse is known as
Church's Thesis: Every set of n-tuples that is (semi)decidable in the intuitive sense is also Turing (semi)decidable.
Here we have encountered something rarely found in mathematics, a thesis. What is it? It is not a theorem because it has no proof. It is not a conjecture because it cannot have a proof. It is not even an axiom that we are free to accept or reject. All of this is due to the fact that Church's Thesis is not a precise mathematical statement, because it relates the rigorous notion of Turing (semi)decidability with the non-rigorous notion of (semi)decidability in the intuitive sense.
What are the arguments in favor of Church's Thesis? They may be very different in appearance but all of them are essentially the same: so far no one has found an example of a set that would be recognized by most mathematicians as (semi)decidable in the intuitive sense and for which we cannot construct an appropriate Turing machine. Of course, this assertion should not be understood literally, i.e., as though for every set recognized to be (semi)decidable someone had actually constructed a corresponding machine. In fact, there are numerous tools for indirectly proving the existence of such a machine.
What is Church's Thesis for? On the one hand, it can serve as a guiding star: as soon as we have established (semi)decidability in the intuitive sense, our chance of finding the corresponding Turing machine should be considered very high. In fact, professional mathematicians usually content themselves with establishing intuitive (semi)decidability and do not condescend to formal proofs.
On the other hand, Church's Thesis plays a role in mathematics similar to that played elsewhere by the law of conservation of energy. Namely, as long as no exception to the law is found, it is unreasonable to set out to construct a perpetual motion machine. Similarly, once the Turing undecidability of a set has been proved, one need not spend one's time seeking a universal method for recognizing the elements of that set. In particular, according to Church's Thesis, the quite special result (5.7.2) gives us the moral right to cease the hunt (so far carried out in vain) for a "process" of the sort Hilbert asked for in his Tenth Problem.
In Chapter 7 we shall discuss the question of whether (5.7.2) constitutes a complete solution of Hilbert's Tenth Problem from another point of view.
The English translation of Chapter 5 from the book is placed on WWW with kind permition of The MIT Press.