Given that the halting problem is RE-Complete, we can reduce any problem in RE to an instance of the halting problem. Are there are any results on the time-bounds for this reduction? Can we do this reduction in polynomial time in general? Exponential time? Polynomial space?

On the surface, defining an oracle machine like $P^{H}$, where $H$ is a black-box that solves the halting problem in $O(1)$ time seems to provide a tremendous amount of power over $P$ alone. However, if the reduction from a problem in $P$ (primes, 2-SAT, etc) to the halting problem takes exponential time (or worse!) then $P^{H}$ isn't that much more powerful than $P$ in terms of what it can solve quickly.

  • $\begingroup$ "we can reduce any problem in RE to an instance" -- careful. We reduce problems to problems, which sometimes entails mapping instances to instances (for many-one reductions). Don't mix things up. $\endgroup$ – Raphael Jun 20 '16 at 7:59

The reduction from $M$ to $HALT$ is essentially the function $x \mapsto \langle x, M\rangle$. This function can be computed very easily in linear time.

$P^{HALT} = Exp^{HALT} = Rec^{HALT}$. The computation you want to perform inside your reduction can be delegated to $HALT$ as part of $M$ in the reduction, i.e. just include the code for wherever you want to do inside your reduction and passed it on to $HALT$ and $HALT$ will execute that for you.

Let's say your reduction from $M$ to $HALT$ is $N$. We can define a new reduction as $x \mapsto \langle x, HALT \circ N \rangle$ from $M$ to $HALT$. The new reduction only attaches a fixed string (the code of $HALT \circ N$) to its input $x$ and computable easily in linear time.

The possibility of delegating work in reduction to $HALT$ is the reason that the reduction class doesn't matter (as long as your class of reductions are computable functions and powerful enough to attach strings) and we end up with the same class of functions when attach a $HALT$ oracle whether the class of reductions is $P$ or $Exp$.


When inputs for the halting problem are encoded as ​ prefixfree(Turing_machine) || TM's_input , ​ even DFAs can do that reduction:

Let Me be an enumerator and let M be a machine that halts if and only if Me outputs M's input. ​ Now, regardless of what prefix-free code prefixfree is, "output prefixfree(M) followed by the reduction's input" describes a DFA reducing to the halting problem.

(If there's no prefix-free code for which that's an acceptable encoding of halting problem instances, then you'll need to be more specific.)

  • $\begingroup$ The formatting of your first sentence seems to have been mangled. $\endgroup$ – David Richerby Jun 20 '16 at 9:50

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.