停机问题（3）- 证明溯源
There are two versions of the popular proof of the "haling problem": one based on the liar's paradox and the other based on the Cantor’s diagonisation.
The academic claims that the halting problem and its proofs are originated from Turing's 1936 paper, which is highly questionable, …
Roger Penrose gave an accessible presentation of the proof of the halting problem based on the Cantor’s diagonisation in The Emperor's New Mind, and I excerpt the relevant content as follows (p.59-64) :
A natural question arises: how are we to decide whether or not any particular Turing machine (when fed with some specific input) will ever stop? … So, is there some algorithmic procedure for answering the general question - the halting problem - completely automatically? Turing showed that indeed there is not.
His argument was essentially the following. We first suppose that, on the contrary, there is such an algorithm. Then there must be some Turing machine H which 'decides' whether or not the with Turing machine, when acting on the number m, eventually stops. Let us say that it outputs the tape numbered 0 if it does not stop and 1 if it does:
H(n;m) = 0 if Tn(m) = □; 1 if Tn(m) stops.
Now let us imagine an infinite array, which lists all the outputs of all possible Turing machines acting on all the possible different inputs. The nth row of the array displays the output of the nth Turing machine, as applied to the various inputs 0,1,2,3,4,… :
m → | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | … |
0 | □ | □ | □ | □ | □ | □ | □ | □ | □ | |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
3 | 0 | 2 | 0 | 2 | 0 | 2 | 0 | 2 | 0 | |
4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
5 | 0 | □ | 0 | □ | 0 | □ | 0 | □ | 0 | |
6 | 0 | □ | 1 | □ | 2 | □ | 3 | □ | 4 | |
7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
8 | □ | 1 | □ | □ | 1 | □ | □ | □ | 1 | |
… | ||||||||||
197 | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | |
… |
In the above table I have cheated a little, and not listed the Turing machines as they are actually numbered. … In fact I have simply made up the entries fairly randomly, just to give some kind of impression as to what its general appearance could be like.
I am not asking that we have actually calculated this array, say by some algorithm. (In fact, there is no such algorithm, as we shall see in a moment. ) We are just supposed to imagine that the true list has somehow been laid out before us, perhaps by God! It is the occurrence of the □s which would cause the difficulties if we were to attempt to calculate the array, for we might not know for sure when to place a □ in some position since those calculations simply run on forever!
However, we could provide a calculation procedure for generating the table if we were allowed to use our putative H, for H would tell us where the □s actually occur. But instead, let us use H to eliminate every □ by replacing each occurrence with 0. This is achieved by preceding the action of Tn on m by the calculation H(n; m); then we allow Tn to act on m only if H(n; m) = 1 (i.e. only if the calculation Tn(m) actually gives an answer), and simply write 0 if H(n; m) = 0 (i.e. if Tn(m) = □). We can write our new procedure (i.e. that obtained by preceding Tn(m) by the action of H(n; m) ) as
Tn (m) X H(n; m).
(Here I am using a common mathematical convention about the ordering of mathematical operations: the one on the right is to be performed first. Note that, symbolically, we have □ x 0 = 0. )
The table for this now reads:
m/n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | … |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
3 | 0 | 2 | 0 | 2 | 0 | 2 | 0 | 2 | 0 | |
4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
6 | 0 | 0 | 1 | 0 | 2 | 0 | 3 | 0 | 4 | |
7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
8 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | |
… |
Note that, assuming H exists, the rows of this table consist of computable sequences. (By a computable sequence I mean an infinite sequence whose successive values can be generated by an algorithm; i.e. there is some Turing machine which, when applied to the natural numbers m = 0, 1, 2, 3, 4, 5,. in turn, yields the successive members of the sequence. ) Now, we take note of two facts about this table. In the first place, every computable sequence of natural numbers must appear somewhere (perhaps many times over) amongst its rows. This property was already true of the original table with its Ds. We have simply added some rows to replace the 'dud' Turing machines (i. e. the ones which produce at least one □).
In the second place, the assumption having been made that the Turing machine H actually exists, the table has been computably generated (i. e. generated by some definite algorithm), namely by the procedure Tn(m) X H(n; m). That is to say, there is some Turing machine Q which, when acting on the pair of numbers (n, m) produces the appropriate entry in the table. For this, we may code n and m on Q's tape in the same way as for H, and we have
Q(n; m) = Tn(m) X H(n; m).
We now apply a variant of an ingenious and powerful device, the 'diagonal slash' of Georg Cantor. Consider the elements of the main diagonal, marked now with bold figures:
m → | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | … |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
3 | 0 | 2 | 0 | 2 | 0 | 2 | 0 | 2 | 0 | |
4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
6 | 0 | 0 | 1 | 0 | 2 | 0 | 3 | 0 | 4 | |
7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
8 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | |
… |
The elements provide some sequence 0,0,1,2,1,0,3,7,1,… to each of whose terms we now add 1:
1,1,2,3,2,1,4,8,2,…
This is clearly a computable procedure and, given that our table was computably generated, it provides us with some new computable sequence, in fact with the sequence 1 + Q(n; n), i. e.
1+Tn(n)xH(n;n)
(since the diagonal is given by making m equal to n). But our table contains every computable sequence, so our new sequence must be somewhere in the list. Yet this cannot be so! For our new sequence differs from the first row in the first entry, from the second row in the second entry, from the third row in the third entry, and so on. This is manifestly a contradiction. It is the contradiction which establishes what we have been trying to prove, namely that the Turing machine H does not in fact exist! There is no universal algorithm for deciding whether or not a Turing machine is going to stop.
Another way of phrasing this argument is to note that, on the assumption that H exists, there is some Turing machine number, say k, for the algorithm (diagonal process! ) 1 + Q(n; n), so we have
1+Tn(n)xH(n;n)=Tk(n).
But if we substitute n = k in this relation we get
1 + Tk(k) x H(k; k) = Tk(k).
This is a contradiction because if Tk(k) stops we get the impossible relation
1 + Tk(k) = Tk(k)
(since H(k; k) = 1), whereas if Tk(k) does not stop (so H(k; k) = 0) we have the equally inconsistent
1 + 0 = □.
The question of whether or not a particular Turing machine stops is a perfectly well-defined piece of mathematics (and we have already seen that, conversely, various significant mathematical questions can be phrased as the stopping of Turing machines). Thus, by showing that no algorithm exists for deciding the question of the stopping of Turing machines, Turing showed (as had Church, using his own rather different type of approach) that there can be no general algorithm for deciding mathematical questions. Hilbert's Entscheidungsproblem has no solution!
Reference :
[1] https://en.wikipedia.org/wiki/Roger_Penrose
[2] https://en.wikipedia.org/wiki/The_Emperor%27s_New_Mind
Commentaires
Enregistrer un commentaire