Primitive-Recursive Function

Definition

Primitive-Recursive Function

A function is primitive-recursive if it can be constructed in finitely many steps from the following basic functions using composition and primitive recursion:

• Zero functions: .
• Successor function: .
• Projection functions: , where .

The construction rules are:

• Composition: from primitive-recursive and , construct
• Primitive recursion: from primitive-recursive and , construct

Here, denotes the input tuple. Thus the primitive-recursive functions form the smallest class containing the basic functions and closed under these two rules.

Totality and Computability

Every primitive-recursive function is total and computable: the basic functions terminate, composition combines terminating computations, and recursion on performs exactly recursive steps after the base case.

The converse does not hold: some total computable functions, such as the Ackermann function, are not primitive-recursive.

Example

Addition

Definition

Addition ( Primitive Recursion)

Addition , with , is primitive-recursive. Recursing over the first argument gives

The base returns ; each step increases the previous result by one. Thus

Here, is the successor function, denotes a projection function, and is the primitive recursion operator.

Link to original

Multiplication

Definition

Multiplication ( Primitive Recursion)

Multiplication , with , is primitive-recursive. Recursing over the first argument gives

The base returns ; each step adds to the previous result. Thus

Here, is the unary zero function, is addition, and denotes a projection function.

Link to original

Factorial

Definition

Factorial ( Primitive Recursion)

Factorial , with , is primitive-recursive. Its recursive equations are

The base returns ; each step multiplies the previous result by the next natural number . Thus

Here, is a constant with no arguments, is the successor function, is multiplication, and denotes a projection function.

Link to original

Signum

Definition

Signum ( Primitive Recursion)

The natural-number signum is primitive-recursive and satisfies

The base returns ; every step returns , independently of the previous result. Thus

Here, supplies the initial value, while the constant function ignores both the previous index and previous result . Equivalently, signum is the indicator function of the positive natural numbers: .

Link to original

Predecessor function

Definition

Predecessor Function ( Primitive Recursion)

The predecessor function returns for and for . It is primitive-recursive, with

The base returns ; each step returns the previous index , ignoring the previous result. Thus

Here, is a constant with no arguments, and is a projection function. This total version is also called the truncated predecessor, since it stops at rather than becoming negative or undefined.

Link to original

Truncated subtraction

Definition

Truncated Subtraction ( Primitive Recursion)

Truncated subtraction, also called monus, is the primitive-recursive function

Recursing over the second argument gives

The base returns ; each step applies the predecessor function to the previous result. Once the result reaches , it stays there.

To use , which recurses over its first argument, define . Then

Here, denotes a projection function.

Link to original

Negation

Definition

Negation ( Primitive Recursion)

With representing false and representing true, negation is represented by the primitive-recursive function

where the dotted minus denotes truncated subtraction. Thus

On Boolean inputs, and . On all natural numbers, it is the zero test: it returns exactly when .

Link to original

Conjunction

Definition

Conjunction ( Primitive Recursion)

With representing false and representing true, conjunction is represented by the primitive-recursive function

On Boolean inputs , the product is exactly when both inputs are , and otherwise. This uses multiplication directly; outside Boolean inputs, the product need not be a truth value.

Link to original

Disjunction

Definition

Disjunction ( Primitive Recursion)

With representing false and representing true, disjunction is represented by the primitive-recursive function

Addition counts the true inputs; signum converts a positive count to . Thus

On Boolean inputs, the result is exactly when at least one input is . More generally, it returns exactly when at least one natural-number input is positive.

Link to original

Less-than predicate

Definition

Less-Than Predicate ( Primitive Recursion)

The less-than predicate on natural numbers has the primitive-recursive indicator function

The result is when and otherwise. Truncated subtraction computes the non-negative difference ; signum tests whether it is positive. Thus

The projections swap the inputs so that the difference is , not . In particular, the less-than predicate is decidable.

Link to original