MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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 2012 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 2012 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.

-
Typo: "founders" should be "flounders" – Quinn Culver Apr 14 2012 at 12:30
Thanks, Quinn, I have edited. – Joel David Hamkins Apr 14 2012 at 12:58
But actually, I think I really did mean "founders" and not "flounders". (e.g. see ldoceonline.com/dictionary/founder_2). For the English language connoisseurs here, vote up this comment, if I should change it back to "founders". Otherwise I'll leave it. – Joel David Hamkins Apr 14 2012 at 14:49
Founders is pefectly correct, but flounders made me smile so keep it just for the halibut. – Todd Eisworth Apr 14 2012 at 15:24

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.

-