Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have read that there is some debate over the exact origin of the Halting argument, which begins with Kleene and Davis in the 1950s [Copeland 2004]. Motivated by this I want to clarify the Degree of the problem actually proved unsolvable by Turing [1936]. Of course the Halting problem is ${\Delta^0_2}$, but it is based on Post's (1947) model rather than Turing's (1936) model with its circular and circle-free machines.

My own quick analysis of this is that we would translate as follows:

M circle-free = $\{m| \phi(m) converges\}$ is infinite

This represents the fact that a Turing a-machine M will converge in infinitely many F- squares producing a computable real (say). $\phi$ is the corresponding (partial) recursive function computed by a-machine M. The D.N of M Turing called Satisfactory.

M circular = $\{m| \phi(m) converges\}$ is finite

This machine converges only finitely often. The difference between "circular" and the "terminating" of the Halting proof, is that a circular machine might not actually stop, since computation will continue (on the E-squares). The basic example of this is within Turing's proof itself wherein a candidate machine prints N-1 values then loops in its attempt to print any more: hence the term "circular".

So Turing's Proof 1 (which we could call the Satisfactoriness problem) is to show that no Turing a-machine D can decide D(M) = 1 if M is satisfactory; D(M)=0 if M is circular.

My calculation is that this satisfactoriness problem for D is at Level $\Delta^0_3$.

Has anyone else done this calculation?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.