Věta UTM - UTM theorem
![]() | Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace.Srpna 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v teorie vypočítatelnosti, UTM teorémnebo univerzální Turingův stroj teorém, je základní výsledek o Gödelovo číslování sady vypočítatelné funkce. Potvrzuje existenci vypočítatelného univerzální funkce, který je schopen vypočítat jakoukoli jinou vypočítatelnou funkci.[1] Univerzální funkce je abstraktní verzí univerzální Turingův stroj, tedy název věty.
Rogerova věta o ekvivalenci poskytuje charakterizaci Gödelova číslování vypočítatelných funkcí z hlediska smn teorém a teorém UTM.
Teorém
Věta říká, že a částečný vypočítatelná funkce u dvou proměnných existuje tak, že pro každou vypočítatelnou funkci F jedné proměnné, an E existuje takový, že pro všechny X. To znamená, že pro každého X, buď F(X) a u(E,X) jsou oba definované a jsou si rovni, nebo jsou oba nedefinovaní.[2]
Věta tedy ukazuje, že definováním φE(X) tak jako u(E, X), posloupnost φ1, φ2,… Je výčet částečných vypočítatelných funkcí. Funkce ve tvrzení věty se nazývá univerzální funkce.
Reference
- Rogers, H. (1987) [1967]. Teorie rekurzivních funkcí a efektivní vypočítatelnost. První MIT tisk brožované vydání. ISBN 0-262-68052-1.CS1 maint: ref = harv (odkaz)
- Soare, R. (1987). Rekurzivně vyčíslitelné množiny a stupně. Perspektivy v matematické logice. Springer-Verlag. ISBN 3-540-15299-7.CS1 maint: ref = harv (odkaz)
![]() | Tento matematická logika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |
- ^ Rogers 1967, str. 22.
- ^ Soare 1987, str. 15.