About: General recursive function

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: General recursive function Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

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

Attributes	Values
rdf:type	Thing
rdfs:label	General recursive function (en)
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 (en)
dbp:wikiPageUsesTemplate	dbt:Authority_control dbt:Blockquote dbt:Cite_book dbt:Cite_journal dbt:Example_needed dbt:Expand_section dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Rp dbt:Sfn dbt:Short_description dbt:Unordered_list dbt:Su dbt:Mset
Subject	Computability theory Theory of computation
Link from a Wikipa... related subject.	dbpedia-ru:Рекурсивная_функция_(теория_вычислимости)
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/General_recursive_function?oldid=1072785618&ns=0
Wikipage page ID	26469 (xsd:integer)
page length (characters) of wiki page	17697 (xsd:nonNegativeInteger)
Wikipage revision ID	1072785618 (xsd:integer)
Link from a Wikipage to another Wikipage	Machine that always halts Ackermann function Turing machine Universal Turing machine Μ operator Computability theory Theory of computation Journal of Symbolic Logic Domain of a function Church–Turing thesis Primitive recursive function Computability theory Computable function Algorithmic complexity Computer science Partial function Fibonacci number Halting problem Integer square root Lambda calculus Kleene's T predicate Markov algorithm Marvin Minsky Mathematical logic McCarthy 91 function History of numbers R (complexity) Recursion Recursion (computer science) Register machine
has 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. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/General_recursive_function
is Wikipage redirect of	Μ-recursive function General-recursive General recursive Total recursive function Mu-recursive Mu recursive function Recursive function (computability) Recursive function theory M-recursive function Mu-recursive function Μ-recursive Μ recursion Partial recursive function
is Link from a Wikipage to another Wikipage of	Francisco Dória List of terms relating to algorithms and data structures List of types of functions Machine that always halts Non-recursive function Number 1905 in science 1932 in science 1936 in science 1977 in science 20th century in science Algorithm characterizations Andrzej Grzegorczyk Brainfuck Jacques Herbrand Judith Gersting Dieter Rödding Double recursion History of computer science History of mathematics Church–Turing thesis Computability Computability theory Computable function Computable number Computable topology Computational complexity Constructive set theory

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 925 MB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software