Definition:Basic Primitive Recursive Function
Jump to navigation
Jump to search
Definition
The basic primitive recursive functions are:
Zero Function
The zero function $\Zero: \N \to \N$ is a basic primitive recursive function, defined as:
- $\forall n \in \N: \map \Zero n = 0$
Successor Function
The successor function $\Succ: \N \to \N$ is a basic primitive recursive function, defined as:
- $\forall n \in \N: \map \Succ n = n + 1$
Projection Function
The projection functions $\pr_j^k: \N^k \to \N$ are basic primitive recursive functions, defined as:
- $\forall \tuple {n_1, n_2, \ldots, n_k} \in \N^k: \map {\pr_j^k} {n_1, n_2, \ldots, n_k} = n_j$[1]
where $j \in \closedint 1 k$.
Identity Function
The identity function $I_\N: \N \to \N$ is a basic primitive recursive function, defined as:
- $\forall n \in \N: \map {I_\N} n = n$
Note that this is an implementation of the projection function:
- $\pr_1^1: \N \to \N: \map {\pr_1^1} {n_1} = n_1$
Also see
URM Computability
The basic primitive recursive functions:
are each URM computable by a single-instruction URM program.
Notation
- ↑ The usual notation for the projection function omits the superscript that defines the arity of the particular instance of the projection in question at the time, for example: $\pr_j$. However, in the context of computability theory, it is a very good idea to be completely certain of exactly which projection function is under discussion.