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

Admissible numbering

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

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

Определение

Формализация теории вычислимости Клини привела к конкретной универсальной частично вычислимой функции (е, Икс) определяется с помощью Предикат T. Эта функция универсальна в том смысле, что она частично вычислима, и для любой частично вычислимой функции ж существует е такое, что для всех Икс, ж(Икс) = Ψ (е,Икс), где равенство означает, что либо обе стороны не определены, либо обе определены и равны. Обычно пишут ψе(Икс) для Ψ (е,Икс); таким образом, последовательность ψ0, ψ1, ... перечисление всех частично вычислимых функций. Такие нумерации формально называются вычислимыми нумерациями частично вычислимых функций.

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

  • Функция ЧАС(е,Икс) = ηе(Икс) - частично вычислимая функция.
  • Есть полная вычислимая функция ж такое, что для всех е, ηе = ψж(е).
  • Есть полная вычислимая функция грамм такое, что для всех е, ψе = ηграмм(е).

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

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

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

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

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

  • Ю.Л. Ершов (1999), "Теория нумерации", Справочник по теории вычислимости, E.R. Griffor (ed.), 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