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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

1 Pluspunkt 0 Minuspunkte
127 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?
in 2015-H-05 von uxduy uxduy Lernwillige(r) (470 Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
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)
von uxdjy uxdjy Tutor(in) (100k Punkte)  
...