1

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

Dean Menezes
  • 673
  • 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. – DanielV Jun 12 '17 at 04:15

1 Answers1

0

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.

Dean Menezes
  • 673