In computability theory a cylindrification is a construction that associates a cylindric numbering to each numbering. The concept was first introduced by Yuri L. Ershov in 1973.

Definition

edit

Given a numbering  , the cylindrification   is defined as

 
 

where   is the Cantor pairing function.

Note that the cylindrification operation increases the input arity by 1.

Properties

edit
  • Given two numberings   and   then  
  •  

References

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