A question on s-m-n Theorem

Question

Let $\phi$ be an acceptable programming system. If $f(x,y)$ is a $2$-ary partial recursive function, by the s-m-n Theorem there exists a $1$-ary recursive function $r$ such that, for all $x$ and $y$, $\phi_{r(x)}(y)=f(x,y)$. Now, suppose that the sequence $f_0,f_1,f_2,\ldots$ (where $f_x=\lambda y\centerdot f(x,y)$) includes only finitely many distinct partial recursive functions. Is there a recursive $r$ such that $(\forall x)(\forall y)(\phi_{r(x)}(y)=f(x,y))$ and the range of $r$ is finite?

Answer 1

This is an interesting question! You are asking that if $f(x,y)$ is computable in $x$ and $y$, but there are only finitely many possibilities for the curried function $f_x$, is there a finite list of programs for these unary functions such that we can computably pass from $x$ to a program for $f_x$ taken from that finite set.

The answer, unfortunately, is no, we cannot always do this. There is a computable function $f$ for which one cannot computably find the program for $f_x$ from a finite list of programs.

Consider the following counterexample. Let $f(x,y)=0$, if $x$ is a program that halts on input $x$, and otherwise, $f(x,y)$ is not defined. This is computable, because on input $(x,y)$, we can simpy try to compute $\phi_x(x)$, or in other words, run program $x$ on input $x$; if it halts, then we output $0$, and otherwise, we keep trying.

The thing to notice is 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$.

Suppose toward contradiction that there were a computable function $r$ with finite range such that $f(x,y)=\phi_{r(x)}(y)$, which means that $r(x)$ is a program for computing $f_x$. Thus, $\phi_{r(x)}$ is the constant zero function if $\phi_x(x)$ converges and otherwise $\phi_{r(x)}$ is the empty function.

If the range of $r$ is a finite set, then we may create a program with a finite look-up table for those values that tells us truthfully whether they are the constant zero function or the empty function. Now, given input $x$, the function $r(x)$ will give us one of those values, and we may consult the look-up table to discover whether $\phi_{r(x)}$ is the constant zero function or the empty function. By the design of $f$, however, the answer to this question is the same as the answer to whether $\phi_x(x)$ halts. Thus, we have computably solved the halting problem.

Since this is impossible, there can be no such program $r$, and so $f$ is a counterexample to your requested property.