General recursive function

In mathematical logic and computer science, general recursive function AKA partial recursive function AKA μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense.

If total, these functions are also called total recursive functions, shortened to recursive functions. total general recursive functions AKA total μ-recursive functions.

(For some authors, the terms recursive and general recursive are synonymous with partial recursive.)

In computability theory, it is shown that the μ-recursive functions are precisely those functions computable by a Turing machine or Lambda calculus (which is a theorem of the Church-Turing thesis).

The μ-recursive functions are closely related to primitive recursive functions, and their inductive definition builds upon the primitive recursive functions; GRF = PRF + μ operator.

However, not every total recursive function is a primitive recursive function-the most famous example is the Ackermann function.

Other equivalent classes of functions are the functions of lambda calculus and the functions that can be computed by Markov algorithms.

The subset of all total recursive functions with values in {0,1} is known in computational complexity theory as the complexity class R.