Space Bounded Turing Machine - Klarstellung zur Rechenkomplexität (Buch: Arora -Barak) Frage 4.1

Question

Ich habe die folgende Frage von Computerkomplexität - ein moderner Ansatz von Sanjeev Arora und Boaz Barak:

Q 4.1
Beweisen Sie die Existenz eines universellen TM für die räumlich begrenzte Berechnung (analog zum deterministischen universellen TM von Satz 1.9).

Das heißt, beweisen Sie, dass es eine Turing -Maschine $ su $ gibt, so dass für jeden String $ alpha $ $ $ $ x $, wenn der tm $ m_ alpha $ - der TM von $ alpha $ - anhält $ x $, bevor $ t $ cellen seines Arbeitsband Das Arbeitsband, wobei $ C $ eine Konstante ist, abhängig von $ M_ alpha $.

Nachdem ich Theorem 1.9 und das universelle TM mit der Zeit überprüft habe, sehe ich, dass das Konstrukt $ su ( alpha, t, x) $ bedeutet, dass die Turing -Maschine SU nach $ t $ Schritten stoppt. Wenn dies jedoch der Fall ist, bedeutet dies, dass wir ein Turing -Maschine erstellen können, der $ m_ alpha $ entspricht, so dass die neue Turing -Maschine in $ t $ Schritten anhält, in denen $ t $ der "Raum" ist, der im Original verwendet wird.

Dies scheint jedoch ein zweifelhafter Austausch von Raum und Zeit zu sein. Wenn andererseits $ t $ tatsächlich bedeutet, dass die zweite Maschine auch innerhalb von $ t $ Platz stoppt, macht der zweite Teil keinen Sinn mehr, da $ Su $ $ $ ct $ cells verwendet, was nicht $ ist t $.

Meine Frage ist also, wie ich das interpretiere? Ist die erste Interpretation wirklich möglich?

Answer 1

Ich verstehe nicht, was Sie nach dem "-"-", aber hier ist, was Sie tun müssen:

Hoffentlich verstehen Sie die Idee der Turing -Maschinencodierung: dh Sie können jeder Turing -Maschine eine eindeutige Kennung (dh "Etikett") $ alpha $ zuweisen. Also mit $ m_ alpha $ meinen wir die von $ alpha $ gekennzeichnete Turing -Maschine. Sie müssen also a entwerfen Single turing machine $SU$ which takes three inputs $alpha$, $t$ and $x$ ($alpha$ is a turing machine label, $t$ is a space bound, and $x$ is an input string) and :

• Wenn $ m_ alpha $ mehr als $ t $ Bits Workspace für Eingabe $ x $ verwendet, bevor es anhielt

• Wenn $ m_ alpha $ höchstens $ t $ bits productspace für Input $ x $ verwendet, haben wir zwei Anforderungen für $ su $:

  • $ Su $ verwendet höchsten
  • $ Su $ gibt $ m_ alpha (x) $ aus

Die Idee ist, dass $ su $ für jede Maschine und für jede Eingabe diese Maschine simulieren kann, während sie nur etwas mehr Platz nutzen als die ursprüngliche Maschine. Beachten Sie, dass $ T $ eine Grenze für den Raum ist, den $ m_ alpha $ verwendet, nicht den Raum, den $ su $ verwendet. $ Su $ kann nicht genau so speicherisch effizient sein wie die ursprüngliche Maschine, da die Simulation etwas Overhead erfordert. Der Punkt ist jedoch, dass der Overhead für jeden $ alpha $ gering ist, egal wie groß $ $ $ ist Größe.

Satz 1.9. Außerdem gibt es einige Overheads: Eine Maschine, die in Zeitschritten $ t $ anhält, wird in $ ct log t $ Zeitschritten simuliert, bei denen $ C $ wieder konstant unabhängig von $ t $ oder der Eingabezeichenfolge ist.