Cylindric numbering
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 with . Usually is not injective but if is a cylindric numbering we can always find an injective .
Definition
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
- every Gödel numbering is cylindric
Properties
- cylindric numberings are idempotent,
gollark: Actually, I can also pay in shattered dreams, extremely small amounts of computer time, and 0.1 banano.
gollark: Er, it's Saturday.
gollark: Well, we actually only pay in melons right now, and only melons in computer games because real melons are a hassle to transport.
gollark: But you would work for osmarks.tk™ corporation™™?
gollark: ... but you wouldn't work for a company?
References
- Yu. L. Ershov, "Theorie der Numerierungen I." Zeitschrift für mathematische Logik und Grundlagen der Mathematik 19, 289-388 (1973).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.