В теории вычислимости теорема UTM или теорема об универсальной машине Тьюринга является основным результатом о гёделевской нумерации множества вычислимых функций . Он подтверждает существование вычислимой универсальной функции , способной вычислить любую другую вычислимую функцию. [1] Универсальная функция — это абстрактная версия универсальной машины Тьюринга , отсюда и название теоремы.
Теорема Роджера об эквивалентности дает характеристику гёделевой нумерации вычислимых функций в терминах теоремы s mn и теоремы UTM.
Теорема утверждает, что существует частично вычислимая функция u двух переменных, такая что для каждой вычислимой функции f одной переменной существует e такое, что для всех x . Это означает, что для каждого x либо f ( x ) и u ( e , x ) оба определены и равны, либо оба не определены. [2]
Таким образом, теорема показывает, что, определяя φ e ( x ) как u ( e , x ), последовательность φ 1 , φ 2 , ... является перечислением частично вычислимых функций. Функция в формулировке теоремы называется универсальной функцией.
