В теории вычислимости , допустимые нумераций являются перечисления ( нумерации ) из множества частичных вычислимых функций , которые могут быть преобразованы в и из стандартной нумерации. Эти нумерации также называются приемлемыми нумерациями и приемлемыми системами программирования .
Теорема Роджерса об эквивалентности показывает, что все приемлемые системы программирования эквивалентны друг другу в формальном смысле теории нумерации.
Определение
Формализации теории Вычислимости Клини привели к определенной универсальной частичной вычислимой функции W ( е , х ) , определенной с помощью Т - предикатом . Эта функция является универсальной в том смысле , что он является частичным вычислимо, и для любой частичной вычислимой функции F существует е такое , что для всех х , е ( х ) = Ψ ( е , х ), где означает равенство что или оба стороны не определены или обе определены и равны. Оно является общим для записи ψ е ( х ) для Ф ( е , х ); таким образом, последовательность ψ 0 , ψ 1 , ... является перечислением всех частично вычислимых функций. Такие нумерации формально называются вычислимыми нумерациями частично вычислимых функций.
Произвольная нумерация частичных функций η определяется как допустимая, если:
- Функция H ( e , x ) = η e ( x ) является частично вычислимой функцией.
- Существует полная вычислимая функция f такая, что для всех e η e = ψ f ( e ) .
- Существует полная вычислимая функция g такая, что для всех e ψ e = η g ( e ) .
Здесь для первого маркера требуется, чтобы нумерация была вычислимой; второй требует, чтобы любой индекс для нумерации η мог быть эффективно преобразован в индекс для нумерации ψ; а третий требует, чтобы любой индекс для нумерации ψ мог быть эффективно преобразован в индекс для нумерации η.
Теорема эквивалентности Роджерса
Хартли Роджерс-младший показал, что нумерация η частично вычислимых функций допустима тогда и только тогда, когда существует полная вычислимая биекция p такая, что для всех η e = ψ p ( e ) (Soare 1987: 25).
Смотрите также
Рекомендации
- Ю.Л. Ершов (1999), "Теория нумерации", Справочник по теории вычислимости , Э. Р. Гриффор (ред.), Эльзевьер, стр. 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