In computability theory complete numberings are generalizations of Gödel numbering first introduced by A.I. Mal'tsev in 1963. They are studied because several important results like the Kleene's recursion theorem and Rice's theorem, which were originally proven for the Gödel-numbered set of computable functions, still hold for arbitrary sets with complete numberings.

Definition

A numbering is called complete) if for every partial computable function there exists a total computable function so that (Ershov1999:482):

Ershov refers to the element a is called precomplete if the weaker property holds:

Examples

• Any numbering of a singleton set is complete

• The identity function on the natural numbers is not complete

• A Gödel numbering is precomplete

References

• Y.L. Ershov (1999), "Theory of numberings", Handbook of Computability Theory, E.R. Griffor (ed.), Elsevier, pp.473506.

• A.I. Mal'tsev, Sets with complete numberings. Algebra i Logika, 1963, vol. 2, no. 2, 4-29 (Russian)