## Recursive Function

A recursive function is a function generated by (1) Addition, (2) Multiplication, (3) selection of an element from a list, and (4) determination of the truth or falsity of the Inequality according to the technical rules:

1. If and the sequence of functions , ..., are recursive, then so is ).

2. If is a recursive function such that there is an for each with , then the smallest can be obtained recursively.
A Turing Machine is capable of computing recursive functions.

See also Turing Machine

References

Kleene, S. C. Introduction to Metamathematics. Princeton, NJ: Van Nostrand, 1952.

© 1996-9 Eric W. Weisstein
1999-05-25