This HTML5 document contains 59 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n9http://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:General_recursive_function
rdf:type
owl:Thing
rdfs:label
General recursive function
rdfs:comment
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
dbp:wikiPageUsesTemplate
dbt:Refbegin dbt:Cite_journal dbt:Refend dbt:Reflist dbt:Rp dbt:Math dbt:Mset dbt:Blockquote dbt:Example_needed dbt:Short_description dbt:Mvar dbt:Su dbt:Expand_section dbt:Unordered_list dbt:Authority_control dbt:Sfn dbt:Cite_book
dct:subject
dbc:Computability_theory dbc:Theory_of_computation
dbo:wikiPageInterLanguageLink
dbpedia-ru:Рекурсивная_функция_(теория_вычислимости)
prov:wasDerivedFrom
n9:General_recursive_function?oldid=1072785618&ns=0
dbo:wikiPageID
26469
dbo:wikiPageLength
17697
dbo:wikiPageRevisionID
1072785618
dbo:wikiPageWikiLink
dbr:Lambda_calculus dbr:Machine_that_always_halts dbr:Computer_science dbr:Μ_operator dbr:Kleene's_T_predicate dbr:Ackermann_function dbr:Markov_algorithm dbc:Theory_of_computation dbr:Computable_function dbr:Computational_complexity_theory dbr:Marvin_Minsky dbr:Computability_theory dbr:Mathematical_logic dbr:Universal_Turing_machine dbr:Partial_function dbr:Natural_number dbr:Domain_of_a_function dbr:Register_machine dbr:Church–Turing_thesis dbr:Halting_problem dbc:Computability_theory dbr:Integer_square_root dbr:R_(complexity) dbr:McCarthy_91_function dbr:Journal_of_Symbolic_Logic dbr:Recursion dbr:Recursion_(computer_science) dbr:Primitive_recursive_function dbr:Fibonacci_number dbr:Turing_machine
dbo:abstract
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} is known in computational complexity theory as the complexity class R.
foaf:isPrimaryTopicOf
n9:General_recursive_function