HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Are Primitive recursive functions (with bounded $\mu$ operator) equivalent to other known computational model?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
equivalentoperatorarewithcomputationalprimitiverecursiveknownboundedfunctions

Problem

There is a famous equivalence between types of grammars and automatons. However when discussing recursive functions, we only consider equivalence of General Recursive functions with Turing machines. However primitive recursive functions are considered separately and I don't know any equivalence of that computational model with any other. I was wondering whether primitive recursive functions are equivalent to any other known computational model. I was thinking about Turing Machine with bounded tape size (linearly bounded), since primitive recursive functions have bounded $\mu$ operator. However I couldn't find any result that would say that, so is there any known computational model equivalent to primitive recursive functions?

Solution

LOOP is a simple programming language which exactly captures primitive recursive functions.

Primitive recursive functions also have other characterizations. For example, they are the functions which are provably total in $\rm I\Sigma_1$ (a fragment of Peano arithmetic), and they are the functions computable by a Turing machine whose running time is in the Grzegorczyk hierarchy.

Context

StackExchange Computer Science Q#167302, answer score: 5

Revisions (0)

No revisions yet.