General recursive function

In <a href="/facts/Mathematical_logic/SaI7Y3wN">mathematical logic</a> and <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a general recursive function, partial recursive function, or μ-recursive function is a <a href="/facts/Partial_function/0vJMw0Nm">partial function</a> from <a href="/facts/Natural_number/u65og8JE">natural numbers</a> to natural numbers that is "computable" in an intuitive sense – as well as in a <a href="/facts/Computable_function/dzwBlLGn">formal one</a>. If the function is total, it is also called a total recursive function (sometimes shortened to recursive function). In <a href="/facts/Computability_theory_(computation)/cqDfXwdf">computability theory</a>, it is shown that the μ-recursive functions are precisely the functions that can be computed by <a href="/facts/Turing_machine/ojCtglYu">Turing machines</a> (this is one of the theorems that supports the <a href="/facts/Church%25E2%2580%2593Turing_thesis/hDHn641f">Church–Turing thesis</a>). The μ-recursive functions are closely related to <a href="/facts/Primitive_recursive_function/4z97gRnl">primitive recursive functions</a>, 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 <a href="/facts/Ackermann_function/WQNpCWHn">Ackermann function</a>.
Other equivalent classes of functions are the functions of <a href="/facts/Lambda_calculus/DaD3RuQ4">lambda calculus</a> and the functions that can be computed by <a href="/facts/Markov_algorithm/3WMjt2As">Markov algorithms</a>.
The subset of all total recursive functions with values in {0,1} is known in <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> as the <a href="/facts/R_(complexity)/RRLVW00j">complexity class R</a>.

General recursive function open-in-new

General recursive function