Теорема UTM

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

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

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

Таким образом, теорема показывает, что, определяя φ e (x) как u (e, x), последовательность φ 1, φ 2,… является перечислением частично вычислимых функций. Функция $u\; \{\backslash \; displaystyle\; u\}$в формулировке теоремы называется универсальной функцией.

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

1. ^Роджерс 1967, стр. 22. Ошибка sfn: нет цели: CITEREFRogers1967 (help )
2. ^Soare 1987, стр. 15. Ошибка sfn: нет цели: CITEREFSoare1987 (help )