I was reading Turing's paper "On computable numbers, with an application to the Entscheidungsproblem" and while reading $\S\ 8$ (his proof that computable numbers are enumerable) and his proof that the diagonal process cant be used for computable numbers, because $\beta$ (a binary number which prints in its $n$-th position one minus the $n$-th digit of circle-free Turing machine $n$ which he calls $\phi_n(n)$, and so $\beta$ is defined as $\phi_k(n) = 1 - \phi_n(n)$ ) or even $\beta$' (just a machine $k$ such that $\phi_k(n) = \phi_n(n)$ ) cant be computed, based on the fact that $\mathfrak{D}$ (a Turing machine which can tell if another machine is "circle-free" and prints a "$s$" if yes and "$u$" if not) isnt possible (because then $\mathfrak{H}$ would be possible by combining $\mathfrak{U}$ and $\mathfrak{D}$, and $\mathfrak{H}$ is a paradox), and i thought of a machine to which this paradox may not apply (at least not enough to disprove the diagonal argument).

Assume a machine $\mathfrak{D^+}$, which prints "$s$" for satisfactory ("circle-free") machine, "$u$" for unsatisfactory ("circular") machines, and "$p$" (paradox) for machines that are generally circle-free, besides for their own S.D. numbers (standard description number - a number which identifies and describes any Turing machine) and the S.D. numbers of all their variants i.e. different S.D. numbers which compute the same number as themselves (which would be a paradox - as described in his paper).

Then we can construct a machine $\mathfrak{H^+}$ which comprised of $\mathfrak{U}$ (Turing's universal machine) and above-described $\mathfrak{D^+}$. This $\mathfrak{H^+}$ would print $\phi_n (R(n))$ for all machines that are "$s$" (to exclude machines designated as "$u$" and "$p$"). Would we then be able to prove by means of the diagonal argument defined by Turing ( $\phi_K (n) = 1 - \phi_n (n)$ and then showing that: $1 = 2 \phi_K (K)$ ) that the computable numbers are not enumerable? basically, how am i wrong?

  • 4
    $\begingroup$ I recommend you define some of your terms. E.g. what is $\beta$? What does "S.D." stand for? $\endgroup$ – Quinn Culver Dec 8 '14 at 13:28
  • 2
    $\begingroup$ Your machine $D^+$ can't exist. $\endgroup$ – Steven Stadnicki Dec 9 '14 at 18:28
  • $\begingroup$ @StevenStadnicki and why not? if a proof is required to prove $\mathfrak{D}$ wont work. dont you need a proof to establish that for $\mathfrak{D^+}$? $\endgroup$ – Math chiller Dec 9 '14 at 23:48
  • $\begingroup$ @QuinnCulver is this better? $\endgroup$ – Math chiller Jan 5 '15 at 9:20

Your $D^+$ machine can't exist. You could still fool it, just like you could fool $D$. Let $U$ be a program that halts if its input is not its own S.D. number. (This can be done using the same techniques that are used for creating Quines). Else, it runs $D^+$. Then if $D^+$ outputs "$s$", it loops, and if $D^+$ outputs "$p$", it halts. We have a contradiction, since if $D^+(U)$ outputs "$s$" then $U$ is circular for at least one input, and if outputs "$p$" then $U$ halts for all inputs.

What you may be interested in is the concept of an "Oracle" machine. That is, a machine that has an extra input tape, an oracle tape containing any information you want to give it. You can consider oracle machines that simply "know" the answer to the halting problem for all Turing machines. Of course, no oracle machine solves the halting problem for all oracle machines - for that you would need another oracle, and so on ad infinitum. For detailed discussion on oracle machines, you might want to look up Turing degrees.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.