go-v.orgcodex
Menu
Page tools

codex · Philosophy

General recursive function

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). In computability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines (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} (that is, solving decision problems) is known in computational complexity theory as the complexity class R.

Wikipedia contributors, "General recursive function", Wikipedia, revision 1382206144, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex