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.
user53100
·
2020-09-18T17:12:41Z (over 3 years ago)