Question

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.

Answer 1

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.

Answer 2

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.