Abschließend $ Space (n^2) Neq Space (n^7) $ von universeller Laufmaschine Laufzeit

Question

Sei $ m_u $ eine universelle Turing -Maschine, die die folgende Bedingung erfüllt:

Wenn $ M $ läuft $ x $ $ f (x) $ space, dann läuft $ m_u $ auf $ Langle Langle m rangle, x rangle $ nimmt $ (f (| x |))^3+2 cdot | x |+| Langle m rangle | $ space.

Warum können wir aus dem oben genannten $ { sf space} (n^2) neq { sf space} (n^7) $?

Answer 1

Ich nehme an, mit $ { sf space} $, Sie meinen $ { sf dspace} $. Wie üblich für diese Art von Hierarchie -Frage können Sie a verwenden Diagonalisierung Streit.

Erstellen Sie also eine Maschine $ d $, die ihren Eingang $ W $ nimmt und dann $ M_U ( Langle W, W Rangle) $ ausführt. Bei der Ausführung von $ m_u $ prüft es auch, wie viel Speicherplatz verwendet wird und wie viele Schritte $ M_U $ ausgeführt haben. Dann ist das Ergebnis von $ d $ das folgende:

• Wenn $ d $ mehr als $ n^2 $ Platz als Ablehnung verwendet,
• Wenn $ d $ mehr als $ 2^{cn^2} $ Schritte macht, akzeptieren
• Wenn keines der oben genannten Aufträge aufgetreten ist, akzeptieren Sie, ob $ M_U $ abgelehnt wurde, und lehnen Sie ab, ob $ M_U $ akzeptiert wird.

Sie können sagen, dass $ D (w) $ Anti-Simulate Die Maschine $ M_U ( Langle W, W Rangle) $, wenn $ Langle W rangle $ in $ { sf dspace} (n^2) $ ist. Offensichtlich ist $ Langle d rangle $ in $ { sf dspace} (n^7) $. Es kann jedoch nicht in $ { sf dspace} (n^2) $ sein. Wenn dies der Fall wäre, erhalten Sie einen Widerspruch bei $ D ( Langle d rangle) $.