recursive function theory

<logic> If we start with a small number of intuitively computable functions, and a small number of operations that create new computable functions from old ones, then we can generate a large set of functions called recursive functions. If we pick the initial functions and building operations so as to capture what we take to be all the intuitively computable functions, then we generate a set with the same extension as the set of Turing-computable functions. (This led Church to conjecture - Church's thesis - that all intuitively computable functions or effective methods are recursive functions.) Recursive function theory studies these functions, their method of generation, ways to prove that some functions are not recursive in this sense, and related matters.

[Glossary of First-Order Logic]

<2001-03-16>

Try this search on OneLook / Google


Nearby terms: recursive « recursive definition « recursive function « recursive function theory » recursive set » recursive type » reductio ad absurdum