Universelle Simulation von Turingmaschinen

Sei eine feste zeitkonstruierbare Funktion.$f$

Das klassische universelle Simulationsergebnis für TMs (Hennie und Stearns, 1966) besagt, dass es ein solches Zwei-Band-TM gibt$U$

• Die Beschreibung eines TM und$\langle M \rangle$
• eine Eingabezeichenfolge ,$x$

läuft für Schritte und gibt die Antwort von M auf x zurück . Und für g kann jede Funktion in ω ( f ( n ) lg f ( n ) ) genommen werden .$g(|x|)$$M$$x$$g$$\omega(f(n)\lg f(n))$

Meine Fragen sind:

1. Was ist das bekannteste Simulationsergebnis auf einem einzelnen Band TM? Gilt das obige Ergebnis auch noch?

2. Gibt es eine Verbesserung gegenüber [HS66]? Können wir TMs auf einem Zwei-Band-TM schneller für Schritte simulieren ? Können wir annehmen, dass g ( n ) in ω ( f ( n ) ) anstelle von ω ( f ( n ) lg f ( n ) ) ist ?$f(n)$$g(n)$$\omega(f(n))$$\omega(f(n)\lg f(n))$

Was ist das bekannteste Simulationsergebnis auf einem einzelnen Band TM? Gilt das obige Ergebnis auch noch?

Wir können ein Multi-Tape-TM auf einem Single-Tape-TM mit quadratischem Zeitanstieg simulieren. Die Simulationszeit ist . Die quadratische Erhöhung ist erforderlich, da es Sprachen (z. B. Palindrome) gibt, die Zeit Ω ( n 2 ) in einem Einzelband-DTM benötigen, aber in Zeit O ( n ) in einem Doppelband-DTM gelöst werden können .$O(n^2)$$\Omega(n^2)$$O(n)$

Kurz gesagt, das obige Ergebnis funktioniert nicht, wenn der Simulator ein Single-Tape-TM ist.

Zur Simulation von Einzelband TMs auf einer Single-Band TM (mit beliebigem endlichen Alphabet), hält das Ergebnis, dh die Simulation kann erfolgen Faktor Zunahme der Zeit. Siehe (2) und (3). Die Referenz scheint (6) zu sein.$\lg$

Gibt es eine Verbesserung gegenüber [HS66]? Können wir TMs auf einem Zwei-Band-TM schneller für Schritte simulieren ? Können wir annehmen, dass g ( n ) in ω ( f ( n ) ) anstelle von ω ( f ( n ) lg f ( n ) ) ist ?$f(n)$$g(n)$$\omega(f(n))$$\omega(f(n)\lg f(n))$

Es scheint keine Verbesserung zu geben, da dies einen besseren Zeithierarchiesatz implizieren würde als derzeit bekannt.

Korrektur: Die üblichen Hierarchiesätze basieren auf Zeitkomplexitätsklassen, die mit Single-Tape-TMs definiert wurden. Für Band-TMs hat Furer 1982 ein dichtes Ergebnis ähnlich dem Raumhierarchiesatz bewiesen (5). Der lg- Faktor wird nicht benötigt. Siehe auch (4).$n$$\lg$

Verweise:

1. Peter van Emde Boas, "Maschinenmodelle und Simulation", im Handbuch Theoretische Informatik, 1990
   (insbesondere S. 18-21)

2. Michael Sipser, "Introduction to the Theory of Computation", 2006
   (Zeitkomplexitätsklassen werden mit TMs mit Single-Tape Infinite in beide Richtungen und beliebigem endlichem Alphabet definiert, siehe Seiten 140 und 341)

3. Odifreddi, "Klassische Rekursionstheorie", vol. I & II, 1989 & 1999
   (Definitionen sind ähnlich wie Sipser, siehe Def. I.4.1 in Band I Seite 48, Def. VII.4.1 in Band II Seite 67 und Thm. VII.4.15 in Band II Seite 83)

4. Piergiorgio Odifreddi, "Klassische Rekursionstheorie", vol. II, 1999
   (Seite 84)

5. Martin Fürer, " Die enge deterministische Zeithierarchie ", 1982

6. Juris Hartmanis, " Computational Complexity of One-Tape Turing Machine Computations ", 1968

7. FC Hennie und RE Stearns, " Two-Tape-Simulation von Multitape-Turing-Maschinen ", 1966

8. Andere verwandte Fragen:

   1. Untere Schranken und Klassentrennung ,
   2. Begründung von im DTIME-Hierarchiesatz$\lg f$ ,
   3. Alphabet der Single-Tape-Turing-Maschine ,
   4. Wie wird die Eingabe für den Zeithierarchiesatz effizient übersetzt? ,
   5. ein Kommentar von Luca Trevisan.