Cilindrificación

Concepto en teoría de la computabilidad, un campo de las matemáticas.

En teoría de 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.

Definición

Dada una numeración , la cilindrificación se define como ${\displaystyle \nu }$ ${\displaystyle c(\nu )}$

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

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

¿Dónde está la función de emparejamiento de Cantor ? ${\displaystyle \langle n,k\rangle }$

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

Propiedades

• Dadas dos numeraciones y luego ${\displaystyle \nu }$ ${\displaystyle \mu }$ ${\displaystyle \nu \leq \mu \Leftrightarrow c(\nu )\leq _{1}c(\mu )}$
• ${\displaystyle \nu \leq _{1}c(\nu )}$

Referencias

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