Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Wie kommt man auf S(1)=1?

+1 Punkt
99 Aufrufe
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?
Gefragt 12, Feb 2016 in 2015-H-05 von uxduy uxduy Lernwillige(r) (470 Punkte)  

Eine Antwort

0 Punkte
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)
Beantwortet 13, Feb 2016 von uxdjy uxdjy Tutor(in) (100,420 Punkte)  
...