General recursive function

A function on natural numbers generated from initial functions by composition, primitive recursion, and unbounded minimization. These functions coincide with the partial computable functions.

Initial functions: The zero, successor, and projection functions used to generate recursive-function classes. They form the starting basis for the general recursive functions.
Least number operator: An operator that returns the least number satisfying a specified condition, when one exists. General recursion uses least-number search to define values through minimization.
Primitive recursive function: A total function generated from initial functions using composition and primitive recursion alone. It omits minimization and therefore excludes some total computable functions.
Jacques Herbrand: A French logician whose work helped establish the theory of recursive functions. His ideas contributed to the formal foundations later developed as general recursion.
Composition (computability): The operation that builds a function by feeding outputs of functions into another function. Composition combines functions already generated by the defining rules.
Halting problem: The problem of deciding whether an arbitrary program eventually stops on a given input. A minimization search may fail to terminate, reflecting undecidable halting behavior.
Total computable function: A function defined for every input and computed by an algorithm that always halts. General recursive definitions may be partial, although their total members are exactly total computable functions.
Kurt Gödel: An Austrian logician whose work transformed mathematical logic and the foundations of mathematics. Gödel developed recursive-function methods in the formal analysis of arithmetic.
Primitive recursion: A scheme defining functions through a base case and repeated recursion on a natural-number argument. It is one of the two central closure operations in the definition.
Kleene normal form theorem: A theorem expressing partial recursive functions through a universal computation predicate and minimization. It gives a precise normal form for computations represented by general recursive functions.

Linked from 1 page