Course-of-values recursion

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+1) is computed from the sequence $\langle f(1),f(2),\ldots,f(n)\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.

This article uses the convention that the natural numbers are the set {1,2,3,4,...}.

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) = \sum_{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,\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 particular

$f(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 by

$h(n,s)=\begin{cases}n&\text{if }n<2\\ s[n-2]+s[n-1]&\text{if }n\geq2\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 f 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.$

Thus $\bar{f}(n)$ encodes the first n values of f. 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) = \mathit{append}(n,\bar{f}(n),h(n,\bar{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 (again this is a primitive recursive function, under the assumption of an appropriate Gödel numbering).

Given $\bar{f}$, the original function f 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 $\langle n_1,n_2,\ldots,n_k\rangle$ as

$\prod_{i = 1}^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(\langle f(1), f(2), \ldots, f(n-1)\rangle)$.

is also primitive recursive.

When the natural numbers are taken to begin with zero, the sequence $\langle n_1,n_2,\ldots,n_k\rangle$ is instead represented as

$\prod_{i = 1}^k p_i^{(n_i +1)}$,

which makes it possible to distinguish the codes for the sequences $\langle 0 \rangle$ and $\langle 0,0\rangle$.

References

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