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