Теорема UTM

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

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

Теорема

Теорема утверждает, что существует частично вычислимая функция u двух переменных такая, что для каждой вычислимой функции f одной переменной существует e такое, что $f(x)\simeq u(e,x)$ для всех х . Это означает, что для каждого x либо f ( x ) и u ( e , x ) оба определены и равны, либо оба не определены.

Таким образом, теорема показывает, что, определяя φ _e ( x ) как u ( e , x ), последовательность φ ₁ , φ ₂ , ... является перечислением частично вычислимых функций. Функция $u$ в формулировке теоремы называется универсальной функцией.

Ссылки

• Роджерс, Х. (1987) [1967]. Теория рекурсивных функций и эффективная вычислимость . Первое издание MIT в мягкой обложке. ISBN  0-262-68052-1 .
• Соаре, Р. (1987). Рекурсивно перечислимые множества и степени . Перспективы математической логики. Спрингер-Верлаг. ISBN  3-540-15299-7 .