1
$\begingroup$

Assume $\{f_i^{(n)}\}_{i=0}^\infty$ is a Gödel enumeration of the $\mu$-recursive functions of $n$ arguments, such that the $S^m_n$ theorem and the universal function theorem hold. Denote the set of (total and partial) functions $\{f:\mathbb N^k\to\mathbb N\ \}$ by $\mathfrak F^k$

Definition: We call an operator $G:\mathfrak F^n\to\mathfrak F^k$ effective, if $(\forall j\in\mathbb N)(G(f^{(n)}_j)=f^{(k)}_{g(j)})$ for some total recursive function $g$.

Claim: The minimization operator $\mu:\mathfrak F^{k+1}\to\mathfrak F^k$ defined by $$\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))$$ is an effective operator.

Question: How can I go about proving the statement? Hints are welcome.

Thought: By definition the $\mu$-recursive functions are closed with respect to the $\mu$-operator. Therefore, $\mu(f^{(k+1)}_j)=f^{(k)}_{h(j)}$, for some unique total function $h$. But why is $h$ a computable function?

Note that I would really like to stay within the Partial Recursive Functions Formalism. Pseudo code means nothing to me. I cannot read it. I am not familiar with most of the notation from the programming world. I would also prefer not go into Register Machine Formalisms.

|cite|improve this question
$\endgroup$

migrated from cstheory.stackexchange.com Feb 10 '14 at 23:09

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ I'm not sure what you mean when you say an operator is primitive recursive, @cody. Would you make that more clear? $\endgroup$ – superAnnoyingUser Feb 10 '14 at 18:56
  • $\begingroup$ This should be some definition juggling. You will probably need to use either or both of the $S^m_n$ theorem and the universal function theorem. $\endgroup$ – Yuval Filmus Feb 11 '14 at 6:37
  • 1
    $\begingroup$ Well, you have to describe a total recursive function $g$ that realizes $\mu$. With a bit of care $g$ turns out to be primitive recursive, and so then we say that $\mu$ is primitive recursive. $\endgroup$ – Andrej Bauer Feb 11 '14 at 10:19
  • $\begingroup$ To expand on what @Andrej Bauer is saying: there is a primitive recursive function $m\colon \mathbb{N}\to\mathbb{N}$ such that, whenever $e$ is a program such that $f_e(i,j)$ is a total computable function of two variables, $f_{m(e)}(j)$ is the (partial) computable function $(\mu i) [f_e(i,j) = 0]$. The key point is that $m$ is only guaranteed to be correct when $e$ is actually a program for a total computable function. $\endgroup$ – Carl Mummert Feb 12 '14 at 18:10
  • $\begingroup$ @CarlMummert Which $\mu$-operator are you using? It's quite clear (imho) that the question uses the unbounded one. $\endgroup$ – Raphael♦ Feb 13 '14 at 11:31
2
$\begingroup$

It's a direct application of the smn-theorem if you don't let the currying get in your way.

Since $\mu : \mathbb{N}^{k+1} \to \mathbb{N}$ is computable (by definition), there is $i \in \mathbb{N}$ so that

$\qquad\displaystyle \mu = f^{(k+1)}_i$.

Now the smn-theorem asserts the existence of a recursive and total $g' : \mathbb{N}^2 \to \mathbb{N}$ with

$\qquad\displaystyle f^{(k+1)}_i(x_0, x_1, \dots, x_k) = f^{k}_{g'(i,x_0)}(x_1, \dots, x_k)$

for all $(x_0,\dots,x_k) \in \mathbb{N}^{k+1}$. Because $i$ is fixed, we get (again via smn-theorem) a recursive and total $g : \mathbb{N} \to \mathbb{N}$ with

$\qquad \mu(f,\overline{x}) = f^{(k+1)}_i(f,\overline{x}) = f^{k}_{g'(i,f)}(\overline{x}) = f^{k}_{g(f)}(\overline{x})$

for all $\overline{x} \in \mathbb{N}^k$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I have to revive our discussion. If I am guessing correctly you define a function of the same name $\mu$ by the equality $\mu(x_0,\dots,x_k)=\mu(f_{x_0})(x_1,\dots,x_k)$. So for any fixed first argument $x_0$, the function $\lambda x_1,\dots,x_k.\mu(x_0,x_1,\dots,x_k)$ is recursive. However, that $\mu$ is computable is not obvious. What is more, in the comments here, @Carl Mummert suggests it is not computable at all. Would you care to explain why $\mu$ is computable? $\endgroup$ – superAnnoyingUser Feb 12 '14 at 17:57
  • $\begingroup$ The question here says that $\frak{F}$ is a set of functions, i.e. total functions. The $\mu$ operator is indeed computable by definition when applied to total functions, but as I explain on the other question, the $\mu$ operator is not effective when applied to partial functions. See math.stackexchange.com/a/674076/630 $\endgroup$ – Carl Mummert Feb 12 '14 at 18:05
  • $\begingroup$ @CarlMummert 1) "a set of functions, i.e. total functions" -- I don't agree with the "i.e."; in this context, "function" means "partial function" (to me, i.e. that's what I assume in my answer). 2) The definition of the $\mu$ operator I assume is the one I learned (see e.g. Wikipedia) -- the search may very well loop, depending on parameter $f$. From there, I believe my derivation is valid. $\endgroup$ – Raphael♦ Feb 12 '14 at 18:30
  • $\begingroup$ cc @Student -- what assumptions do you make? Is your $\mu$ the standard $\mu$, or are you aiming at a deciding $\mu$? What should the output be on, say, $f = (1,\uparrow,0,\dots)$? $\endgroup$ – Raphael♦ Feb 12 '14 at 18:31
  • $\begingroup$ @Raphael: as always, Wikipedia is somewhat fickle. They do give the standard definition of the $\mu$ operator at en.wikipedia.org/wiki/%CE%9C_operator . Compare e.g. exercise 4.24 in Soare's book $\endgroup$ – Carl Mummert Feb 12 '14 at 18:36
3
$\begingroup$

The best way to solve such problems is to understand what they amount to in real programming code. All the stuff about Gödel encoding is very mathy and fancy but uneccessary in this day and age.

We can think of Gödel codes of $\mu$-recursive functions as source code. The fact that an enumeration satisfies the smn theorems amounts to the fact that, given the source code of a function on $k$ arguments, we can calculate the source code of the same function with one of the arguments fixed to a particular value. The utm theorem just says that there is an intepreter for the source code.

An operator $G$ is effective if there is a program which converts the source code of a function $f$ to the source code of $G(f)$. This program must work for all valid inputs (is total). To see that the minimization operator is effective we thus have to write a program p which does the following:

  • Input: source code $S$ of a function $f$
  • Output: source code for the function $\bar{x} \mapsto \mu \, y [f(y,\bar{x}) = 0]$

Our program converts some source code to some other source code. It should not try to minimize anything, or simulate $f$, or anything like that. At this point you should stop reading and do the exercise yourself, in whatever your favorite programming language is.

Really, stop reading and do it yourself.

Here is my solution:

def p(k, s):
    """Convert source code s of a function in k+1 arguments to a function in k arguments which
       minimizes in the first argument. We assume that the source code s for the function
       is given in the following form (had we chosen a more decent programming language,
       we could have used anonymous functions instead):

              "def f(x0, ..., xk):
                 <body of function>
              "

       The output is given as a source code of a function in the following format:

              "def f(x1, ..., xk):
                  <body of function>
              "
    """

    # The string "x1, ..., xk"
    xs = ", ".join(["x{0}".format(k) for k in range(1,k+1)])
    # The source code s indended by 4 characters
    s4 = "\n".join("    " + l for l in s.split("\n"))
    # Now we can generate the output
    return ("""def f({0}):
{1}
    y = 0
    while True:
       if f(y, {0}) == 0: return y
       else: y = y + 1
    """.format(xs, s4))

Our program p corresponds to a primitive recursive function because it contains only for loops with prescribed bounds (the while True is not part of our program because it is inside a string and so is really part of the source code that our program outputs).

Let us try an example:

## We look for the least y such that x <= 2 * y.

s = """def f(y,x):
   return (1 if x <= 2 * y else 0)
"""

t = p(1,s)

print(t)

The output printed is:

def f(x1):
    def f(y,x):
       return (1 if x <= 2 * y else 0)

    y = 0
    while True:
       if f(y, x1) == 0: return y
       else: y = y + 1
|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ "All the stuff about Gödel encoding is very mathy and fancy but uneccessary in this day and age." -- can you give a reference to a deep introduction to computability (I'm looking at fixed-point theorem, s-m-n property, Rice's theorem and the like) that does not use such "mathy and fancy" stuff? $\endgroup$ – Raphael♦ Feb 11 '14 at 11:07
  • $\begingroup$ Thank you, sir. I wish I could appreciate your answer. It means nothing to me. I never cared to learn any programming language. $\endgroup$ – superAnnoyingUser Feb 11 '14 at 11:19
  • $\begingroup$ @Student If you wish to ever apply recursion theory to a real problem (that includes understanding why and how idealized programming languages are Turing complete), you might well have to. $\endgroup$ – Raphael♦ Feb 11 '14 at 12:00
  • 2
    $\begingroup$ Well then, I give up with @Student, since he so easily gives up too. $\endgroup$ – Andrej Bauer Feb 11 '14 at 12:14
  • $\begingroup$ @Raphael, such a textbook still needs to be written. But I am sure that, pedagogically speaking, it is better to minimize the use of Gödelization, especially in those cases where actual working alternatives exist. I wouldn't eliminate Gödel encodings and the classical uses of "numbers as code". Rather, I would relate that stuff to actual programming so that people can see that all they're doing is programming in an unusual programming language. And for concrete examples such as this one, I would tell them to solve them in Python. $\endgroup$ – Andrej Bauer Feb 11 '14 at 12:15

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.