Numbering (computability Theory) - Computable Numberings

Computable Numberings

When the objects of the set S 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) = "(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 r.e. subsets of 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.