Course-of-values recursion explained

In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. In a definition of a function f by course-of-values recursion, the value of f(n) is computed from the sequence

\langle f( 0 ),f( 1 ),\ldots,f(n -1 )\rangle .

The fact that such definitions can be converted into definitions using a simpler form of recursion is often used to prove that functions defined by course-of-values recursion are primitive recursive. Contrary to course-of-values recursion, in primitive recursion the computation of a value of a function requires only the previous value; for example, for a 1-ary primitive recursive function g the value of g(n+1) is computed only from g(n) and n.

Definition and examples

The factorial function n! is recursively defined by the rules

0 ! = 1 , (n +1 )! = n!(n +1 ). 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 equationsFib( 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 equationsg( 0 ) = 0 , g(n +1 ) = \sum ^{n} _{i =0} 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,\langle f( 0 ), f( 1 ), \ldots, f(n -1 )\rangle) where \langle f( 0 ), f( 1 ), \ldots, f(n -1 )\rangle is a Gödel number encoding the indicated sequence.In particularf( 0 ) = h( 0 ,\langle\rangle) 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 byh(n,s) = \begin{cases}n& if n< 2 \ s[n -2 ] + s[n -1 ]& if n\geq 2 \end{cases} 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,\langle f( 0 ), f( 1 ), \ldots, f(n -1 )\rangle) .To define using primitive recursion, first define the auxiliary course-of-values function that should satisfy\bar{f}(n) = \langle f( 0 ), f( 1 ), \ldots, f(n -1 )\rangle where the right hand side is taken to be a Gödel numbering for sequences.

Thus

\bar{f}(n) encodes the first values of . The function \bar{f} can be defined by primitive recursion because \bar{f}(n +1 ) is obtained by appending to \bar{f}(n) the new element h(n,\bar{f}(n)) :\bar{f}( 0 ) = \langle\rangle ,\bar{f}(n +1 ) = append (n,\bar{f}(n),h(n,\bar{f}(n))), where computes, whenever encodes a sequence of length, a new sequence of length such that and for all . 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:\bar{f}(n +1 ) = g(n,\bar{f}(n)) where g is itself primitive recursive, being the composition of two such functions:g(i,j) = append (i,j,h(i,j)),

Given

\bar{f} , the original function can be defined by f(n) = \bar{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

\langle n _{0,n} _{1,n} _{2,\ldots,n} _{k\rangle} as\prod ^{k} _{i =0} p ^{n _{i}} _{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(\langle f( 0 ), f( 1 ), f( 2 ), \ldots, f(n -1 )\rangle) .is also primitive recursive.

When the sequence

\langle n _{0,n} _{1,n} _{2,\ldots,n} _{k\rangle} is allowed to include zeros, it is instead represented as\prod ^{k} _{i =0} p ^{(n _{i} +1 )} _{i} ,which makes it possible to distinguish the codes for the sequences \langle 0 \rangle and \langle 0 , 0 \rangle .

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 recursive.

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).

References

• Hinman, P.G., 2006, Fundamentals of Mathematical Logic, A K Peters.
• Odifreddi, P.G., 1989, Classical Recursion Theory, North Holland; second edition, 1999.