Course-of-values recursion

From formulasearchengine
Jump to navigation Jump to search

Template:No footnotes 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 . 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,

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,

where is a Gödel number encoding the indicated sequence. In particular

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

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


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

Thus encodes the first n values of f. The function can be defined by primitive recursion because is obtained by appending to the new element :


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 , the original function f can be defined by , 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 as


where pi 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


is also primitive recursive.

When the natural numbers are taken to begin with zero, the sequence is instead represented as


which makes it possible to distinguish the codes for the sequences and .


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