Definition:Basic Primitive Recursive Function

From ProofWiki
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

  1. 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.