# could a machine $\mathfrak{D^+}$ be made to produce $\beta$ so the diagonal argument could be used on computable numbers?

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?

• I recommend you define some of your terms. E.g. what is $\beta$? What does "S.D." stand for? – Quinn Culver Dec 8 '14 at 13:28
• Your machine $D^+$ can't exist. – Steven Stadnicki Dec 9 '14 at 18:28
• @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^+}$? – Math chiller Dec 9 '14 at 23:48
• @QuinnCulver is this better? – 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.