WikiDer > Теорема UTM

UTM theorem

В теория вычислимости, то UTM теорема, или же универсальная машина Тьюринга теорема, это основной результат о Гёделевская нумерация из набора вычислимые функции. Он подтверждает существование вычислимой универсальная функция, который способен вычислить любую другую вычислимую функцию.[1] Универсальная функция - это абстрактная версия универсальная машина Тьюринга, отсюда и название теоремы.

Теорема эквивалентности Роджера дает характеристику гёделевской нумерации вычислимых функций в терминах sмин теорема и теорема UTM.

Теорема

Теорема утверждает, что a частичный вычислимая функция ты двух переменных существует такое, что для каждой вычислимой функции ж одной переменной, е существует такое, что для всех Икс. Это означает, что для каждого Икс, либо ж(Икс) и ты(е,Икс) оба определены и равны, либо оба не определены.[2]

Таким образом, теорема показывает, что, определяя φе(Икс) в качестве ты(е, Икс) последовательность φ1, φ2,… - перечисление частично вычислимых функций. Функция в формулировке теоремы называется универсальной функцией.

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

  • Роджерс, Х. (1987) [1967]. Теория рекурсивных функций и эффективной вычислимости. Первое издание MIT в мягкой обложке. ISBN 0-262-68052-1.CS1 maint: ref = harv (связь)
  • Соаре, Р. (1987). Рекурсивно перечислимые множества и степени. Перспективы математической логики. Springer-Verlag. ISBN 3-540-15299-7.CS1 maint: ref = harv (связь)
  1. ^ Роджерс 1967, п. 22.
  2. ^ Soare 1987, п. 15.