# Shewing that a problem reduces to the halting problem

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

• 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 4:15

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.