Editing Primitive recursive function (section)

== Relationship to recursive functions ==

The broader class of [[partial recursive function]]s is defined by introducing an [[mu operator|unbounded search operator]].  The use of this operator may result in a [[partial function]], that is, a relation with ''at most'' one value for each argument, but does not necessarily have ''any'' value for any argument (see [[Domain of a function|domain]]).  An equivalent definition states that a partial recursive function is one that can be computed by a [[Turing machine]].  A total recursive function is a partial recursive function that is defined for every input.

Every primitive recursive function is total recursive, but not all total recursive functions are primitive recursive. The [[Ackermann function]] ''A''(''m'',''n'') is a well-known example of a total recursive function (in fact, provable total), that is not primitive recursive. There is a characterization of the primitive recursive functions as a subset of the total recursive functions using the Ackermann function.  This characterization states that a function is primitive recursive [[if and only if]] there is a natural number ''m'' such that the function can be computed by a Turing [[machine that always halts]] within A(''m'',''n'') or fewer steps, where ''n'' is the sum of the arguments of the primitive recursive function.<ref>This follows from the facts that the functions of this form are the most quickly growing primitive recursive functions, and that a function is primitive recursive if and only if its time complexity is bounded by a primitive recursive function. For the former, see {{citation|title=An Introduction to Formal Languages and Automata|first=Peter|last=Linz|publisher=Jones & Bartlett Publishers|year=2011|isbn=9781449615529|page=332|url=https://books.google.com/books?id=hsxDiWvVdBcC&pg=PA332}}. For the latter, see {{citation|title=The Nature of Computation|first1=Cristopher|last1=Moore|author1-link=Cristopher Moore|first2=Stephan|last2=Mertens|publisher=Oxford University Press|year=2011|isbn=9780191620805|page=287|url=https://books.google.com/books?id=jnGKbpMV8xoC&pg=PA287}}</ref>

An important property of the primitive recursive functions is that they are a [[recursively enumerable]] subset of the set of all [[total recursive function]]s (which is not itself recursively enumerable). This means that there is a single computable function ''f''(''m'',''n'') that enumerates the primitive recursive functions, namely:
* For every primitive recursive function ''g'', there is an ''m'' such that ''g''(''n'') = ''f''(''m'',''n'') for all ''n'', and
* For every ''m'', the function ''h''(''n'') = ''f''(''m'',''n'') is primitive recursive.
''f'' can be explicitly constructed by iteratively repeating all possible ways of creating primitive recursive functions. Thus, it is provably total. One can use a [[diagonal lemma|diagonalization]] argument to show that ''f'' is not recursive primitive in itself: had it been such, so would be ''h''(''n'') = ''f''(''n'',''n'')+1. But if this equals some primitive recursive function, there is an ''m'' such that ''h''(''n'') = ''f''(''m'',''n'') for all ''n'', and then ''h''(''m'') = ''f''(''m'',''m''), leading to contradiction.

However, the set of primitive recursive functions is not the ''largest'' recursively enumerable subset of the set of all total recursive functions. For example, the set of provably total functions (in Peano arithmetic) is also recursively enumerable, as one can enumerate all the proofs of the theory. While all primitive recursive functions are provably total, the converse is not true.