Numbering (computability theory)

Types of numberings

A numbering is total if it is a total function. If the domain of a partial numbering is recursively enumerable then there always exists an equivalent total numbering (equivalence of numberings is defined below).

A numbering η is decidable if the set ${\displaystyle \{(x,y):\eta (x)=\eta (y)\}}$ is a decidable set.

A numbering η is single-valued if η(x) = η(y) if and only if x=y; in other words if η is an injective function. A single-valued numbering of the set of partial computable functions is called a Friedberg numbering.

Comparison of numberings

There is a preorder on the set of all numberings. Let ${\displaystyle {\nu }_1:\mathbb{N}\rightharpoonup S}$ and ${\displaystyle {\nu }_2:\mathbb{N}\rightharpoonup S}$ be two numberings. Then ${\displaystyle {\nu }_1}$ is reducible to ${\displaystyle {\nu }_2}$, written ${\displaystyle {\nu }_1\le {\nu }_2}$, if

${\displaystyle \mathrm{\exists }f\in {\mathbf{P}}^{(1)}\mathrm{\forall }i\in \mathrm{D}\mathrm{o}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}({\nu }_1):{\nu }_1(i)={\nu }_2\circ f(i).}$

If ${\displaystyle {\nu }_1\le {\nu }_2}$ and ${\displaystyle {\nu }_1\ge {\nu }_2}$ then ${\displaystyle {\nu }_1}$ is equivalent to ${\displaystyle {\nu }_2}$; this is written ${\displaystyle {\nu }_1\equiv {\nu }_2}$.

Computable numberings

When the objects of the set S being numbered are sufficiently "constructive", it is common to look at numberings that can be effectively decoded (Ershov 1999:486). For example, if S consists of recursively enumerable sets, the numbering η is computable if the set of pairs (x,y) where y ∈ η(x) is recursively enumerable. Similarly, a numbering g of partial functions is computable if the relation R(x,y,z) = "[g(x)](y) = z" is partial recursive (Ershov 1999:487).

A computable numbering is called principal if every computable numbering of the same set is reducible to it. Both the set of all recursively enumerable subsets of ${\displaystyle \mathbb{N}}$ and the set of all partial computable functions have principle numberings (Ershov 1999:487). A principle numbering of the set of partial recursive functions is known as an admissible numbering in the literature.