Return to Question

...

The machine $\mathcal{H}$ has its motion divided into sections. In the first $N - 1$ sections, among other things, the integers $1, 2, \ldots, N - 1$ have been written down and tested by the machine $\mathcal{D}$. A certain number, say $R\left(N - 1\right)$, of them have been found to be the D.N's of circle-free machines. In the $N$-th section the machine $\mathcal{D}$ tests the number $N$. If $N$ is satisfactory, i.e., if it is the D.N of a circle-free machine, then $R\left(N\right) = 1 + R\left(N - 1\right)$ and the first. $R\left(N\right)$ figures of the sequence of which a D.N is $N$ are calculated. The $R\left(N\right)$-th figure of this sequence is written down as one of the figures of the sequence $\beta'$ computed by $\mathcal{H}$. If $N$ is not satisfactory, then $R\left(N\right) = R\left(N - 1\right)$ and the machine goes on to the $\left(N + 1\right)$-th section of its motion.

From the construction of $\mathcal{H}$ we can see that $\mathcal{H}$ is circle-free. Each section of the motion of $\mathcal{H}$ comes to an end after a finite number of steps. For, by our assumption about $\mathcal{D}$, the decision as to whether $N$ is satisfactory is reached in a finite number of steps. If $N$ is not satisfactory, then the $N$-th section is finished. If $N$ is satisfactory, this means that the machine $\mathcal{M}\left(N\right)$ whose D.N is $N$ is circle-free, and therefore its $R\left(N\right)$-th figure can be calculated in a finite number of steps. When this figure has been calculated and written down as the $R\left(N\right)$-th figure of $\beta'$, the $N$-th section is finished. Hence $\mathcal{H}$ is circle-free.

...

At this point, Turing has explicitly stated that $\mathcal{H}$ is "circle-free" and can be, and in fact is, constructed using a finite number of steps.

...

Now let $K$ be the D.N of $\mathcal{H}$. What does $\mathcal{H}$ do in the $K$-th section of its motion? It must test whether $K$ is satisfactory, giving a verdict "$s$" or "$u$". Since $K$ is the D.N of $\mathcal{H}$ and since $\mathcal{H}$ is circle-free, the verdict cannot be "$u$". On the other hand the verdict cannot be "$s$". For if it were, then in the $K$-th section of its motion $\mathcal{H}$ would be bound to compute the first $R\left(K - 1\right) + 1 = R\left(K\right)$ figures of the sequence computed by the machine with $K$ as its D.N and to write down the $R\left(K\right)$-th as a figure of the sequence computed by $\mathcal{H}$. The computation of the first $R\left(K\right) - 1$ figures would be carried out all right, but the instructions for calculating the $R\left(K\right)$-th would amount to "calculate the first $R\left(K\right)$ figures computed by $\mathcal{H}$ and write down the $R\left(K\right)$-th". This $R\left(K\right)$-th figure would never be found. I.e., $\mathcal{H}$ is circular, contrary both to what we have found in the last paragraph and to the verdict "$s$". Thus both verdicts are impossible and we conclude that there can be no machine $\mathcal{D}$.

...

And here is part of the problem- after Turing has just finished showing that $\mathcal{H}$ must be circle-free, and we are only constructing a machine made up of circle-free machines, the proof then immediately states that $\mathcal{H}$ can not be circle-free, even though we've shown that the machine we have constructed must be circle-free by definition.

The fact of the matter is this- the alleged issue that is being used to assert that the halting problem is undecidable has already been resolved by this point. If it were truly a problem that would cause the Turing Machine to be "circular" it never would have been written out as a circle-free machine. At this point we are executing the circle-free machines, so the alleged problem being discussed has already been filtered out along with all the other "circular" machines by halt(). The fallacy here is "denying the antecedent".

edit

@Kaveh stated Note that undecidability of H is usually stated negatively. To be clear, from Turings On computable numbers, with an application to the Entscheidungsproblem paper that established the proof:

It may be thought that arguments which prove that the real numbers are not enumerable would also prove that the computable numbers and sequences cannot be enumerable. It might, for instance, be thought that the limit of a sequence of computable numbers must be computable. This is clearly only true if the sequence of computable numbers is defined by some rule.

Or we might apply the diagonal process. "If the computable sequences are enumerable, let $a_n$ be the $n$-th computable sequence, and let $\phi_n\left(m\right)$ be the $m$-th figure in $a_n$. Let $\beta$ be the sequence with $1 - \phi_n\left(n\right)$ as its $n$-th figure. Since $\beta$ is computable, there exists a number $K$ such that $1 - \phi_n\left(n\right) = \phi_K\left(n\right)$ all $n$. Putting $n = K$, we have $1 = 2\phi_K\left(K\right)$, i.e. $1$ is even. This is impossible. The computable sequences are therefore not enumerable".

The fallacy in this argument lies in the assumption that $\beta$ is computable. It would be true if we could enumerate the computable sequences by finite means, but the problem of enumerating computable sequences is equivalent to the problem of finding out whether a given number is the D.N of a circle-free machine, and we have no general process for doing this in a finite number of steps. In fact, by applying the diagonal process argument correctly, we can show that there cannot be any such general process.

The simplest and most direct proof of this is by showing that, if this general process exists, then there is a machine which computes $\beta$. This proof, although perfectly sound, has the disadvantage that it may leave the reader with a feeling that "there must be something wrong". The proof which I shall give has not this disadvantage, and gives a certain insight into the significance of the idea "circle-free". It depends not on constructing $\beta$, but on constructing $\beta'$, whose $n$-th figure is $\phi_n\left(n\right)$.

Let us suppose that there is such a process; that is to say, that we can invent a machine $\mathcal{D}$ which, when supplied with the S.D of any computing machine $\mathcal{M}$ will test this S.D and if $\mathcal{M}$ is circular will mark the S.D with the symbol "$u$" and if it is circle-free will mark it with "$s$". By combining the machines $\mathcal{D}$ and $\mathcal{U}$ we could construct a machine $\mathcal{M}$ to compute the sequence $\beta'$. The machine $\mathcal{D}$ may require a tape. We may suppose that it uses the $E$-squares beyond all symbols on $F$-squares, and that when it has reached its verdict all the rough work done by $\mathcal{D}$ is erased.

...

It is clear the original proof "assumes that there is a function halt() that can decide whether or not a given Turing Machine halts or not."