Course-of-values recursion

In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. In Number theory an arithmetic function or arithmetical function is a Function defined on the set of Natural numbers (i Recursion in computer science is a way of thinking about and solving problems 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. The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict Subset of the recursive

This article uses the convention that the natural numbers are the set {1,2,3,4,. In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an . . }.

1 Definition and examples
2 Equivalence to primitive recursion
3 Application to primitive recursive functions
4 References

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 only requires the previous value n! in order to compute the next value (n+1)!. On the other hand, the function Fib(n), which returns the nth Fibonacci number, is defined with the recursion equations

Fib(1) = 1,

Fib(2) = 1,

Fib(n+2) = Fib(n+1) + Fib(n). In Mathematics, the Fibonacci numbers are a Sequence of numbers named after Leonardo of Pisa, known as Fibonacci

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(1) = 2,

$g(n+1) = \sum_{i = 1}^{n} g(i)^n$ .

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 function h such that for all n,

$f(n) = h(\langle f(1), f(2), \ldots, f(n-1)\rangle).$

In this notation,

$f(1) = h(\langle\rangle),$

and thus the initial value(s) of the recursion must be "hard coded" into h.

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

$f(n) = h(\langle f(1), f(2), \ldots, f(n-1)\rangle)$ .

To redefine f using primitive recursion, first define the auxiliary course-of-values function

$\bar{f}(n) = \langle f(1), f(2), \ldots, f(n-1), h(\langle f(1), f(2), \ldots, f(n-1)\rangle)\rangle.$

Thus $\bar{f}$ encodes the first n values of f, and $\bar{f}$ is defined by primitive recursion because $\bar{f}(n+1)$ is the concatenation of $\bar{f}(n)$ and the one-element sequence $\langle h(\bar{f}(n)) \rangle$ :

$\bar{f}(1) = \langle h(\langle\rangle)\rangle$ ,

$\bar{f}(n+1) = \bar{f}(n) \smallfrown \langle h(\bar{f}(n))\rangle$ .

Given $\bar{f}$ , the original function f can be defined by letting f(n) be the final element of the sequence $\bar{f}(n)$ . Thus f can be defined without a course-of-values recursion in any setting where it is possible to handle sequences of natural numbers. Such settings include LISP and the primitive recursive functions, discussed in the next section. Lisp (or LISP) is a family of Computer Programming languages with a long history and a distinctive fully parenthesized syntax The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict Subset of the recursive

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. The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict Subset of the recursive One such method 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.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents

Definition and examples

Equivalence to primitive recursion

Application to primitive recursive functions

References