A multivariate function, computable for any fixed first argument, is computable

Question

Claim: If $f:\mathbb N^{k+1}\to\mathbb N$ is a function such that for all $x_0\in\mathbb N$, $\lambda x_1,\dots,x_k.f(x_0,x_1,\dots x_k)$ is a partial recursive function then $f$ is also partial recursive.

Corollary: In particular, let $\mu$ be the minimization operator, and for all natural numbers $n$ let $\{f_i^{(n)}\}$ be a Gödel enumeration of the partial recursive functions of $n$ variables. Then the function $\mu_k:\mathbb N^{k+1}\to\mathbb N$ defined by $\mu_k(x_0,x_1,\dots,x_k)=\mu(f_{x_0}^{(k+1)})(x_1,\dots,x_k)$ is computable. Therefore, via the $S^m_n$ theorem, the minimization operator is effective, (as indicated in this CS.SE post).

Question: For all $i\in\mathbb N$, $\mu_k(i,x_1,\dots,x_k)=F(h(i),x_1,\dots,x_k)$, where $F$ is the universal function, and $h$ is a unique total function. Why is $h$ computable?

EDIT: Please note that I am working with a non-deciding minimization defined as follows: $$\mu(f)(\overline x)=\mu y[f(y,\overline x)=0]=y\iff (f(y,\overline x)=0\land(\forall i<y) (f(i,\overline x)>0))$$

Answer 1

After clarification, I think that the question asks how to prove that there is a computable function $h$ such that, for every partial computable function $f_e(q, i_1, \ldots, i_k)$, we have $$ f_{h(e)}(i_1, \ldots, i_k) = (\mu m)[(\forall q < m)[f_e(q, i_1, \ldots, i_k) \mathord{\downarrow} \land f_e(q, i_1, \ldots, i_k) > 0] \land f_e(m, i_1, \ldots, i_k) = 0] $$ Note that the function on the right is not the same as $(\mu m) f_e(m, i_1, \ldots, i_k) = 0$, which is a noncomputable function for some particular values of $e$. I will call the desired function $M(e)$.

The goal of the question is to show that $h$ is computable. The standard way to prove this is to convince oneself that there is a computable translator $T$ that, given the program (i.e. index) $e$ in some standard model of computation (e.g. Turing machines), produces a program (in the model) to compute $M(e)$. This is a routine exercise in programming.

Once we know that this can be done for any particular standard model of computation, we then know that it can be done for any admissible indexing of the partial computable functions, using the definition of admissibility. In particular, let $\eta$ be our admissible numbering with associated functions $f$ and $g$ as in the Wikipedia article. Let $T$ be the computable function that, given an index $e$ in the standard model, produces an index for $M(e)$ in the standard model of computation. Then $h(e) = g(T(f(e))$ and this will solve the problem for the numbering $\eta$.

Answer 2

It is not clear to me what the current question is asking, because it has several false claims. This comment is too long for the "comments" section, so I have made it a community-wiki post.

1) The initial "Claim" is false. Let $K$ be a noncomputable set and let $f(n,i) = 1_K(n)$. Then for each $n$ the function $(\lambda i)f(n,i)$ is computable, but the overall function $f$ is not computable.

2) Here is why minimization applied to partial functions can be noncomputable. Suppose that $A$ is a noncomputable r.e. set. Define a function $f(i,n)$ as follows:

$$ f(0,n) = 0 \quad \text{if $n \in A$}\\ f(0,n) = \,\,\uparrow \text{if $n \not\in A$}\\ f(i+1, n) = 0 $$

This function is partial computable if $A$ is r.e. What if we apply minimization to this partial function? We obtain a function $$ g(n) = (\mu i)[f(i,n) = 0] $$

Note that $g$ is a total function. Moreover, for all $n$, we have $g(n) = 0$ if and only if $n \in A$. So, if $g$ was computable, $A$ would be decidable, which contradicts the choice of $A$ as a noncomputable r.e. set. So the moral is that the partial computable functions are not closed under the $\mu$ operator, but they are closed under applying the $\mu$ operator to total computable functions. (It turns out that this is essentially exercise 4.24 in Soare's standard computability text.)

In particular, the operator $\mu_k$ in the question is not computable, and claim otherwise in the "corollary" is not correct.

Answer 3

Before all I want to thank Carl Mummert for his answer. Here is another solution I found.

Let $F^n$ be the set of partial functions of $n$ natural variables. Consider without proof that an operator $\Gamma:F^{n_1}\times\dots\times F^{n_k}\to F^m$ is effective exactly when the function $G$ defined bellow is computable.

$$G(a_1,\dots a_k,x_1,\dots,x_m)=\Gamma(f_{a_1},\dots,f_{a_k})(x_1,\dots,x_k)$$

Now if $M:=\lambda a,x_1,\dots,x_k.\mu(f_a^{(k+1)})(x_1,\dots,x_k)$ is computable then $\mu$ is effective. Indeed from the definition of $\mu$ we have:

$$M(a,\overline x)=\mu(f_a^{(k+1)})(x_1,\dots,x_k)=\mu y[f^{(k+1)}_a(y,\overline x)=(\Phi_{k+1}(a,y,\overline x)=0]$$

Since the universal function for the computable functions of $k+1$ arguments $\Phi_{k+1}$ is computable, $M$ is computable, because minimization preserves computability. q.e.d.