Added to Favorites

Popular Searches

Definitions

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 $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.## Definition and examples

The factorial function n! is recursively defined by the rules
## Equivalence to primitive recursion

## 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 represents a sequence $langle\; n\_1,n\_2,ldots,n\_krangle$
as
_{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## References

This article uses the convention that the natural numbers are the set {1,2,3,4,...}.

- 0! = 1,

- (n+1)! = (n+1)*(n!).

- Fib(1) = 1,

- Fib(2) = 1,

- Fib(n+2) = Fib(n+1) + Fib(n).

- g(1) = 2,

- $g(n+1)\; =\; sum\_\{i\; =\; 1\}^\{n\}\; g(i)^n$.

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).$

- $f(1)\; =\; h(langlerangle),$

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)$.

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

- $bar\{f\}(1)\; =\; langle\; h(langlerangle)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.

- $prod\_\{i\; =\; 1\}^k\; p\_i^\{n\_i\}$,

- 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)$.

When the natural numbers are taken to begin with zero, the sequence $langle\; n\_1,n\_2,ldots,n\_krangle$ is instead represented as

- $prod\_\{i\; =\; 1\}^k\; p\_i^\{(n\_i\; +1)\}$,

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

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday June 10, 2008 at 23:50:12 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday June 10, 2008 at 23:50:12 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.