Return to Answer

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 necessarily do this. There is a computably 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.

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.

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.

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 necessarily do this. There is a computably 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.

The answer is no.

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.

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.