0
$\begingroup$

The halting problem can be stated by the decision problem "does the Turing machine $T_n$ without input halts?". It is undecidable, however the binary sequence of the solutions of the halting problem, where the $n$th digit is $1$ or $0$ whether the $n$th machine halts or not, is limit-computable.

Now consider the decision problem "does the Turing machine $T_n$ halts on every inputs?" and the binary sequence where the $n$th digit is $1$ or $0$ whether the $n$th machine halts on every inputs or not. Is this binary sequence limit-computable ?

$\endgroup$
0
$\begingroup$

No, it is not.

By Shoenfield's limit lemma, limit computability is the same as computability relative to the halting problem. But the set $Tot$ of Turing machines which halt on all inputs is strictly harder than the halting problem: it is in fact equivalent to the "halting problem's halting problem."

  • In symbols: the Turing degree of Tot is ${\bf 0''}$ while the Turing degree of the halting problem is (by definition) merely ${\bf 0'}$ (here "${\bf 0}$" is the degree of the computable sets, and "$\bf\cdot'$" is the Turing jump operator).

A proof of the fact that $deg(Tot)={\bf 0''}$ can be found e.g. in Soare's textbook.

| cite | improve this answer | |
$\endgroup$

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.