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 $\backslash langle\; f(0),f(1),\backslash ldots,f(n-1)\backslash 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 ''n''th 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)\; =\; \backslash sum\_^\; g(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,\backslash langle\; f(0),\; f(1),\; \backslash ldots,\; f(n-1)\backslash rangle)$ where $\backslash langle\; f(0),\; f(1),\; \backslash ldots,\; f(n-1)\backslash rangle$ is a Gödel number encoding the indicated sequence. In particular :$f(0)\; =\; h(0,\backslash langle\backslash 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)=\backslash beginn\&\backslash textn<2\backslash \backslash \; s-2s-1\backslash textn\backslash geq2\backslash end$ 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,\backslash langle\; f(0),\; f(1),\; \backslash ldots,\; f(n-1)\backslash rangle)$. To define using primitive recursion, first define the auxiliary course-of-values function that should satisfy :$\backslash bar(n)\; =\; \backslash langle\; f(0),\; f(1),\; \backslash ldots,\; f(n-1)\backslash rangle$ where the right hand side is taken to be a Gödel numbering for sequences. Thus $\backslash bar(n)$ encodes the first values of . The function $\backslash bar$ can be defined by primitive recursion because $\backslash bar(n+1)$ is obtained by appending to $\backslash bar(n)$ the new element $h(n,\backslash bar(n))$: :$\backslash bar(0)\; =\; \backslash langle\backslash rangle$, :$\backslash bar(n+1)\; =\; \backslash mathit(n,\backslash bar(n),h(n,\backslash bar(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: :$\backslash bar(n+1)\; =\; g(n,\backslash bar(n))$ where ''g'' is itself primitive recursive, being the composition of two such functions: :$g(i,j)\; =\; \backslash mathit(i,j,h(i,j)),$ Given $\backslash bar$, the original function can be defined by $f(n)=\backslash bar(n+1)/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 $\backslash langle\; n\_0,n\_1,n\_2,\backslash ldots,n\_k\backslash rangle$ as :$\backslash prod\_^k\; p\_i^$, where ''p''_{''i''} represent the ''i''th 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(\backslash langle\; f(0),\; f(1),\; f(2),\; \backslash ldots,\; f(n-1)\backslash rangle)$.
is also primitive recursive.
When the sequence $\backslash langle\; n\_0,n\_1,n\_2,\backslash ldots,n\_k\backslash rangle$ is allowed to include zeros, it is instead represented as
:$\backslash prod\_^k\; p\_i^\{(n\_i\; +1)\}$,
which makes it possible to distinguish the codes for the sequences $\backslash langle\; 0\; \backslash rangle$ and $\backslash langle\; 0,0\backslash 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.
Category:Computability theory
Category:Recursion

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 ''n''th 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)\; =\; \backslash sum\_^\; g(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,\backslash langle\; f(0),\; f(1),\; \backslash ldots,\; f(n-1)\backslash rangle)$ where $\backslash langle\; f(0),\; f(1),\; \backslash ldots,\; f(n-1)\backslash rangle$ is a Gödel number encoding the indicated sequence. In particular :$f(0)\; =\; h(0,\backslash langle\backslash 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)=\backslash beginn\&\backslash textn<2\backslash \backslash \; s-2s-1\backslash textn\backslash geq2\backslash end$ 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,\backslash langle\; f(0),\; f(1),\; \backslash ldots,\; f(n-1)\backslash rangle)$. To define using primitive recursion, first define the auxiliary course-of-values function that should satisfy :$\backslash bar(n)\; =\; \backslash langle\; f(0),\; f(1),\; \backslash ldots,\; f(n-1)\backslash rangle$ where the right hand side is taken to be a Gödel numbering for sequences. Thus $\backslash bar(n)$ encodes the first values of . The function $\backslash bar$ can be defined by primitive recursion because $\backslash bar(n+1)$ is obtained by appending to $\backslash bar(n)$ the new element $h(n,\backslash bar(n))$: :$\backslash bar(0)\; =\; \backslash langle\backslash rangle$, :$\backslash bar(n+1)\; =\; \backslash mathit(n,\backslash bar(n),h(n,\backslash bar(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: :$\backslash bar(n+1)\; =\; g(n,\backslash bar(n))$ where ''g'' is itself primitive recursive, being the composition of two such functions: :$g(i,j)\; =\; \backslash mathit(i,j,h(i,j)),$ Given $\backslash bar$, the original function can be defined by $f(n)=\backslash bar(n+1)/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 $\backslash langle\; n\_0,n\_1,n\_2,\backslash ldots,n\_k\backslash rangle$ as :$\backslash prod\_^k\; p\_i^$, where ''p''