Comments on Computational hardness of the uniform halting problem
Parent
Computational hardness of the uniform halting problem
How hard is the decision-problem of a plain Turing Machine halting on all inputs? I'm not sure of the terminology, but by "hard" I mean its location on the arithmetical hierarchy.
It can be seen that a TM with a Halt-0 oracle (an oracle that can determine whether a plain TM halts) can co-decide this with the following pseudocode.
x=0
while True:
if not Halt0(TM0,x):
return false
If I got my arithmetical hierarchy right, this puts the upper limit at $\Pi_2$. And obviously, the lower limit must be at least $\Delta_2$. Now I'm struggling to narrow it further.
To prove the problem is not at $\Delta_2$, I can try assuming otherwise. However, I can't get the same kind of self-referential paradox as in the classic Halting problem proof because a TM without an oracle is different from a TM + Halt-0 oracle, so I'm stuck.
Post
According to Wikipedia, the set of (indices of) Turing machines that compute total functions, i.e. which halt on all inputs, is a $\Pi_2$ set. If we use the variation of the definition of arithmetical hierarchy which includes primitive recursive functions, then it is fairly straightforward^[If you are comfortable with encoding data into naturals.] if tedious to explicitly write (given a reasonable encoding of a reasonable representation of Turing machines) a primitive recursive function that returns the state of the Turing machine encoded by $e$ on input $n$ after $s$ steps. We get the $\Pi_2$ formula: $\forall n.\exists s.\mathsf{steps}(e, n, s)=\mathsf{HALT}$. It may require a $\Sigma_1$ formula to formulate $\mathsf{steps}(e, n, s)=\mathsf{HALT}$ without primitive recursive functions, but that is not an issue for us because $\exists s.\mathsf{steps}(e, n, s)=\mathsf{HALT}$ would still be a $\Sigma_1$ formula.
Using Post's Theorem, if we could show that the above set is not recursively enumerable given an oracle that can answer whether a plain Turing machine halts, then we'd know that the formula wasn't $\Sigma_2$ and thus not $\Delta_2$. At this point, we're back to where you are.
A well-known result is that the set of total computable functions is $\Pi_2$-complete (e.g. Theorem 3.2 of Chapter IV of "Recursively Enumerable Sets and Degrees" by Robert Soare). So if this set was $\Delta_2$, we'd have $\Pi_2 = \Delta_2$. The proof from there is roughly as follows.
Given any $\Pi_2$ set, $A$, we have, by definition, $x\in A \iff \forall y.\exists z.R(x,y,z)$ for some recursive relation $R$. We can define a one-to-one recursive function $f$ such that $f(x)$ is a(n index of a plain) Turing machine which halts on input $u$ if and only if $\forall y < u.\exists z.R(x,y,z)$ holds. If $x\in A$, then this resulting Turing machine $f(x)$ implements a total function, i.e. $f(x)$ halts on all (infinitely many) inputs. If $x \notin A$, then $f(x)$ halts on finitely many inputs. Therefore, $x \in A$ if and only if $f(x)$ is total. $\square$
0 comment threads