# Representation of μ-recursive functions

Can every μ-recursive function be defined using a single instance of the μ operator applied to a primitive recursive function?

According to Wikipedia, any μ-recursive function can be expressed as the μ-operator over a primitive recursive function (source):

A consequence of this result is that any μ-recursive function can be defined using a single instance of the μ operator applied to a (total) primitive recursive function.

From this I conclude that given a μ-recursive function $f(x_1,\ldots,x_n)$, I can write it as $\mu y.R(x_1,\ldots,x_n,y)$ with $R$ being a primitive recursive function.

If so, let's say there's a function $h(x,y)$ which is μ-recursive but not primitive recursive and its range is $0,1$. As $h$ is μ-recursive, then I can write it as $\mu z.R(x,y,z)$ for some $R$ primitive recursive. However, as $h$'s range is bounded, the 1-bounded μ-recursive operator (which is primitive recursive) over $R$ should give us $h$ as primitive recursive. Absurd! Regarding the existence of $h$, in this review they show how to construct one of these if I understand correctly.

The question, then, is: what am I misunderstanding in Wikipedia's remark?

Final note: this seems to be an example in Kleene's book Introduction to metamathematics (§58), but I don't see how it is solved.

• The wikipedia article pretty clearly points out that the actual normal form is $U(\mu y. R(x_1,\ldots,x_n,y))$, where $U$ and $R$ are both primitive recursive. So $h(x,y)$ may require the application of another primitive recursive function to $\mu z. R(x,y,z)$. – Henry Towsner Apr 12 '12 at 18:57
• I got wrongly Wikipedia's claim and thought that it meant that you could skip the final $U$. I was doubting whether you could actually represent any μ-recursive $f(x)$ as $\mu y.R(x,y)$ for some primitive recursive $R$ depending on $f$. – Mark T Apr 12 '12 at 19:10

The answer is that you have to apply another primitive recursive function after the $\mu$ operator. Specifically, the Kleene normal form is that every recursive function $f$ has the form $f(n)=U(\mu x T(e,n,x))$, where both $U$ and $T$ are primitive recursive. The predicate $T(e,n,x)$ asserts that $x$ is the code of a halting computation of program $e$ on input $n$, and the function $U$ extracts the output value from this code.
It is the step involving $U$ on which your proposed argument flounders.
Every $\mu$-recursive function can be expressed as a primitive recursive function (usually called $U$) applied to the result of applying the $\mu$ operator to another primitive recursive predicate (usually called $T$). Wikipedia is right that you only need one $\mu$ and it's applied to a primitive recursive $T$, but, as you noted (and as Wikipedia doesn't actually deny) you need additional work ($U$) after you've applied $\mu$.
The idea is that the value of a recursive function $f$ at input $x$ can be described as "the output of the first terminating computation for $f$ on input $x$." The predicate $T$ of being a (Gödel number of a) terminating computation of a particular machine on a particular input is primitive recursive, and so is the function $U$ that extracts the final answer from a computation.