Zu jeder nichtdeterministische Turing-Maschine
Konsequenzen
- NTM und DTM : Gleiche Berechnungsmacht, drastisch unterschiedliche Ressourcenaufwände (exponentielle Verlangsamung)
- DTM und
-Band-DTM: Gleiche Berechnungsmacht, unsubstantielle Laufzeitunterschiede Unterschiedliche Einsatzzwecke:
- Praktische Effizienz: An Laufzeit DTM gemessen
- Prinzipielle Lösbarkeit: An Entscheidbarkeit durch NTM gemessen