numbering (computability theory)

A numbering of a set $S$ is a surjective partial function from $\backslash mathbb\{N\}$ to S (Ershov 1999:477). The value of a numbering ν at a number i (if defined) is often written ν_i instead of the usual $\backslash nu(i)\; \backslash !$.

Examples of numberings include:

• The set of all finite subsets of $\backslash mathbb\{N\}$ has a numbering $\backslash gamma$ , defined so that $\backslash gamma(0)\; =\; \backslash emptyset$ and so that, for each finite nonempty set $A\; =\; \backslash \{a\_0,\; \backslash ldots,\; a\_k\backslash \}$, $\backslash gamma(n\_A)\; =\; A$ where $n\_A\; =\; \backslash sum\_\{i\; \backslash leq\; k\}\; 2^\{a\_i\}$ (Ershov 1999:477). This numbering is a (partial) bijection.
• A fixed Gödel numbering $\backslash varphi\_i$ of the computable partial functions can be used to define a numbering W of the recursively enumerable sets, by letting by W(i) be the domain of φ_i. This numbering will be surjective (like all numberings) but not injective: there will be distinct numbers that map to the same recursively enumerable set under W.

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 $\backslash \{\; (x,y)\; :\; \backslash eta(x)\; =\; \backslash eta(y)\backslash \}$ 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.

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

if

:$\backslash exists\; f\; \backslash in\; \backslash mathbf\{P\}^\{(1)\}\; \backslash ,\; \backslash forall\; i\; \backslash in\; \backslash mathrm\{Domain\}(\backslash nu\_1)\; :\; \backslash nu\_1(i)\; =\; \backslash nu\_2\; \backslash circ\; f(i).$

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

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 $\backslash 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.

• Complete numbering
• Cylindrification
• Gödel numbering
• Description number

{{reflist}}

• Y.L. Ershov (1999), "Theory of numberings", Handbook of Computability Theory, Elsevier, pp. 473–506.
• V.A. Uspenskiĭ, A.L. Semenov (1993), Algorithms: Main Ideas and Applications, Springer.

Category:Theory of computation

Category:Computability theory