What is the difference between total recursive and primitive recursive functions

Question

I am studying the theory of computation. Here are some terminologies that I am confused about.

Are total recursive function and primitive recursive function equivalent? I think they are equal because their domains are both total and they always generate output.

Can anyone tell me if there is some difference?

Answer 1

There is another example of a non-primitive-recursive but total computable function that explains better what the restricted definition of primitive recursion entails.

Each primitive recursive function is defined by a particular finite set of recursion equations, in terms of a fixed set of basic functions. We can use this to define an effective scheme for indexing all the primitive recursive functions. Let $(f_e : e \in \mathbb{N})$ be an effective indexing of the unary primitive recursive functions, meaning that

• Every unary primitive recursive function is of the form $f_{e_f}(n)$ for some fixed $e_f$.

• There is a single algorithm to compute $f_e(n)$ given $e$ and $n$.

Let $g(e,n)$ be the function that computes $f_e(n)$. We call $g$ a universal binary function. It is universal in the sense that it encapsulates all unary primitive recursive functions.

The function $g(e,n) = f_e(n)$ is certainly a total computable function. But it is not primitive recursive:

Suppose that $g(e,n)$ is primitive recursive. Then the function $f(n) = g(n,n)+1$ is also primitive recursive, as you can verify. But this function $f(n)$ cannot be of the form $g(e,n)$ for any fixed $e$, because for every $e$ we have $f(e) = g(e,e) + 1 \not = g(e,e)$, by the definition of $f$. Thus $g$ is total computable but not primitive recursive.

This diagonalization proof can be used in any system that is closed under a few basic operations. The moral of this construction is a key fact in computability theory:

A system of functions in which every function is total, and which has certain basic closure properties, cannot include a (total) universal binary function. The basic closure properties are the ones used in the proof above.

The point is that there is a fundamental incompatibility between the goal of making a system concrete enough that every function is total, and making a system strong enough that it includes universal functions for itself. Only one of these goals can be achieved at a time.

There is a universal binary partial function for the set of unary total computable functions. In fact there is a universal binary partial function for the set of unary partial computable functions, a larger class. This fact is essentially equivalent to the existence of a universal Turing machine.

Answer 2

The Ackermann function, for example, is recursive, but is not primitive recursive. Indeed it "grows faster" than any primitive recursive function. From the definition in the link, it is not difficult to write an explicit program that computes the Ackermann function. There are many other concrete examples. The class of primitive recursive functions is a small subclass of the class of recursive functions.

Answer 3

They are not equivalent. The standard example is the Ackermann function, which is (total) recursive, but not primitive recursive. But if you are a programmer, here's another way to think of the difference between total recursive and primitive recursive functions. I'll discuss this in terms of an idealized imperative programming language running on an idealized computer (no memory or storage limits). You can think in terms of any standard imperative language, such as C or Java.

A total recursive function is any function you can write which always terminates.

A primitive recursive function is any function you can write where the only loops are those of the form "for i=1 to n do ..." Here $n$ is fixed in advance (before the loop starts), and you cannot (explicitly) change $i$ nor $n$ inside the loop. So the number of times the loop executes is determined in advance. This is the only looping structure allowed. You do not have a while loop, which terminates based on a condition, or a goto statement that can jump back to an arbitrary point in the code, or recursive function calls. These conditions make infinite loops impossible.

An example of a programming language that only supports primitive recursive functions is BlooP (this stands for Bounded Loop). It is impossible to write an infinite loop in BlooP, whereas it is undecidable whether a general program terminates.

However, even though all BlooP programs terminate, there are terminating programs that cannot be written in BlooP. The Ackermann function is one of them. The simplest example, though, is the BlooP interpreter. This is a program that takes as input a BlooP program plus any input the BlooP program requires, then runs the BlooP program, and produces its output. Since BlooP programs always terminate, the interpreter always terminates too. But it cannot be written in BlooP, by a diagonalization argument.

Roughly, the diagonalization argument goes as follows: For simplicity, we'll assume all functions map natural numbers to natural numbers. (Other types of inputs can be simulated by a Goedel encoding.) Let $B_1, B_2, \ldots$ be a recursive list of all BlooP programs, and set $f(n) = B_n(n) + 1$. Since every $B_n$ terminates, $f$ always terminates too, and is therefore total recursive. But $f \ne B_n$ for any $n$, since they differ at the value $n$ by construction. So $f$ is already an example of a total recursive function not primitive recursive (i.e. not expressible in BlooP). But since the only obstacle to calculating $f$ is the calculation of $B_n(n)$, which can be achieved by an interpreter, it follows that the BlooP interpreter cannot be written in BlooP.