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.

  • $\begingroup$ 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)$. $\endgroup$ – Henry Towsner Apr 12 '12 at 18:57
  • $\begingroup$ 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$. $\endgroup$ – 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.

  • $\begingroup$ Typo: "founders" should be "flounders" $\endgroup$ – Quinn Culver Apr 14 '12 at 12:30
  • 1
    $\begingroup$ 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. $\endgroup$ – Joel David Hamkins Apr 14 '12 at 14:49
  • 3
    $\begingroup$ Founders is pefectly correct, but flounders made me smile so keep it just for the halibut. $\endgroup$ – Todd Eisworth Apr 14 '12 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.


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.