[Solved]: What is the significance of primitive recursive functions?

Problem Detail: 

I was studying the proof of Ackermann function being recursive, but not primitive recursive, and a question hit me: "So what?". Why does it matter? What is the significance of primitive recursive functions?

Asked By : Untitled

Answered By : Yuval Filmus

The halting problem is undecidable, but one might object that for most programs, it is easy to check whether they halt or not, by looking for any obvious infinite loops. Conversely, if you wanted to ensure that your program always terminates, you could do so by bounding a priori the number of loop iterations for every loop. For example, consider the pseudocode for repeated squaring:

def power(x, y, p):    "compute x^y mod p"    assert y >= 0    result = 1    while y > 0:      if x is odd: result = result * x (mod p)      y = y div 2      x = x * x    return result 

How do we know that this procedure always terminates? One way would be to a priori bound the loop:

def power(x, y, p):    "compute x^y mod p"    assert y >= 0    bound = y    result = 1    loop bound times:      if x is odd: result = result * x (mod p)      y = y div 2      x = x * x      if y == 0: break    return result 

Now it's clear that this program terminates, and if we haven't made a mistake elsewhere, the two programs would produce the same output.

Primitive recursive functions are those computed by programs in which all loops are bounded and there is no recursion.

While we do not allow recursion (since it is not bounded), we can simulate it with a loop. We can ask several questions now:

1. Is every computable function presentable in this form?
2. If not, what is the relation between this class and all computable functions?

To answer 1, one can show that certain computable functions which grow "too fast" are not primitive recursive, for example the Ackermann function. Conversely, every function whose growth rate is "reasonable" is primitive recursive. And every computable function can be stated in the form $f(x) = \psi(\min_y \phi(x,y))$ for primitive recursive $\phi,\psi$, where we think of $\phi$ as a predicate.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24152