Введение
В теории вычислимости присвоение натуральных чисел множеству объектов является нумерацией. Нумерация — это присвоение натуральных чисел множеству объектов, таких как функции, рациональные числа, графы или слова в некотором формальном языке. Нумерацию можно использовать для переноса идеи вычислимости и связанных с ней понятий, которые изначально определены на натуральных числах с помощью вычислимых функций, на эти различные типы объектов. Распространенными примерами нумераций являются числа Гёделя в логике первого порядка, числа описания, возникающие из универсальных машин Тьюринга, и допустимые нумерации множества частично вычислимых функций.
In computability theory a numbering is the assignment of natural numbers to a set of objects such as functions, rational numbers, graphs, or words in some formal language. A numbering can be used to transfer the idea of computability and related concepts, which are originally defined on the natural numbers using computable functions, to these different types of objects. Common examples of numberings include Gödel numberings in first order logic, the description numbers that arise from universal Turing machines and admissible numberings of the set of partial computable functions.
Виды нумерации
Нумерация считается полной, если она является тотальной функцией. Если область определения частичной нумерации рекурсивно перечислима, то всегда существует эквивалентная полная нумерация (эквивалентность нумераций определяется ниже). Нумерация η называется разрешимой, если множество {x | η(x) определено} является разрешимым множеством. Нумерация η называется однозначной, если η(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). Принципиальная нумерация множества частично рекурсивных функций в литературе известна как допустимая нумерация.