Английская Википедия:Course-of-values recursion
Шаблон:Short description Шаблон: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) is computed from the sequence <math>\langle f(0),f(1),\ldots,f(n-1)\rangle</math>.
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
- <math>0! = 1,</math>
- <math>(n+1)! = n!(n+1).</math>
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
- <math>Fib(0) = 0,</math>
- <math>Fib(1) = 1,</math>
- <math>Fib(n+2) = Fib(n+1) + Fib(n).</math>
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
- <math>g(0) = 0,</math>
- <math>g(n+1) = \sum_{i = 0}^{n} g(i)^{n-i}.</math>
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,
- <math>f(n) = h(n,\langle f(0), f(1), \ldots, f(n-1)\rangle)</math>
where <math>\langle f(0), f(1), \ldots, f(n-1)\rangle</math> is a Gödel number encoding the indicated sequence. In particular
- <math>f(0) = h(0,\langle\rangle)</math>
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
- <math>h(n,s)=\begin{cases}n&\text{if }n<2\\ s[n-2]+s[n-1]&\text{if }n\geq2\end{cases}</math>
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
- <math>f(n) = h(n,\langle f(0), f(1), \ldots, f(n-1)\rangle)</math>.
To define Шаблон:Math using primitive recursion, first define the auxiliary course-of-values function that should satisfy
- <math>\bar{f}(n) = \langle f(0), f(1), \ldots, f(n-1)\rangle</math>
where the right hand side is taken to be a Gödel numbering for sequences.
Thus <math>\bar{f}(n)</math> encodes the first Шаблон:Math values of Шаблон:Math. The function <math>\bar{f}</math> can be defined by primitive recursion because <math>\bar{f}(n+1)</math> is obtained by appending to <math>\bar{f}(n)</math> the new element <math>h(n,\bar{f}(n))</math>:
- <math>\bar{f}(0) = \langle\rangle</math>,
- <math>\bar{f}(n+1) = \mathit{append}(n,\bar{f}(n),h(n,\bar{f}(n))),</math>
where Шаблон:Math computes, whenever Шаблон:Math encodes a sequence of length Шаблон:Math, a new sequence Шаблон:Math of length Шаблон:Math such that Шаблон:Math and Шаблон:Math for all Шаблон:Math. 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:
- <math>\bar{f}(n+1) = g(n,\bar{f}(n))</math>
where g is itself primitive recursive, being the composition of two such functions:
- <math>g(i,j) = \mathit{append}(i,j,h(i,j)),</math>
Given <math>\bar{f}</math>, the original function Шаблон:Math can be defined by <math>f(n)=\bar{f}(n+1)[n]</math>, 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 <math>\langle n_0,n_1,n_2,\ldots,n_k\rangle</math> as
- <math>\prod_{i = 0}^k p_i^{n_i}</math>,
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
- <math>f(n) = h(\langle f(0), f(1), f(2), \ldots, f(n-1)\rangle)</math>.
is also primitive recursive.
When the sequence <math>\langle n_0,n_1,n_2,\ldots,n_k\rangle</math> is allowed to include zeros, it is instead represented as
- <math>\prod_{i = 0}^k p_i^{(n_i +1)}</math>,
which makes it possible to distinguish the codes for the sequences <math>\langle 0 \rangle</math> and <math>\langle 0,0\rangle</math>.
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.
