Допустимая нумерация

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

Теорема Роджерса об эквивалентности показывает, что все приемлемые системы программирования эквивалентны друг другу в формальном смысле теории счисления.

Определение

Формализация теории вычислимости Клини привела к конкретной универсальной частично вычислимой функции Ψ( e , x ), определенной с помощью T. предиката Эта функция универсальна в том смысле, что она частично вычислима, и для любой частично вычислимой функции f существует e такое, что для всех x , f ( x ) = Ψ( e , x ), где равенство означает, что либо обе стороны не определены или обе определены и равны. Обычно _{) пишут ψe} ( x вместо Ψ( e , x ); таким образом, последовательность ψ ₀ , ψ ₁ , ... является перечислением всех частично вычислимых функций. Такие нумерации формально называются вычислимыми нумерациями частично вычислимых функций.

Произвольная нумерация частичных функций η называется допустимой, если :

• Функция H ( e , x ) = η _e ( x ) является частично вычислимой функцией.
• Существует полностью вычислимая функция f такая, что для всех e η _e = ψ _{f ( e )} .
• Существует полностью вычислимая функция g такая, что для всех e ψ _e = η _{g ( e )} .

Здесь первый пункт требует, чтобы нумерация была вычислимой; второй требует, чтобы любой индекс нумерации η мог быть эффективно преобразован в индекс нумерации ψ; а третий требует, чтобы любой индекс нумерации ψ можно было эффективно преобразовать в индекс нумерации η.

определение

Следующая эквивалентная характеристика допустимости имеет то преимущество, что она «внутрена по отношению к η», поскольку она не делает прямой ссылки на стандартную нумерацию (только косвенно через определение универсальности Тьюринга). Нумерация η частичных функций допустима в указанном смысле тогда и только тогда, когда:

• Функция оценки H ( e , x ) = η _e ( x ) является частично вычислимой функцией.
• η универсальна по Тьюрингу: для всех частично вычислимых функций f существует такое е , что η _e = f (обратите внимание, что здесь мы не предполагаем полную вычислимую функцию, которая преобразует η-индексы в ψ-индексы)
• η имеет «вычислимое каррирование» или удовлетворяет теореме о параметре или теореме Smn , т.е. существует полная вычислимая функция c такая, что для всех e,x,y , η _c(e,x) (y) = η _e (x, й)

Доказательство следующее:

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

С другой стороны, предположим, что η обладает свойствами эквивалентной характеристики.

Поскольку оценочная функция H(e,x)= η _e (x) частично вычислима, существует v такое, что ψ _v =H . Таким образом, по теореме о параметрах для стандартной нумерации существует полная вычислимая функция d такая, что ψ _d(v,e) (x)=H(e,x) для всех x . Тогда общая функция f(e) = d(v,e) удовлетворяет второй части приведенного выше определения.

Далее, поскольку функция оценки E(e,x)= ψ _e (x) для стандартной нумерации частично вычислима, по предположению тьюринговой универсальности существует u такое, что η _u (e, x) = ψ _e (x) для всех e,x .

Пусть c(x,e) — вычислимая функция карри для η. Тогда η _c(u,e) =ψ _e для всех e , поэтому g(e) = c(u,e) удовлетворяет третьей части первого определения, приведенного выше.

Роджерса

Хартли Роджерс-младший показал, что нумерация η частично вычислимых функций допустима тогда и только тогда, когда существует полная вычислимая биекция p такая, что для всех e η _e = ψ _{p ( e )} (Soare 1987:25).

См. также

• Нумерация Фридберга

Ссылки

• Ю.Л. Ершов (1999), «Теория нумераций», Справочник по теории вычислимости , Э.Р. Гриффор (ред.), Elsevier, стр. 473–506. ISBN   978-0-444-89882-1
• М. Мачти и П. Янг (1978), Введение в общую теорию алгоритмов , Северная Голландия, 1978. ISBN   0-444-00226-X
• Х. Роджерс-младший (1967), Теория рекурсивных функций и эффективная вычислимость , второе издание, 1987 г., MIT Press. ISBN   0-262-68052-1 (мягкая обложка), ISBN   0-07-053522-1
• Р. Соаре (1987), Рекурсивно перечислимые множества и степени , Перспективы математической логики, Springer-Verlag. ISBN   3-540-15299-7