Entscheiden, ob eine Turingmaschine eine Bewegung nach links ausgeführt hat

Wenn Sie eine Entscheidung für eine Maschine schreiben, um zu sehen, ob sie bei einer Eingabe von w eine Bewegung nach links ausgeführt hat oder nicht , wird gesagt, dass, wenn wir die Berechnung für fortsetzen$|w|+N+1$ ($N$ : Anzahl der Zustände) Anzahl der Schritte, wir können eine Entscheidung für diese Entscheidung treffen.

Ich habe nicht verstanden warum $|w|+N+1$Anzahl der Schritte. Könnte jemand dies genauer erklären?

$|w|$ Zum Scannen der Eingabe sind Schritte erforderlich, wenn während dieses Scanvorgangs eine Linksbewegung ausgeführt wird.

Andernfalls befindet sich am Ende der Eingabe der Kopf der Turing-Maschine auf dem leeren Teil des Bandes (über dem ersten leeren Symbol nach der Eingabe). Angenommen, der Zustand ist$q_{i_1}$. Wenn die Turingmaschine keinen Schritt nach links macht und im Zustand bleibt$q_{i_1}$, dann wird es es für immer tun (es wird sich weiter rechts auf dem unendlichen leeren Band-Ein-Zustand bewegen $q_{i_1}$). Aber es kann sich nach rechts bewegen und in den Zustand wechseln$q_{i_2}, i_1 \neq i_2$.

Wenn Sie mit dieser Argumentation fortfahren, sehen Sie, dass es nur zwei Möglichkeiten gibt:

• es bewegt sich nach links oder

• es tritt in einen Zustand ein $q_{i_{k+j}}$ zum zweiten mal und damit wird es für immer schleifen: $q_{i_k} \rightarrow q_{i_{k+1}}\rightarrow ...\rightarrow q_{i_{k+j}}=q_{i_k} \rightarrow q_{i_{k+1}}\rightarrow ...$

Aber es gibt nur $N$ verschiedene Zustände also höchstens $N+1$ Es sind weitere Schritte erforderlich, um eine solche Schleife zu erkennen.