Цилиндрификация - Cylindrification

В теория вычислимости а цилиндрификация конструкция, которая связывает цилиндрическая нумерация для каждого нумерация. Концепция была впервые представлена Юрий Львович Ершов в 1973 г.

Определение

Учитывая нумерацию ${\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 (i)}$

куда ${\displaystyle \langle n,k\rangle }$ это Функция сопряжения Кантора Операция цилиндрификации принимает отношение на входе арности k и выводит отношение арности k + 1 следующим образом: Для отношения R арности K его цилиндрификация, обозначенная как c (R), представляет собой следующее множество {(a1 ,. .., ak, a) | (a1, ..., ak) принадлежит R, а a принадлежит A}. Обратите внимание, что операция цилиндрификации увеличивает арность входа на 1.

Характеристики

• Учитывая две нумерации ${\displaystyle \nu }$ и ${\displaystyle \mu }$ тогда ${\displaystyle \nu \leq \mu \Leftrightarrow c(\nu )\leq _{1}c(\mu )}$
• ${\displaystyle \nu \leq _{1}c(\nu )}$

Рекомендации

• Ю. Л. Ершов, "Theorie der Numerierungen I." Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 19, 289-388 (1973).