In computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. They are defined using recursion and composition as central operations and are a strict subset of the recursive functions, which are exactly the computable functions. The broader class of recursive functions are defined by additionally allowing partial functions and introducing an unbounded search operator. Computability theory is that part of the theory of computation dealing with which problems are solvable by algorithms (equivalently, by Turing machines), with various restrictions and extensions. ... A Sierpinski triangle —a confined recursion of triangles to form a geometric lattice. ... In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. Every set is a subset of itself. ... In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are computable in some intuitive sense. ... In computability theory computable functions or Turing computable functions are the basic objects of study. ... This article needs to be cleaned up to conform to a higher standard of quality. ...

Many of the functions normally studied in number theory, and approximations to real-valued functions, are primitive recursive, such as addition, division, factorial, exponential, finding the nth prime, and so on (Brainerd and Landweber, 1974). In fact, it is difficult to devise a function that is not primitive recursive, although some are known (see e.g. Ackermann function). Thus, by studying them, we can discover properties that have wide-reaching consequences. This article needs to be cleaned up to conform to a higher standard of quality. ... 3 + 2 with apples Addition is the most basic operation of arithmetic. ... In mathematics, especially in elementary arithmetic, division is an arithmetic operation which is the inverse of multiplication, and sometimes it can be interpreted as repeated subtraction. ... In mathematics, the factorial of a natural number n is the product of all positive integers less than and equal to n. ... The term exponential may refer to any of several topics in mathematics: Exponential distribution Exponential function Exponential growth, exponential decay Exponential time Matrix exponential Exponential map (in differential geometry) All relate in some fashion to exponents. ... In the theory of computation, the Ackermann function or Ackermann-Peter function is a simple example of a recursive function that is not primitively recursive. ...

Primitive recursive functions can be computed by machines that always halt, while recursive functions require Turing-complete systems. In computability theory, a machine that always halts — also called a decider (Sipser, 1996) — is any abstract machine or model of computation that, contrary to the most general Turing machines, is guaranteed to halt for any particular description and input (see halting problem). ... In computability theory a programming language or an abstract machine is called Turing-complete, Turing-equivalent, or (computationally) universal if it has a computational power equivalent to a universal Turing machine (a simplified model of a programmable computer). ...

The set of primitive recursive functions is known as PR in complexity theory. PR is the complexity class of all primitive recursive functions – or, equivalently, the set of all formal languages that can be decided by such a function. ... Complexity theory can refer to more than one thing: Computational complexity theory: a field in theoretical computer science and mathematics dealing with the resources required during computation to solve a given problem Systems theory (or systemics or general systems theory): an interdisciplinary field including engineering, biology and philosophy that incorporates...

Definition

Primitive recursive functions take natural numbers or tuples of natural numbers as arguments and produce a natural number. A function which takes n arguments is called n-ary. The basic primitive recursive functions are given by these axioms: Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... In mathematics, a tuple is a finite sequence of objects, that is, a list of a limited number of objects (an infinite sequence is a family). ... In mathematics and computer programming the arity of a function or an operator is the number of arguments or operands it takes (arity is sometimes referred to as valency, although that actually refers to another meaning of valency in mathematics). ... In epistemology, an axiom is a self-evident truth upon which other knowledge must rest, from which other knowledge is built up. ...

1. The constant function 0 is primitive recursive.
2. The successor function S, which takes one argument and returns the succeeding number as given by the Peano postulates, is primitive recursive.
3. The projection functions P_iⁿ, which take n arguments and return their ith argument, are primitive recursive.

More complex primitive recursive functions can be obtained by applying the operators given by these axioms: In mathematics and the mathematical sciences, a constant is a fixed, but possibly unspecified, value. ... In mathematics, the Peano axioms (or Peano postulates) are a set of first-order axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order arithmetic). ... In mathematics, an operator is some kind of function; if it comes with a specified type of operand as function domain, it is no more than another way of talking of functions of a given type. ...

1. Composition: Given f, a k-ary primitive recursive function, and k l-ary primitive recursive functions g₀,...,g_k-1, the composition of f with g₀,...,g_k-1, i.e. the function h(x₀,...,x_l-1) = f(g₀(x₀,...,x_l-1),...,g_k-1(x₀,...,x_l-1)), is primitive recursive.
2. Primitive recursion: Given f, a k-ary primitive recursive function, and g, a (k+2)-ary primitive recursive function, the (k+1)-ary function defined as the primitive recursion of f and g, i.e. the function h where h(0,x₀,...,x_k-1) = f(x₀,...,x_k-1) and h(S(n),x₀,...,x_k-1) = g(h(n,x₀,...,x_k-1),n,x₀,...,x_k-1), is primitive recursive.

The projection functions allow us to get around the apparent rigidity in terms of the arity of the functions above, as via composition we can pass any subset of the arguments. In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ... In mathematics and computer programming the arity of a function or an operator is the number of arguments or operands it takes (arity is sometimes referred to as valency, although that actually refers to another meaning of valency in mathematics). ...

It follows from the axioms that a function is primitive recursive if it is one of the basic functions above or if it can be obtained from the basic functions by applying the operators a finite number of times.

Examples

Addition

Intuitively we would like to define addition recursively as: 3 + 2 with apples Addition is the most basic operation of arithmetic. ...

add(0,x)=x

add(n+1,x)=add(n,x)+1

In order to fit this into a strict primitive recursive definition, we define:

add(0,x)=P₁¹(x)

add(S(n),x)=S(P₁³(add(n,x),n,x))

(Note: here P₁³ is a function, which takes 3 arguments and returns the first one.)

P₁¹ is simply the identity function; its inclusion is required by the definition of the primitive recursion operator above; it plays the role of f. The composition of S and P₁³, which is primitive recursive, plays the role of g. An identity function f is a function which doesnt have any effect: it always returns the same value that was used as its argument. ...

Subtraction

We can define limited subtraction, i.e. subtraction that bottoms out at 0 (since we have no concept of negative numbers yet). First we must define the "predecessor" function, which acts as the opposite of the successor function. 5 - 2 = 3 Subtraction is one of the four basic arithmetic operations; it is essentially the opposite of addition. ...

Intuitively we would like to define predecessor as:

pred(0)=0

pred(n+1)=n

To fit this in to a formal primitive recursive definition, we write:

pred(0)=0

pred(S(n))=P₂²(pred(n),n)

Now we can define subtraction in a very similar way to how we defined addition.

sub(0,x)=P₁¹(x)

sub(S(n),x)=pred(P₁³(sub(n,x),n,x))

For the sake of simplicity, the order of the arguments has been switched from the "standard" definition to fit the requirements of primitive recursion, i.e. sub(a,b) corresponds to b-a. This could easily be rectified using composition with suitable projections.

Many other familiar functions can be shown to be primitive recursive; some examples include conditionals, exponentiation, primality testing, and mathematical induction, and the primitive recursive functions can be extended to operate on other objects such as integers and rational numbers. In logical calculus of mathematics, the logical conditional (also known as the material implication, sometimes material conditional) is a binary logical operator connecting two statements, if p then q where p is a hypothesis (or antecedent) and q is a conclusion (or consequent). ... In mathematics, exponentiation is a process generalized from repeated (or iterated) multiplication, in much the same way that multiplication is a process generalized from repeated addition. ... A primality test is an algorithm for determining whether an input number is prime. ... Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers, or otherwise is true of all members of an infinite sequence. ...

Limitations

Primitive recursive functions tend to correspond very closely with our intuition of what a computable function must be. Certainly the initial set of functions are intuitively computable (in their very simplicity), and the two operations by which one can create new primitive recursive functions are also very straightforward. However the set of primitive recursive functions does not include every possible computable function — this can be seen with a variant of Cantor's diagonal argument. This argument provides a computable function which is not primitive recursive. A sketch of the proof is as follows: Cantors diagonal argument is a proof devised by Georg Cantor to demonstrate that the real numbers are not countably infinite. ...

The primitive recursive functions can be computably numerated. This numbering is unique on the definitions of functions, though not unique on the actual functions themselves (as every function can have an infinite number of definitions — consider simply composing by the identity function). The numbering is computable in the sense that it can be defined under formal models of computability such as recursive functions or Turing machines; but an appeal to the Church-Turing thesis is likely sufficient. In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if There is an algorithm that, when given an input â€” typically an integer or a tuple of integers or a sequence of characters â€” eventually halts if it... An identity function f is a function which doesnt have any effect: it always returns the same value that was used as its argument. ... In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are computable in some intuitive sense. ... An artistic representation of a Turing Machine . ... In computability theory the Church-Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. ...

Now consider a matrix where the rows are the primitive recursive functions of one argument under this numbering, and the columns are the natural numbers. Then each element (i, j) corresponds to the ith unary primitive recursive function being calculated on the number j. We can write this as f_i(j).

Now consider the function g(x) = S(f_x(x)). g lies on the diagonal of this matrix and simply adds one to the value it finds. This function is computable (by the above), but clearly no primitive recursive function exists which computes it as it differs from each possible primitive recursive function by at least one value. Thus there must be computable functions which are not primitive recursive.

This argument can be applied to any class of computable (total) functions that can be enumerated in this way. Therefore, any such explicit list of computable (total) functions can never be complete, such as those functions computed by a machine that always halts. Note however that the partial computable functions (those which need not be defined for all arguments) can be explicitly enumerated, for instance by enumerating Turing machine encodings. In computability theory, a machine that always halts — also called a decider (Sipser, 1996) — is any abstract machine or model of computation that, contrary to the most general Turing machines, is guaranteed to halt for any particular description and input (see halting problem). ... An artistic representation of a Turing Machine . ...

One can also explicitly exhibit a simple 1-ary computable function which is recursively defined for any natural number, but which is not primitive recursive, see Ackermann function. In the theory of computation, the Ackermann function or Ackermann-Peter function is a simple example of a recursive function that is not primitively recursive. ...

Bibliography

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0471095850

See also

• Machines that always halt