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

• Определение и эквивалентность допустимых нумераций

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

• Формализация теории вычислимости

  • Клини создал универсальную частично вычислимую функцию θ(e, x) с использованием предиката T. 
  • Последовательность ψ0, ψ1, … представляет все частично вычислимые функции. 

• Эквивалентное определение допустимости

  • Нумерация η допустима, если она вычислима, универсальна по Тьюрингу и обладает вычислимым каррированием. 

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

  • Хартли Роджерс-младший доказал, что нумерация η допустима тогда и только тогда, когда существует полная вычислимая биекция p, такая, что для всех e ne = θp(e). 

• Рекомендации и источники

  • Ссылки на книги и статьи по теории вычислимости и нумерациям.