Cilindrificación

En la teoría de la computabilidad, una cilindrificación es una construcción que asocia una numeración cilíndrica a cada numeración . El concepto fue introducido por primera vez por Yuri L. Ershov en 1973.

Dado un número${\displaystyle \nu }$, la cilindrificación${\displaystyle c(\nu )}$se define como

${\displaystyle \mathrm {Dominio} (c(\nu )):=\{\langle n,k\rangle |n\in \mathrm {Dominio} (\nu )\}}$

${\displaystyle c(\nu )\langle n,k\rangle$ :=\nu (n)}

dónde${\displaystyle \langle n,k\rangle }$es la función de emparejamiento de Cantor .

Tenga en cuenta que la operación de cilindrificación aumenta la aridad de entrada en 1.

• Dados dos números${\displaystyle \nu }$y${\displaystyle \mu }$entonces${\displaystyle \nu \leq \mu \Leftrightarrow c(\nu )\leq _{1}c(\mu )}$
• ${\displaystyle \nu \leq _{1}c(\nu )}$

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