Допустимая нумерация
-
Определение и эквивалентность допустимых нумераций
- Допустимые нумерации — это перечисления частично вычислимых функций, которые можно преобразовать в стандартную нумерацию.
- Все допустимые системы программирования эквивалентны в теории нумерации.
-
Формализация теории вычислимости
- Клини создал универсальную частично вычислимую функцию θ(e, x) с использованием предиката T.
- Последовательность ψ0, ψ1, … представляет все частично вычислимые функции.
-
Эквивалентное определение допустимости
- Нумерация η допустима, если она вычислима, универсальна по Тьюрингу и обладает вычислимым каррированием.
-
Теорема Роджерса об эквивалентности
- Хартли Роджерс-младший доказал, что нумерация η допустима тогда и только тогда, когда существует полная вычислимая биекция p, такая, что для всех e ne = θp(e).
-
Рекомендации и источники
- Ссылки на книги и статьи по теории вычислимости и нумерациям.