Skip to main content
2 of 4
added 17 characters in body
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

The answer is no, not necessarily.

For a counterexample, let $f(x,y)=0$, if $x$ is a Turing machine program that halts on $x$. Otherwise, $f(x,y)$ is not defined. This is computable, since on input $(x,y)$, I can run $\phi_x(x)$, and if it ever halts, then I output $0$; otherwise, keep running it.

Notice that every $f_x$ is either the constant $0$ function or the empty function, depending on whether $x$ halts on $x$. So there are only two functions that arise as $f_x$.

But if there were an $r$ with finite range such that $f(x,y)=\phi_{r(x)}(y)$, then some $\phi_{r(x)}$ are the constant $0$ function and some are the empty function.

With a finite look-up table, we can know which of those values are the constant zero function and which are the empty function. Thus, if there is such an $r$, we can solve the halting problem by inspecting $r(x)$. Contradiction.

Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k