Cylindric numbering

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

If a numbering ${\displaystyle \nu }${\displaystyle \nu } is reducible to ${\displaystyle \mu }${\displaystyle \mu } then there exists a computable function ${\displaystyle f}${\displaystyle f} with ${\displaystyle \nu =\mu \circ f}${\displaystyle \nu =\mu \circ f}. Usually ${\displaystyle f}${\displaystyle f} is not injective, but if ${\displaystyle \mu }${\displaystyle \mu } is a cylindric numbering we can always find an injective ${\displaystyle f}${\displaystyle f}.

A numbering ${\displaystyle \nu }${\displaystyle \nu } is called cylindric if

${\displaystyle \nu \equiv _{1}c(\nu ).}${\displaystyle \nu \equiv _{1}c(\nu ).}

That is if it is one-equivalent to its cylindrification

A set ${\displaystyle S}${\displaystyle S} is called cylindric if its indicator function

${\displaystyle 1_{S}:\mathbb {N} \to \{0,1\}}${\displaystyle 1_{S}:\mathbb {N} \to \{0,1\}}

is a cylindric numbering.

• Every Gödel numbering is cylindric

• Cylindric numberings are idempotent: ${\displaystyle \nu \circ \nu =\nu }${\displaystyle \nu \circ \nu =\nu }

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

• Theory of computation

• Articles with short description
• Short description with empty Wikidata description
• Articles needing additional references from October 2010
• All articles needing additional references