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 numberings ν is reducible to μ then there exists a computable function f with 
. Usually f is not injective but if μ is a cylindric numbering we can always find an injective f.
Contents |
[edit] Definition
A numbering ν is called cylindric if
That is if it is one equivalent to its cylindrification
A set S is called cylindric if its indicator function
is a cylindric numbering.
[edit] Examples
- every Gödel numbering is cylindric
[edit] Properties
- cylindric numberings are idempotent,
[edit] References
- Yu. L. Ershov, "Theorie der Numerierungen I." Zeitschrift für mathematische Logik und Grundlagen der Mathematik 19, 289-388 (1973).
