From Wikipedia, the free encyclopedia

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 of a set is called complete (with respect to an element ) if for every partial computable function there exists a total computable function so that (Ershov 1999:482):

Ershov refers to the element a as a "special" element for the numbering. A numbering is called precomplete if the weaker property holds:

Examples

References

  • Y.L. Ershov (1999), "Theory of numberings", Handbook of Computability Theory, E.R. Griffor (ed.), Elsevier, pp. 473–506. ISBN  978-0-444-89882-1
  • A.I. Mal'tsev, Sets with complete numberings. Algebra i Logika, 1963, vol. 2, no. 2, 4-29 (Russian)
From Wikipedia, the free encyclopedia

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 of a set is called complete (with respect to an element ) if for every partial computable function there exists a total computable function so that (Ershov 1999:482):

Ershov refers to the element a as a "special" element for the numbering. A numbering is called precomplete if the weaker property holds:

Examples

References

  • Y.L. Ershov (1999), "Theory of numberings", Handbook of Computability Theory, E.R. Griffor (ed.), Elsevier, pp. 473–506. ISBN  978-0-444-89882-1
  • A.I. Mal'tsev, Sets with complete numberings. Algebra i Logika, 1963, vol. 2, no. 2, 4-29 (Russian)

Videos

Youtube | Vimeo | Bing

Websites

Google | Yahoo | Bing

Encyclopedia

Google | Yahoo | Bing

Facebook