Wie kommt man auf S(1)=1?

Question

Hallo, ich verstehe leider nicht, wieso man auf S(1) = 1 kommt. Wieso befindet sich der Kopf nach der Bewegung in eine beliebige Richtung wieder im Anfangszustand?

Answer 1

Es geht bei dieser Aufgabe ja darum, das Verhalten einer Turingmaschine mit n Zuständen (in diesem Fall n=1) für die Eingabe des leeren Wortes lambda zu betrachten. Wenn man in eine Turingmaschine lambda eingibt sieht das Band ja wie folgt aus:

....**************....   es besteht also nur aus Sternen, da das Wort, welches auf dem Band zwischen den Sternen stehen würde leer ist. Also steht der Zeiger am Anfang auf jeden Fall auf einem Stern.

Hat die Turingmaschine nur einen Zustand und nur 2 erlaubte Zeichen (1,*) gibt es also nur folgende Möglichkeiten:

Der Übergang beim Lesen von * ist so, dass eine 1 geschrieben wird, man stehen bleibt und dann stoppt, weil es für 1 keinen weiteren Übergang gibt.

Beim Lesen von * wird eine 1 oder ein * geschrieben und nach links oder rechts gegangen. Da auf dem Band nur Sterne stehen (bis auf ggf. die 1 die wir selbst geschrieben haben) würde der Zeiger also wieder auf einem Stern stehen, einen Schritt in die gleiche Richtung gehen, dort wieder einen Stern lesen, u.s.w.

Da man im zweiten Fall ja immer in die gleiche Richtung geht würde man nie aus dem Stern lesen und weitergehen rauskommen und die Turingmaschine würde endlos weiterlaufen. In der Aufgabenstellung bezieht sich S(n) aber per Definition nur auf nicht endlos laufende Turingmaschinen, somit richtet sich S(n) nach dem 1. Fall und S(1)=1.

Ich hoffe das hilft dir weiter!

Pia (Tutorin)