Twierdzenie UTM
W teorii obliczalności twierdzenie UTM funkcji lub uniwersalne twierdzenie o maszynie Turinga jest podstawowym wynikiem numeracji Gödla zbioru obliczalnych . Potwierdza istnienie obliczalnej funkcji uniwersalnej , która jest zdolna do obliczenia dowolnej innej funkcji obliczalnej. Funkcja uniwersalna jest abstrakcyjną wersją uniwersalnej maszyny Turinga , stąd nazwa twierdzenia.
Twierdzenie Rogera o równoważności zapewnia charakterystykę numeracji Gödla funkcji obliczalnych w kategoriach twierdzenia s mn i twierdzenia UTM.
Twierdzenie
Twierdzenie stwierdza, że istnieje częściowa obliczalna funkcja u dwóch zmiennych, taka że dla każdej obliczalnej funkcji f jednej zmiennej istnieje e takie, że dla wszystkich x . Oznacza to , że dla każdego x f ( x ) i u ( e , x ) są zdefiniowane i są równe lub oba są niezdefiniowane.
Twierdzenie pokazuje zatem, że definiując φ e ( x ) jako u ( e , x ), ciąg φ 1 , φ 2 , … jest wyliczeniem cząstkowych funkcji obliczalnych. Funkcja twierdzenia nazywana jest funkcją uniwersalną.
- Rogers, H. (1987) [1967]. Teoria funkcji rekurencyjnych i efektywna obliczalność . Pierwsze wydanie prasowe MIT w miękkiej oprawie. ISBN 0-262-68052-1 .
- Soare, R. (1987). Rekurencyjnie przeliczalne zbiory i stopnie . Perspektywy w logice matematycznej . Springer-Verlag. ISBN 3-540-15299-7 .