Resource bounded reductions for RE-Complete problems

Question

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.

Answer 1

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$.

Answer 2

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

Let M_e be an enumerator and let M be a machine that halts if and only if M_e 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.)