One of several equivalent definitions of a computable 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).[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]
and 23 Related for: General recursive function information
Primitive recursivefunctions form a strict subset of those generalrecursivefunctions that are also total functions. The importance of primitive recursive functions...
functions and the general recursivefunctions. According to the Church–Turing thesis, computable functions are exactly the functions that can be calculated...
recursive. All primitive recursivefunctions are total and computable, but the Ackermann function illustrates that not all total computable functions...
analysis, a partial function is generally called simply a function. In computability theory, a generalrecursivefunction is a partial function from the integers...
The special case of tail-recursive calls, when a function calls itself, may be more amenable to call elimination than general tail calls. When the language...
the generalrecursive definition will be given below. Let A be a set and let a0 be an element of A. If ρ is a function which assigns to each function f...
operator (M operator), a function-building operator for Generalrecursivefunction Möbius function, a multiplicative function in number theory and combinatorics...
complexity theory, the complexity class ELEMENTARY of elementary recursivefunctions is the union of the classes E L E M E N T A R Y = ⋃ k ∈ N k - E X...
computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input,...
effective calculability led to a variety of proposed definitions (generalrecursivefunctions, Turing machines, λ-calculus) that later were shown to be equivalent...
and recursive rule, one can generate the set of all natural numbers. Other recursively defined mathematical objects include factorials, functions (e.g...
probabilistic approach for estimating an unknown probability density function (PDF) recursively over time using incoming measurements and a mathematical process...
while according to Robert I. Soare it is a total recursive (equivalently, generalrecursive) function. This article follows the second of these conventions...
recursive calls will be made (7 and 6), and the value for 5! will have been stored from the previous call. In this way, memoization allows a function...
A recursive neural network is a kind of deep neural network created by applying the same set of weights recursively over a structured input, to produce...
tail call optimization in general (when the function called is not the same as the original function, as in tail-recursive calls) may be more difficult...
arithmetic propositions involving natural numbers and any primitive recursivefunction, including the operations of addition, multiplication, and exponentiation...
In mathematics, an injective function (also known as injection, or one-to-one function ) is a function f that maps distinct elements of its domain to...
Recursive least squares (RLS) is an adaptive filter algorithm that recursively finds the coefficients that minimize a weighted linear least squares cost...
^{2}} ) is not an elementary recursivefunction. One can prove by induction that for every elementary recursivefunction f, there is a constant c such...
computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where...
Global Information
