Jump to content

Cylindric numbering

From Wikipedia, the free encyclopedia

In computability theory a cylindric numbering is a special kind of numbering first introduced by Yuri L. Ershov in 1973.

If a numbering is reducible to then there exists a computable function with . Usually is not injective, but if is a cylindric numbering we can always find an injective .

Definition

[edit]

A numbering is called cylindric if

That is if it is one-equivalent to its cylindrification

A set is called cylindric if its indicator function

is a cylindric numbering.

Examples

[edit]

Properties

[edit]
  • Cylindric numberings are idempotent:

References

[edit]
  • Yu. L. Ershov, "Theorie der Numerierungen I." Zeitschrift für mathematische Logik und Grundlagen der Mathematik 19, 289-388 (1973).