Beweis

• Fall 1: ≠x ⇒ M terminiert sofort, da in Endzustand

• Fall 2: =x

  • Fall 2.1:  = „L“ ⇒ M terminiert irgendwann:
    • Wenn Zeichen nicht mehr passt oder Bandende erreicht, und weil keine andere Kopfbewegung mehr möglich
    • Band enthält endlich viele Zeichen (⇐ endliche Eingabe; endliche Anzahl Schritte ausgeführt)
  • Fall 2.2:  = „R“ ⇒ M terminiert irgendwann (analog 2.1)
  • Fall 2.3:  = „N“
    • Fall 2.3.1: = ⇒ M terminiert nicht (Endlosschleife)
    • Fall 2.2.2: ≠ ⇒ M terminiert im nächsten Schritt (Fall 1)

Notizen: