PR is the complexity class of all
primitive recursive function
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 ...
s—or, equivalently, the set of all
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sy ...
s that can be decided in
time
Time is the continued sequence of existence and events that occurs in an apparently irreversible succession from the past, through the present, into the future. It is a component quantity of various measurements used to sequence events, ...
bounded by such a function. This includes
addition,
multiplication,
exponentiation
Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to r ...
,
tetration
In mathematics, tetration (or hyper-4) is an operation based on iterated, or repeated, exponentiation. There is no standard notation for tetration, though \uparrow \uparrow and the left-exponent ''xb'' are common.
Under the definition as rep ...
, etc.
The
Ackermann function is an example of a function that is ''not'' primitive recursive, showing that PR is strictly contained in
R (Cooper 2004:88).
On the other hand, we can "enumerate" any
recursively enumerable set
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that th ...
(see also its complexity class
RE) by a primitive-recursive function in the following sense: given an input (''M'', ''k''), where ''M'' is a
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
and ''k'' is an integer, if ''M'' halts within ''k'' steps then output ''M''; otherwise output nothing. Then the union of the outputs, over all possible inputs (''M'', ''k''), is exactly the set of ''M'' that halt.
PR strictly contains
ELEMENTARY
Elementary may refer to:
Arts, entertainment, and media Music
* ''Elementary'' (Cindy Morgan album), 2001
* ''Elementary'' (The End album), 2007
* ''Elementary'', a Melvin "Wah-Wah Watson" Ragin album, 1977
Other uses in arts, entertainment, a ...
.
PR does not contain "PR-complete" problems (assuming, e.g.,
reductions that belong to ELEMENTARY). In practice, many problems that are not in PR but just beyond are
-complete (Schmitz 2016).
References
*
*
*
External links
* .
{{DEFAULTSORT:Pr (Complexity)
Complexity classes