1
$\begingroup$

Let $\phi_e$ be an enumeration of the partial recursive functions.

A total function $f : \omega \to \omega$ is large if $f(e) > \phi_e(0)$ whenever $\phi_e(0)$ is defined.

If $f$ is large then given an oracle for $f$ it is possible to solve the Halting problem; i.e. we can decide membership in if X = {$e$ : $\phi_e(e)$ is defined }.

$\endgroup$
1
  • $\begingroup$ It sounds like you want to reduce the halting problem to your given problem, not the other way around. It is usually trivial to reduce a problem to the halting problem. $\endgroup$ – DanielV Jun 12 '17 at 4:15
0
$\begingroup$

We have that there is a computable function $\psi(e)$ such that $\phi_\psi(e)(0) =$ the number of steps it takes $\phi_e(e)$ to halt if \phi_e(e) is halts.

We can then solve the halting problem by running $\phi_e(e)$ for $f(\psi(e))$ steps.

$\endgroup$

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.