Beweisen, dass Turing Machine M rechtzeitig $ O (2^{dn}) $ läuft

Question

Ich versuche, diese Frage zu lösen, um meine Prüfung zu überprüfen, und dieser hat mich ein bisschen ratlos gemacht. Aus dem Aussehen scheint es eine ziemlich einfache Frage zu sein, aber ich kann nicht herausfinden, mit welchen Schritten sie beginnen.

Sei $ m $ eine lineare Turing-Maschine, die aus einem einzigen Klebeband besteht. Wir sagen, $ M $ ist eine linear-Raum-Turing-Maschine, wenn m bei jeder Eingabe angehalten wird und wenn es Konstanten $ C $ und $ n_ {0} $ gibt, so dass für alle Eingaben $ x in sigma^{ ast} $ von Länge $ N Geq N_ {0} $, $ m $ läuft auf $ x $ Besuchen höchstens $ c cdot n $ Tape Quadrate.

Beweisen Sie, dass $ m $ für einige konstante $ d $ läuft $ o (2^{dn}) $.

Ich habe zunächst ein paar Ideen. Erstens sagt mir meine Intuition, dass ich nur einen Algorithmus erstellen muss, der nach diesen Regeln läuft und rechtzeitig $ O (2^{dn}) $ akzeptiert/ablehnt. Zweitens gibt es einen Hinweis, der mir sagt, ich soll "die Anzahl der Konfigurationen berücksichtigen". Ich bin mir jedoch nicht sicher, wie ich das einbeziehen soll.

Vielen Dank im Voraus für jede Hilfe.

Answer 1

Ihre Intuition ist aus dem folgenden Grund problematisch: Sie erhalten eine bestimmte Maschine $ m $, keine Sprache. Wenn Sie also einen Algorithmus beschreiben, der in $ o (2^{dn}) $ ausgeführt wird und dieselbe Sprache entscheidet, beweisen Sie effektiv, dass $ l (m) $ in $ o (2^{dn}) $ entscheidbar ist. Aber das bedeutet nicht, dass $ M $ selbst läuft in diesem Zeitrahmen.

Wie der Hinweis darauf hinweist, berücksichtigen Sie die Anzahl der möglichen Konfigurationen von $ M $: Erinnern Sie sich daran, dass eine Konfiguration eines TM aus dem Inhalt des Bandes, der Position des Kopfes und des Zustands besteht. Da das Alphabet der Maschine festgelegt ist und dass das in $ m $ $ $ x $ verwendete Band $ c cdot | x | $ ist, versuchen Sie, die Anzahl der möglichen Konfigurationen zu binden (ausgedrückt in der Größe von $ m $ und $ | x | $)

Erinnern Sie sich nun daran, dass $ M $ immer angehalten wird. Was bedeutet das über die Abfolge der Konfigurationen, die es in seinem Lauf auf $ x $ durchläuft?

Wenn Sie diese beiden Beobachtungen kombinieren, erhalten Sie die Antwort. Kommentieren Sie, wenn Sie weitere Hinweise benötigen.