Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Q&A

Computational hardness of the uniform halting problem

+6
−0

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.

History
Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

0 comment threads

1 answer

+3
−0

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$

History
Why does this post require moderator attention?
You might want to add some details to your flag.

1 comment thread

General comments (1 comment)

Sign up to answer this question »