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

В теории вычислимости — присвоение натуральных чисел множеству объектов

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

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

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

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

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

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

Типы нумерации

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

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

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

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

На множестве всех нумераций существует предпорядок . Пусть и — две нумерации. Тогда сводится к , пишется , если ${\displaystyle \nu _{1}:\mathbb {N} \rightharpoonup S}$ ${\displaystyle \nu _{2}:\mathbb {N} \rightharpoonup S}$ ${\displaystyle \nu _{1}}$ ${\displaystyle \nu _{2}}$ ${\displaystyle \nu _{1}\leq \nu _{2}}$

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

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

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

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

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

Смотрите также

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

Ссылки

1. "Теория вычислимости - обзор | Темы ScienceDirect". www.sciencedirect.com . Получено 19.01.2021 .

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