In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as in a formal one. If the function is total, it is also called a total recursive function (sometimes shortened to recursive function).[1] In computability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines[2][4] (this is one of the theorems that supports the Church–Turing thesis). The μ-recursive functions are closely related to primitive recursive functions, and their inductive definition (below) builds upon that of the primitive recursive functions. 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.
- ^ "Recursive Functions". The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. 2021.
- ^ Stanford Encyclopedia of Philosophy, Entry Recursive Functions, Sect.1.7: "[The class of μ-recursive functions] turns out to coincide with the class of the Turing-computable functions introduced by Alan Turing as well as with the class of the λ-definable functions introduced by Alonzo Church."
- ^ Kleene, Stephen C. (1936). "λ-definability and recursiveness". Duke Mathematical Journal. 2 (2): 340–352. doi:10.1215/s0012-7094-36-00227-2.
- ^ Turing, Alan Mathison (Dec 1937). "Computability and λ-Definability". Journal of Symbolic Logic. 2 (4): 153–163. doi:10.2307/2268280. JSTOR 2268280. S2CID 2317046. Proof outline on p.153: [3]
