Cylindric numbering
This article needs additional citations for verification. (October 2010) |
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]
- Every Gödel numbering is cylindric
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).