Gibt es einen Beweis dafür, dass die Emulation einer Turing-Maschine auf einer Turing-Maschine nicht in weniger als wobei die Anzahl der Schritte ist, die die Turing-Maschine verwendet ? Oder ist das nur eine Obergrenze?
In der Arbeit von Paul Vitányi über relativierte vergessene Turingmaschinen behauptet Vitányi
Sie [ Pippenger und Fischer, 1979 ] zeigten, dass dieses Ergebnis im Allgemeinen nicht verbessert werden kann, da es eine Sprache L gibt, die von einer 1-Band-Echtzeit-Turing-Maschine erkannt wird , und eine beliebige Turing-Maschine die erkennen muss Verwenden Sie mindestens eine Reihenfolge Schritte ".
Dies sollte als absolute Grenze angeben. Allerdings finde ich keinen Beweis dafür in
Pippenger, Nicholas; Fischer, Michael J. , Beziehungen zwischen Komplexitätsmaßen , J. Assoc. Comput. Mach. 26, 361 & ndash; 381 (1979). ZBL0405.68041 .
Irgendwelche Ideen? Welche räumliche Komplexität hat diese Emulation? Der Umbau auf eine Universal-Turingmaschine verdoppelt meines Wissens nur die Bandlänge. Kann ich davon ausgehen , dass der Raum Komplexität mit der Raum Komplexität der ursprünglichen Turing - Maschine?
quelle
Antworten:
Wie oben erwähnt, ist im Allgemeinen nicht bekannt, ob es eine schnellere vergessene Simulation gibt.
Interessante Untergrenzen für dieses Problem sind jedoch unter eingeschränkteren Bedingungen bekannt. Was ist zum Beispiel, wenn Sie eine vergessene Simulation wünschen, die nicht nur die Zeit sondern auch die Raumnutzung berücksichtigt ? Beame und Machmouchi haben kürzlich einen interessanten Kompromiss zwischen Zeit und Raum für dieses Problem gefunden: Entweder muss der Raum um den Faktor oder die Zeit um den Faktor .s n 1 - o ( 1 ) Ω ( log n ⋅ log log n )t s n1 - o ( 1 ) Ω ( logn ⋅ logLogn )
Das Papier ist hier: http://eccc.hpi-web.de/report/2010/104/
quelle
Nur ein ausführlicher Kommentar: Ich denke, es ist immer noch ein offenes Problem. Im Blog von Lipton und Regan finden Sie einige interessante Diskussionen zur Verbesserung des Ergebnisses des Fischer-Pippenger-Theorems .
Siehe zum Beispiel die Posts: Oblivious Turing Machines and a "Crock" oder Circuits Bounds für Turing Machine-Berechnungen (beide vom 2009).
Im zweiten Beitrag zeigen sie, dass eine bessere Schaltungsgrenze ( ) mit einer partiellen booleschen Funktion , die sich annähert die ursprüngliche Funktion auf Eingängen.O ( n logLogn ) G: 2n→ { 0 , 1 , ∗ } f 2n - o ( n )
quelle