About: Primitive recursive function

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

About: Primitive recursive function Goto Sponge NotDistinct Permalink

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

In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The set of primitive recursive functions is known as PR in computational complexity theory.

Attributes	Values
rdf:type	software
rdfs:label	Primitive recursive function (en)
rdfs:comment	In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The set of primitive recursive functions is known as PR in computational complexity theory. (en)
sameAs	Primitive recursive function Primitive recursive function
dbp:wikiPageUsesTemplate	dbt:= dbt:Block_indent dbt:Cite_journal dbt:Cleanup dbt:Cn dbt:Expert_needed dbt:Math dbt:Mvar dbt:Ordered_list dbt:Reflist dbt:Sfn dbt:Short_description dbt:Slink dbt:Isbn dbt:Unordered_list dbt:Su dbt:Mathematical_logic
Subject	Computability theory Recursion Theory of computation Functions and mappings
gold:hypernym	Functions
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Primitive_recursive_function?oldid=1073885778&ns=0
Wikipage page ID	24829 (xsd:integer)
page length (characters) of wiki page	39232 (xsd:nonNegativeInteger)
Wikipage revision ID	1073885778 (xsd:integer)
has abstract	In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The importance of primitive recursive functions lies on the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive. For example, addition and division, the factorial and exponential function, and the function which returns the nth prime are all primitive recursive. In fact, for showing that a computable function is primitive recursive, it suffices to show that its time complexity is bounded above by a primitive recursive function of the input size. It is hence not that easy to devise a computable function that is not primitive recursive; some examples are shown in section below. The set of primitive recursive functions is known as PR in computational complexity theory. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Primitive_recursive_function
is Wikipage redirect of	Primitive recursive Primitive recursive functions Primitive recursion Primitive recursive fuctions
is Link from a Wikipage to another Wikipage of	List of terms relating to algorithms and data structures List of types of functions Machine that always halts Ackermann function Algorithm characterizations Andrzej Grzegorczyk Apomorphism Arithmetical hierarchy Automated theorem proving BIT predicate Bar recursion BlooP and FlooP Monus Bounded quantifier Brouwer–Hilbert controversy Cannon–Thurston map General recursive function Gentzen's consistency proof Double recursion Kruskal's tree theorem Mutual recursion Channel system (computer science) Hyperoperation List of mathematical functions List of mathematical logic topics List of mathematical proofs Computability Computability theory Computable function Computable real function Computably enumerable Constructive set theory Corecursion Counter-machine model Counter machine Course-of-values recursion ELEMENTARY History of the Church–Turing thesis Choice sequence Craig's theorem Function (mathematics) Composition operator Gabriel Sudan Index of computing articles Indicator function Diagonal lemma Fast-growing hierarchy Grzegorczyk hierarchy Gödel's incompleteness theorems Gödel's β function Gödel numbering Gödel numbering for sequences Hales–Jewett theorem Halting problem Integer-valued function LOOP (programming language) Kleene's T predicate Knuth's up-arrow notation Loop variant Menachem Magidor László Kalmár Mathematical logic McCarthy Formalism

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, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software