Machine model for primitive recursion? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T00:49:35Z http://mathoverflow.net/feeds/question/73068 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73068/machine-model-for-primitive-recursion Machine model for primitive recursion? David Harris 2011-08-17T14:59:24Z 2011-08-18T03:06:27Z <p>General computable functions can be described either functionally (in terms of closure of the coordinate functions, constant functions, composition, primitive recursion, and $\mu$-recursion), or in terms of a Turing machine. </p> <p>I have only seen primitive recursion defined in the functional language, i.e. functions obtained by coordinates, constants, composition, primitive recursion.</p> <p>Is there a similar type of machine model for primitive recursion?</p> <p>I am aware of some (pedagogical) programming languages, such as Hofstadter's BLOOP, that are PR-complete, but this approach doesn't really look like a Turing machine to me.</p> http://mathoverflow.net/questions/73068/machine-model-for-primitive-recursion/73079#73079 Answer by Adam for Machine model for primitive recursion? Adam 2011-08-17T17:31:38Z 2011-08-18T03:06:27Z <p>If you're willing to accept <a href="http://en.wikipedia.org/wiki/Register_machine" rel="nofollow">register machines</a> (rather than just tape machines), you can get what you want via the <a href="http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy" rel="nofollow">Grzegorczyk hierarchy</a>, which generates the class of primitive recursive functions in stages.</p> <p>The ${n+1}^{th}$ stage of the hierarchy ${\mathscr E}_{n+1}$ is the closure of the zero, successor, projection, and <a href="http://en.wikipedia.org/wiki/Hyper_operation" rel="nofollow">hyper operation</a> $H_n$ function under composition and <em>bounded recursion</em>.</p> <p>Bounded recursion is defined just like primitive recursion, except that when defining a function $f$ at the ${n+1}^{th}$ level, the definitions of the base case and inductive case for $f(m,\bar x)$ must take the form $\text{min}(g(m,\bar x),...)$ where $g$ is a function from the $n^{th}$ level.</p> <p>Every primitive recursive function belongs to ${\mathscr E}_n$ for some $n$, and every function in the hierarchy is primitive recursive.</p> <p>Beltiukov's <a href="http://www.mathnet.ru/links/997df5ff55640141a337239e0c83e37c/znsl_3100_card_eng.pdf" rel="nofollow">stack register machines</a> (also <a href="http://www.springerlink.com/content/r0h6nw66t123l5g6/fulltext.pdf" rel="nofollow">here</a>) give a "machine-oriented" characterization of the Grzegorczyk hierarchy -- and therefore of the primitive recursive functions. There is a slightly more accessible description of stack register machines <a href="http://www.springerlink.com/content/f74740307h6x3880/fulltext.pdf" rel="nofollow">here</a>, starting on page 108.</p>