In
computability theory, course-of-values recursion is a technique for defining
number-theoretic function
In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function ''f''(''n'') whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their d ...
s by
recursion
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathemati ...
. In a definition of a function ''f'' by course-of-values recursion, the value of ''f''(''n'') 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
In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
. 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
:
:
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 ''n''th
Fibonacci number
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
, is defined with the recursion equations
:
:
:
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
:
:
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 using primitive recursion, first define the auxiliary course-of-values function that should satisfy
:
where the right hand side is taken to be a
Gödel numbering for sequences
In mathematics, a Gödel numbering for sequences provides an effective way to represent each finite sequence of natural numbers as a single natural number. While a set theoretical embedding is surely possible, the emphasis is on the effectiveness ...
.
Thus
encodes the first values of . The function
can be defined by primitive recursion because
is obtained by appending to
the new element
:
:
,
:
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:
:
where ''g'' is itself primitive recursive, being the composition of two such functions:
:
Given
, the original function can be defined by