Course of values recursion

Definition and examples

The factorial function n! is recursively defined by the rules

0! = 1, (n+1)! = (n+1)*(n!).

This recursion is a primitive recursion because it computes the next value (n+1)! of the function based on the value of n and the previous value n! of the function. On the other hand, the function Fib(n), which returns the nth Fibonacci number, is defined with the recursion equations

Fib(0) = 0, Fib(1) = 1, Fib(n+2) = Fib(n+1) + Fib(n).

In order to compute Fib(n+2), the last two values of the Fib function are required. Finally, consider the function g defined with the recursion equations

g(0) = 0, g ( n + 1 ) = ∑ i = 0 n g ( i ) n − i .

To compute g(n+1) using these equations, all the previous values of g must be computed; no fixed finite number of previous values is sufficient in general for the computation of g. The functions Fib and g are examples of functions defined by course-of-values recursion.

In general, a function f is defined by course-of-values recursion if there is a fixed primitive recursive function h such that for all n,

f ( n ) = h ( n , ⟨ f ( 0 ) , f ( 1 ) , … , f ( n − 1 ) ⟩ )

where ⟨ f ( 0 ) , f ( 1 ) , … , f ( n − 1 ) ⟩ is a Gödel number encoding the indicated sequence. In particular

f ( 0 ) = h ( 0 , ⟨ ⟩ ) ,

provides the initial value of the recursion. The function h might test its first argument to provide explicit initial values, for instance for Fib one could use the function defined by

h ( n , s ) = { n if  n < 2 s [ n − 2 ] + s [ n − 1 ] if  n ≥ 2

where s[i] denotes extraction of the element i from an encoded sequence s; this is easily seen to be a primitive recursive function (assuming an appropriate Gödel numbering is used).

Equivalence to primitive recursion

In order to convert a definition by course-of-values recursion into a primitive recursion, an auxiliary (helper) function is used. Suppose that one wants to have

f ( n ) = h ( n , ⟨ f ( 0 ) , f ( 1 ) , … , f ( n − 1 ) ⟩ ) .

To define f using primitive recursion, first define the auxiliary course-of-values function that should satisfy

f ¯ ( n ) = ⟨ f ( 0 ) , f ( 1 ) , … , f ( n − 1 ) ⟩

where the right hand side is taken to be a Gödel numbering for sequences.

Thus f ¯ ( n ) encodes the first n values of f. The function f ¯ can be defined by primitive recursion because f ¯ ( n + 1 ) is obtained by appending to f ¯ ( n ) the new element h ( n , f ¯ ( n ) ) :

f ¯ ( 0 ) = ⟨ ⟩ , f ¯ ( n + 1 ) = a p p e n d ( n , f ¯ ( n ) , h ( n , f ¯ ( n ) ) ) ,

where append(n,s,x) computes, whenever s encodes a sequence of length n, a new sequence t of length n + 1 such that t[n] = x and t[i] = s[i] for all i < n. This is a primitive recursive function, under the assumption of an appropriate Gödel numbering; h is assumed primitive recursive to begin with. Thus the recursion relation can be written as primitive recursion:

f ¯ ( n + 1 ) = g ( n , f ¯ ( n ) )

where g is itself primitive recursive, being the composition of two such functions:

g ( i , j ) = a p p e n d ( i , j , h ( i , j ) ) ,

Given f ¯ , the original function f can be defined by f ( n ) = f ¯ ( n + 1 ) [ n ] , which shows that it is also a primitive recursive function.

Application to primitive recursive functions

In the context of primitive recursive functions, it is convenient to have a means to represent finite sequences of natural numbers as single natural numbers. One such method, Gödel's encoding, represents a sequence of positive integers ⟨ n 0 , n 1 , n 2 , … , n k ⟩ as

∏ i = 0 k p i n i ,

where p_i represent the ith prime. It can be shown that, with this representation, the ordinary operations on sequences are all primitive recursive. These operations include

Determining the length of a sequence,

Extracting an element from a sequence given its index,

Concatenating two sequences.

Using this representation of sequences, it can be seen that if h(m) is primitive recursive then the function

f ( n ) = h ( ⟨ f ( 0 ) , f ( 1 ) , f ( 2 ) , … , f ( n − 1 ) ⟩ ) .

is also primitive recursive.

When the sequence ⟨ n 0 , n 1 , n 2 , … , n k ⟩ is allowed to include zeros, it is instead represented as

∏ i = 0 k p i ( n i + 1 ) ,

which makes it possible to distinguish the codes for the sequences ⟨ 0 ⟩ and ⟨ 0 , 0 ⟩ .

Limitations

Not every recursive definition can be transformed into a primitive recursive definition. One known example is Ackermann's function, which is of the form A(m,n) and is provably not primitive resursive.

Indeed, every new value A(m+1, n) depends on the sequence of previously defined values A(i, j), but the i-s and j-s for which values should be included in this sequence depend themselves on previously computed values of the function; namely (i, j) = (m,A(m+1,n)). Thus one cannot encode the previously computed sequence of values in a primitive recursive way in the manner suggested above (or at all, as it turns out this function is not primitive recursive).