Numbering (computability theory)
In computability theory a numbering is the assignment of natural numbers to a set of objects such as functions, rational numbers, graphs, or words in some formal language. A numbering can be used to transfer the idea of computability[1] and related concepts, which are originally defined on the natural numbers using computable functions, to these different types of objects.
Common examples of numberings include Gödel numberings in first-order logic, the description numbers that arise from universal Turing machines and admissible numberings of the set of partial computable functions.
Definition and examples
A numbering of a set [math]\displaystyle{ S }[/math] is a surjective partial function from [math]\displaystyle{ \mathbb{N} }[/math] to S (Ershov 1999:477). The value of a numbering ν at a number i (if defined) is often written νi instead of the usual [math]\displaystyle{ \nu(i) \! }[/math].
Examples of numberings include:
- The set of all finite subsets of [math]\displaystyle{ \mathbb{N} }[/math] has a numbering [math]\displaystyle{ \gamma }[/math] , defined so that [math]\displaystyle{ \gamma(0) = \emptyset }[/math] and so that, for each finite nonempty set [math]\displaystyle{ A = \{a_0, \ldots, a_k\} }[/math], [math]\displaystyle{ \gamma(n_A) = A }[/math] where [math]\displaystyle{ n_A = \sum_{i \leq k} 2^{a_i} }[/math] (Ershov 1999:477). This numbering is a (partial) bijection.
- A fixed Gödel numbering [math]\displaystyle{ \varphi_i }[/math] 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.
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 [math]\displaystyle{ \{ (x,y) : \eta(x) = \eta(y)\} }[/math] 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 [math]\displaystyle{ \nu_1: \mathbb{N} \rightharpoonup S }[/math] and [math]\displaystyle{ \nu_2: \mathbb{N} \rightharpoonup S }[/math] be two numberings. Then [math]\displaystyle{ \nu_1 }[/math] is reducible to [math]\displaystyle{ \nu_2 }[/math], written [math]\displaystyle{ \nu_1 \le \nu_2 }[/math], if
- [math]\displaystyle{ \exists f \in \mathbf{P}^{(1)} \, \forall i \in \mathrm{Domain}(\nu_1) : \nu_1(i) = \nu_2 \circ f(i). }[/math]
If [math]\displaystyle{ \nu_1 \le \nu_2 }[/math] and [math]\displaystyle{ \nu_1 \ge \nu_2 }[/math] then [math]\displaystyle{ \nu_1 }[/math] is equivalent to [math]\displaystyle{ \nu_2 }[/math]; this is written [math]\displaystyle{ \nu_1 \equiv \nu_2 }[/math].
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 [math]\displaystyle{ \mathbb{N} }[/math] 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.
See also
References
- 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.
 |  |
