Нумерация (теория вычислимости)

В теории вычислимости нумерация — это присвоение натуральных чисел множеству объектов , таких как функции , рациональные числа , графики или слова на некотором формальном языке . Нумерацию можно использовать для передачи идеи вычислимости. и связанные концепции, которые изначально определены для натуральных чисел с использованием вычислимых функций , для этих различных типов объектов.

Общие примеры нумераций включают нумерацию Гёделя в логике первого порядка , числа описания , возникающие из универсальных машин Тьюринга , и допустимые нумерации множества частично вычислимых функций.

Определение и примеры

Нумерация ​ комплекта $S$ является сюръективной частичной функцией от $\mathbb {N}$ к С (Ершов 1999: 477). Значение нумерации ν в номере i (если оно определено) часто пишется ν _i вместо обычного $\nu (i)\!$.

Примеры нумерации включают в себя:

• Множество всех конечных подмножеств $\mathbb {N}$ имеет нумерацию $\gamma$ , определенный так, что $\gamma (0)=\emptyset$ и так, что для каждого конечного непустого множества $A=\{a_{0},\ldots ,a_{k}\}$, $\gamma (n_{A})=A$ где $n_{A}=\sum _{i\leq k}2^{a_{i}}$ (Ершов 1999: 477). Эта нумерация является (частичной) биекцией.
• Фиксированная нумерация Гёделя $\varphi _{i}$ вычислимых частичных функций можно использовать для определения нумерации W , рекурсивно перечислимых множеств полагая W ( i ) областью определения _φi . Эта нумерация будет сюръективной (как и все нумерации), но не инъективной: будут разные числа, которые отображаются в одно и то же рекурсивно перечислимое множество под W .

Виды нумерации

Нумерация является тотальной, если она является тотальной функцией. Если область определения частичной нумерации рекурсивно перечислима , то всегда существует эквивалентная полная нумерация (эквивалентность нумераций определена ниже).

Нумерация η разрешима, если множество $\{(x,y):\eta (x)=\eta (y)\}$ является разрешимым множеством.

Нумерация η однозначна , если η ( x ) = η ( y ) тогда и только тогда, когда x = y ; другими словами, если η — инъективная функция. Однозначная нумерация множества частично вычислимых функций называется нумерацией Фридберга .

Сравнение нумераций

есть предзаказ На комплект всех нумераций . Позволять $\nu _{1}:\mathbb {N} \rightharpoonup S$ и $\nu _{2}:\mathbb {N} \rightharpoonup S$ быть две нумерации. Затем $\nu _{1}$ сводится ​ к $\nu _{2}$, написано $\nu _{1}\leq \nu _{2}$, если

$\exists f\in \mathbf {P} ^{(1)}\,\forall i\in \mathrm {Domain} (\nu _{1}):\nu _{1}(i)=\nu _{2}\circ f(i).$

Если $\nu _{1}\leq \nu _{2}$ и $\nu _{1}\geq \nu _{2}$ затем $\nu _{1}$ эквивалентно ​ ​ $\nu _{2}$; это написано $\nu _{1}\equiv \nu _{2}$.

Вычислимые нумерации

Когда нумеруемые объекты множества S достаточно «конструктивны», обычно рассматривают нумерации, которые можно эффективно декодировать (Ершов 1999: 486). Например, если S состоит из рекурсивно перечислимых множеств, нумерация η вычислима , если набор пар ( x , y ), где y ∈ η ( x ), рекурсивно перечислим. Аналогично, нумерация g частичных функций вычислима, если отношение R ( x , y , z ) = «[ g ( x )]( y ) = z » частично рекурсивно (Ершов 1999: 487).

Вычислимая нумерация называется главной , если к ней сводится всякая вычислимая нумерация одного и того же множества. И совокупность всех рекурсивно перечислимых подмножеств $\mathbb {N}$ и множество всех частично вычислимых функций имеет основные нумерации (Ершов 1999: 487). Принципиальная нумерация множества частично рекурсивных функций известна как допустимая нумерация в литературе .

См. также

• Полная нумерация
• Цилиндрификация
• нумерация Гёделя
• Номер описания

Ссылки

• Ю.Л. Ершов (1999), «Теория нумераций», Справочник по теории вычислимости , Elsevier, стр. 473–506.
• В.А. Успенский , А.Л. Семенов (1993), Алгоритмы: основные идеи и приложения , Springer.