Machine model for primitive recursion?

2011-08-17T14:59:24Z

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.

I have only seen primitive recursion defined in the functional language, i.e. functions obtained by coordinates, constants, composition, primitive recursion.

Is there a similar type of machine model for primitive recursion?

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.

Answer by Adam for Machine model for primitive recursion?

2011-08-17T17:31:38Z

If you're willing to accept register machines (rather than just tape machines), you can get what you want via the Grzegorczyk hierarchy, which generates the class of primitive recursive functions in stages.

The ${n+1}^{th}$ stage of the hierarchy ${\mathscr E}_{n+1}$ is the closure of the zero, successor, projection, and hyper operation $H_n$ function under composition and bounded recursion.

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.

Every primitive recursive function belongs to ${\mathscr E}_n$ for some $n$, and every function in the hierarchy is primitive recursive.

Beltiukov's stack register machines (also here) 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 here, starting on page 108.

Machine model for primitive recursion? - MathOverflow

Machine model for primitive recursion?

Answer by Adam for Machine model for primitive recursion?