Global Information Lookup Global Information

General recursive function information


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.

  1. ^ "Recursive Functions". The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. 2021.
  2. ^ 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."
  3. ^ Kleene, Stephen C. (1936). "λ-definability and recursiveness". Duke Mathematical Journal. 2 (2): 340–352. doi:10.1215/s0012-7094-36-00227-2.
  4. ^ 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 21 Related for: General recursive function information

Request time (Page generated in 0.8529 seconds.)

General recursive function

Last Update:

and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to...

Word Count : 2748

Primitive recursive function

Last Update:

Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The importance of primitive recursive functions...

Word Count : 6722

Recursive function

Last Update:

Recursive function may refer to: Recursive function (programming), a function which references itself General recursive function, a computable partial...

Word Count : 94

Partial function

Last Update:

analysis, a partial function is generally called simply a function. In computability theory, a general recursive function is a partial function from the integers...

Word Count : 2041

Ackermann function

Last Update:

recursive. All primitive recursive functions are total and computable, but the Ackermann function illustrates that not all total computable functions...

Word Count : 6780

Computable function

Last Update:

functions and the general recursive functions. According to the Church–Turing thesis, computable functions are exactly the functions that can be calculated...

Word Count : 3393

Tail call

Last Update:

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...

Word Count : 4209

Recursion

Last Update:

and recursive rule, one can generate the set of all natural numbers. Other recursively defined mathematical objects include factorials, functions (e.g...

Word Count : 3644

Recursive definition

Last Update:

the general recursive 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...

Word Count : 1584

ELEMENTARY

Last Update:

complexity theory, the complexity class ELEMENTARY of elementary recursive functions is the union of the classes E L E M E N T A R Y = ⋃ k ∈ N k - E X...

Word Count : 1112

MU

Last Update:

operator (M operator), a function-building operator for General recursive function Möbius function, a multiplicative function in number theory and combinatorics...

Word Count : 1094

Computable set

Last Update:

computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input,...

Word Count : 586

Computability theory

Last Update:

while according to Robert I. Soare it is a total recursive (equivalently, general recursive) function. This article follows the second of these conventions...

Word Count : 6432

Tetration

Last Update:

^{2}} ) is not an elementary recursive function. One can prove by induction that for every elementary recursive function f, there is a constant c such...

Word Count : 6000

Effective method

Last Update:

effective calculability led to a variety of proposed definitions (general recursive functions, Turing machines, λ-calculus) that later were shown to be equivalent...

Word Count : 448

Memoization

Last Update:

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...

Word Count : 3744

Recursive Bayesian estimation

Last Update:

probabilistic approach for estimating an unknown probability density function (PDF) recursively over time using incoming measurements and a mathematical process...

Word Count : 1155

Mutual recursion

Last Update:

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...

Word Count : 2013

Hierarchical and recursive queries in SQL

Last Update:

general recursive fixpoint queries, which compute transitive closures. In standard SQL:1999 hierarchical queries are implemented by way of recursive common...

Word Count : 1346

Recursive neural network

Last Update:

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...

Word Count : 954

Recursive descent parser

Last Update:

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...

Word Count : 1067

PDF Search Engine © AllGlobal.net