|
=== Some common primitive recursive functions ===
:The following examples and definitions are from Kleene (1952) pp. 223–231. Many appear with proofs. Most also appear with similar names, either as proofs or as examples, in Boolos-Burgess-Jeffrey 2002 pp. 63–70; they add the logarithm lo(x, y) or lg(x, y) depending on the exact derivation. ▼{{cleanup|section|reason=Remove functions and explanations that appear above|date=November 2021}}
▲:The following examples and definitions are from Kleene (1952) pp. 223–231. Many appear with proofs. Most also appear with similar names, either as proofs or as examples, in Boolos-Burgess-Jeffrey 2002 pp. 63–70; they add the logarithm lo(x, y) or lg(x, y) depending on the exact derivation.
In the following we observe that primitive recursive functions can be of four types:
# ''functions'' for short: "number-theoretic functions" from { 0, 1, 2, ...} to { 0, 1, 2, ...},
# ''predicates'': from { 0, 1, 2, ...} to truth values { t =true, f =false },
# ''propositional connectives'': from truth values { t, f } to truth values { t, f },
# ''representing functions'': from truth values { t, f } to { 0, 1, 2, ... }. Many times a predicate requires a representing function to convert the predicate's output { t, f } to { 0, 1 } (note the order "t" to "0" and "f" to "1" matches with ~sg( ) defined below). By definition a function φ('''x''') is a "representing function" of the predicate P('''x''') if φ takes only values 0 and 1 and produces ''0'' when P is true".
In the following the mark " ' ", e.g. a', is the primitive mark meaning "the successor of", usually thought of as " +1", e.g. a +1 =<sub>def</sub> a'. The functions 16–20 and #G are of particular interest with respect to converting primitive recursive predicates to, and extracting them from, their "arithmetical" form expressed as [[Gödel number]]s.
|
