Нумерация (теория вычислимости)
В теории вычислимости нумерация — это присвоение натуральных чисел множеству объектов , таких как функции , рациональные числа , графики или слова на некотором формальном языке . Нумерацию можно использовать для передачи идеи вычислимости. [1] и связанные концепции, которые изначально определены для натуральных чисел с использованием вычислимых функций , для этих различных типов объектов.
Общие примеры нумераций включают нумерацию Гёделя в логике первого порядка , числа описания , возникающие из универсальных машин Тьюринга , и допустимые нумерации множества частично вычислимых функций.
Определение и примеры
[ редактировать ]Нумерация комплекта является сюръективной частичной функцией от к С (Ершов 1999: 477). Значение нумерации ν в номере i (если оно определено) часто пишется ν i вместо обычного .
Примеры нумерации включают в себя:
- Множество всех конечных подмножеств имеет нумерацию , определенный так, что и так, что для каждого конечного непустого множества , где (Ершов 1999: 477). Эта нумерация является (частичной) биекцией.
- Фиксированная нумерация Гёделя вычислимых частичных функций можно использовать для определения нумерации W , рекурсивно перечислимых множеств полагая W ( i ) областью определения φi . Эта нумерация будет сюръективной (как и все нумерации), но не инъективной: будут разные числа, которые отображаются в одно и то же рекурсивно перечислимое множество под W .
Виды нумерации
[ редактировать ]Нумерация является тотальной, если она является тотальной функцией. Если область определения частичной нумерации рекурсивно перечислима , то всегда существует эквивалентная полная нумерация (эквивалентность нумераций определена ниже).
Нумерация η разрешима, если множество является разрешимым множеством.
Нумерация η однозначна , если η ( x ) = η ( y ) тогда и только тогда, когда x = y ; другими словами, если η — инъективная функция. Однозначная нумерация множества частично вычислимых функций называется нумерацией Фридберга .
Сравнение нумераций
[ редактировать ]есть предзаказ На комплект всех нумераций . Позволять и быть две нумерации. Затем сводится к , написано , если
Если и затем эквивалентно ; это написано .
Вычислимые нумерации
[ редактировать ]Когда нумеруемые объекты множества S достаточно «конструктивны», обычно рассматривают нумерации, которые можно эффективно декодировать (Ершов 1999: 486). Например, если S состоит из рекурсивно перечислимых множеств, нумерация η вычислима , если набор пар ( x , y ), где y ∈ η ( x ), рекурсивно перечислим. Аналогично, нумерация g частичных функций вычислима, если отношение R ( x , y , z ) = «[ g ( x )]( y ) = z » частично рекурсивно (Ершов 1999: 487).
Вычислимая нумерация называется главной , если к ней сводится всякая вычислимая нумерация одного и того же множества. И совокупность всех рекурсивно перечислимых подмножеств и множество всех частично вычислимых функций имеет основные нумерации (Ершов 1999: 487). Принципиальная нумерация множества частично рекурсивных функций известна как допустимая нумерация в литературе .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ «Теория вычислимости — обзор | Темы ScienceDirect» . www.sciencedirect.com . Проверено 19 января 2021 г.
- Ю.Л. Ершов (1999), «Теория нумераций», Справочник по теории вычислимости , Elsevier, стр. 473–506.
- В.А. Успенский , А.Л. Семенов (1993), Алгоритмы: основные идеи и приложения , Springer.