most recent 30 from http://mathoverflow.net 2013-05-19T04:53:30Z http://mathoverflow.net/feeds/question/93887 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/93887/representation-of-recursive-functions Mark T 2012-04-12T17:46:09Z 2012-04-14T12:58:25Z

<p>Can every μ-recursive function be defined using a single instance of the μ operator applied to a primitive recursive function?</p> <p>According to Wikipedia, any μ-recursive function can be expressed as the μ-operator over a primitive recursive function (<a href="https://en.wikipedia.org/wiki/%25CE%259C-recursive_function#Normal_form_theorem" rel="nofollow">source</a>):</p> <blockquote> <p>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.</p> </blockquote> <p>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.</p> <p>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 <a href="http://www.jstor.org/stable/2269168" rel="nofollow">this review</a> they show how to construct one of these if I understand correctly.</p> <p>The question, then, is: what am I misunderstanding in Wikipedia's remark?</p> <p>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.</p>

http://mathoverflow.net/questions/93887/representation-of-recursive-functions/93893#93893 Andreas Blass 2012-04-12T18:52:02Z 2012-04-12T18:52:02Z

<p>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$.</p> <p>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.</p>

http://mathoverflow.net/questions/93887/representation-of-recursive-functions/93895#93895 Joel David Hamkins 2012-04-12T18:55:39Z 2012-04-14T12:58:25Z

<p>The answer is that you have to apply another primitive recursive function after the $\mu$ operator. Specifically, the <a href="https://en.wikipedia.org/wiki/Kleene%27s_T_predicate" rel="nofollow">Kleene normal form</a> 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. </p> <p>It is the step involving $U$ on which your proposed argument flounders.</p>