Universelle Simulation von Turingmaschinen

16

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 gibtU

  • Die Beschreibung eines TM undM
  • 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|)Mxgω(f(n)lgf(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)ω(f(n))ω(f(n)lgf(n))

Kaveh
quelle
Sollte die Anzahl der Bänder gleich oder irgendwie begrenzt sein?
Raphael
Und mehrere Bänder können in quadratischer Zeit auf einem Band simuliert werden. Wenn diese Art der Simulation also fair ist, warum erwarten Sie dann einen Unterschied? Oder ist die lineare Simulationszeit aus anderen Gründen angemessen?
Raphael
"Ich frage, ob die Simulation mit linearem Overhead durchgeführt werden kann" - das kann ich der Frage nicht zuordnen. Meinten Sie ? o(f(n))
Raphael
1
@Raphael, ich habe es nochmals überprüft und die Frage aktualisiert. Das ist korrekt, beachte, dass g eine beliebige Funktion in ω ( f ( n ) ) ist . (Im Theorem brauchen wir etwas, das schneller wächst als f ( n ) lg f ( n ), weil das Alphabet und die Anzahl der Zustände der simulierten Maschine nicht festgelegt sind, daher gibt es eine maschinenabhängige Konstante. ω wird verwendet wegen sie.)ωgω(f(n))f(n)lgf(n)ω
Kaveh

Antworten:

7

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(n2)Ω(n2)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)ω(f(n))ω(f(n)lgf(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).nlg

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-Hierarchiesatzlgf ,
    3. Alphabet der Single-Tape-Turing-Maschine ,
    4. Wie wird die Eingabe für den Zeithierarchiesatz effizient übersetzt? ,
    5. ein Kommentar von Luca Trevisan.
Kaveh
quelle
Dennoch gibt es ein paar Dinge, die für mich immer noch nicht ganz klar sind, insbesondere zu 8.3 und zur Single-Tape-Simulation von Single-Tape-Maschinen. Ich werde die Antwort bei Bedarf aktualisieren.
Kaveh,
n2t(n)t(n)