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 $a<b$ according to the technical rules:

1. If $F$ and the sequence of functions $G_1$, ..., $G_n$ are recursive, then so is $F(G_1, \ldots, G_n$).

2. If $F$ is a recursive function such that there is an $x$ for each $a$ with $H(a,x)=0$, then the smallest $x$ 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.