В теории вычислимости нумерация является присвоением натуральных чисел в виде набора объектов , такие как функции , рациональные числа , графики , или слова в некотором формальном языке . Нумерация может использоваться для передачи идеи вычислимости [1] и связанных понятий, которые первоначально определены для натуральных чисел с использованием вычислимых функций , на эти различные типы объектов.
Общие примеры нумерации включают нумерацию Гёделя в логике первого порядка и допустимую нумерацию множества частично вычислимых функций.
Определение и примеры
Нумерации из набораявляется сюръективной частичной функцией изк С (Ершов 1999: 477). Значение нумерации ν для числа i (если оно определено) часто записывается как ν i вместо обычного.
Примеры нумерации включают:
- Множество всех конечных подмножеств имеет нумерацию , определенная так, что так что для каждого конечного непустого множества , где (Ершов 1999: 477). Эта нумерация является (частичной) биекцией.
- Фиксированная нумерация Гёделя из вычислимых частичных функций могут быть использована для определения нумерации W из перечислимых множеств , позволяя с помощью W ( я ) быть областью φ я . Эта нумерация будет сюръективна (как и все нумерации) , но не инъективна: там будут различными числа , что карта с тем же рекурсивно перечислимым множеством при W .
Типы нумерации
Нумерация является итоговой, если это итоговая функция. Если область частичной нумерации рекурсивно перечислима, то всегда существует эквивалентная полная нумерация (эквивалентность нумерации определяется ниже).
Нумерация η является разрешимым , если набор - разрешимое множество.
Нумерация η является однозначным , если η ( х ) = η ( у ) тогда и только тогда , когда х = у ; другими словами, если η - инъективная функция. Однозначная нумерация множества частично вычислимых функций называется нумерацией Фридберга .
Сравнение нумераций
По набору всех нумераций есть предварительный заказ . Позволять а также быть двумя нумерациями. потомявляется приводимым к, написано , если
Если а также тогда является эквивалентом для; это написано.
Вычислимые нумерации
Когда нумеруемые объекты множества S достаточно «конструктивны», обычно обращаются к нумерации, которая может быть эффективно декодирована (Ершов 1999: 486). Например, если S состоит из перечислимых множеств, нумерация п является вычислимой , если множество пар ( х , у ) , где у ∈ п ( х ) перечислимо. Аналогично, нумерация 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.