# Is there a Turing machine that limit-compute if some other TM halts on all inputs?

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 ?

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.