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))$$

  • $\begingroup$ I am only applying the $\mu$ operator to very special relations, namely the computable functions. This class of functions by its definition is closed under minimization, therefore, if I apply the $\mu$ operator to any partial recursive function, I still get a partial recursive function. $\endgroup$ – superAnnoyingUser Feb 12 '14 at 16:30
  • $\begingroup$ I am only trying to see that the $\mu$ operator is effective, Mr. @Mummert. The person who answered my question insists that the function $\mu_k$ is computable by definition. Would you argue that it is a computable function? $\endgroup$ – superAnnoyingUser Feb 12 '14 at 16:31
  • $\begingroup$ @CarlMummert: I beg your pardon, sir. Both questions are clear. We are minimizing partial functions. Could this misunderstanding have risen from us considering different definitions of some concept? I gave my definitions in the initial question on CS.SE $\endgroup$ – superAnnoyingUser Feb 12 '14 at 16:44

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


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.

  • $\begingroup$ Thank you, sir. This is very revealing. $\endgroup$ – superAnnoyingUser Feb 12 '14 at 18:05
  • $\begingroup$ However, we must be considering different definitions of minimization. As far as I am concerned if $n\not\in A$, then $f(0,n)$ is undefined and the minimization will not halt. Therefore, $g$ is not a total function. When we minimize the function $f$ we need to make sure that $f(i,n)$ is defined and nonzero for all $i\leq j$, where $j$ is the smallest number such that $f(j,n)=0$ $\endgroup$ – superAnnoyingUser Feb 12 '14 at 18:09
  • $\begingroup$ @Student: By definition, $(\mu i)[f(i,n) = 0]$ is the least $i$ such that $f(i,n) = 0$, if such an $i$ exists. For my function, we have that $f(1,n) = 0$ for all $n$, which means that $(\mu i)[f(i,n) = 0]$ is guaranteed to be a total function - in particular, for all $n$, we have $(\mu i)[f(i,n) = 0] \leq 1$. The definition that you quote is not the standard definition, but is equivalent when the argument of the $\mu$ operator is total. $\endgroup$ – Carl Mummert Feb 12 '14 at 18:12
  • $\begingroup$ To the contrary, by definition it is the least number $i$ such that $f(i,n)=0\land (\forall j<i )(f(j,n)>0)$, if such $i$ exists. $\endgroup$ – superAnnoyingUser Feb 12 '14 at 18:15
  • $\begingroup$ @Student: I am afraid that you have not learned the standard definition. This might be because, in the literature, authors will be careful not to apply the $\mu$ operator to non-total relations. If you wish to use the definition you have stated, you will need to indicate this each time, because it is not what experts will think of when you refer to the $\mu$ operator $\endgroup$ – Carl Mummert Feb 12 '14 at 18:17

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.

  • 1
    $\begingroup$ To avoid any confusion in the future: the usual $\mu$ operator only preserves computability when applied to total relations, as shown at math.stackexchange.com/questions/673633/… . But this question assumes a different definition of the $\mu$ operator, $\mu'$, with $(\mu' i)f(i,x) = (\mu i)[(\forall j < i) f(j,x) \downarrow\not=0] \land f(i,x) \downarrow=0]$. $\endgroup$ – Carl Mummert Feb 13 '14 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.