Primitive Recursion

Definition

Primitive Recursion

Primitive recursion constructs a function from a base function and a step function . Let and be total functions with types

Write for the unchanged parameters. The function is uniquely specified by:

Base: initialise the result

The base function supplies the result at index .

Step: use the previous result

The step function receives the previous index , previous result , and unchanged parameters . Here, abbreviates .

For fixed , let . The graph shows each result feeding the next application of ; the parameters stay unchanged:

Computing requires the base case followed by applications of . Since and are total, is total. For , there are no unchanged parameters and supplies a fixed initial value.

Computability

Primitive-recursive functions are computable and total. However, not every computable total function is primitive-recursive.

We can list all primitive-recursive functions as . This gives the following table:

Then the diagonal function

is computable and total.

For any fixed , compare with at input :

The output of is exactly one larger than the output of at that input. Therefore, . Since equal functions must agree on every input, . This holds for every , so is not primitive-recursive.

Not all total computable functions are primitive-recursive

Not all computable total functions are primitive-recursive.

Ackermann function

The Ackermann function is computable and total, but not primitive-recursive.

Guaranteed termination forces incompleteness

There is no programming language in which every program terminates and in which every total computable function is expressible.

Examples

Example

Example

Example

Example

Example

Example

We want to find an equivalent -expression for:

First, we want to represent recursively:

Now, it’s easier to write as -expresion:

The above immediately increments , as the never uses alone and uses multiple times in the recursive definition.