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

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

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

Определение

Формализация теории вычислимости Клини привела к конкретной универсальной частично вычислимой функции Ψ( 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).

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

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

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

Определение

Эквивалентное определение

Теорема Роджерса об эквивалентности

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

Рекомендации