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

Turingmaschine - Tabelle gegeben?

–2 Punkte
158 Aufrufe
Hey Leute ,

ich hätte maln paar Fragen zu Turingmaschinen.

1. Muss man die Tabelle immer selber erstellen oder ist sie immer gegeben?

2. Verstehe überhaupt nicht wie die Tabelle zur Stande kommt , kann das jemand erklären?

3. Wenn man quasi n Codewort generiert , sieht man ja bei der Lösung , man kanns z.B mit 4 Zeichen oder 3 oder x Zeichen machen. Inwiefern kann ich das entscheiden wie viele Zeichen genutzt werden müssen ??
Gefragt 9, Feb 2017 in 2014-B-02 von ucekt ucekt Lernwillige(r) (150 Punkte)  
Was 2. und 3. angeht, müssen Sie schon präziser werden. Was verstehen Sie an der Turingtafel nicht - was die Einträge bedeuten? Oder wie man für diesen speziellen Fall eine Turingtafel aufstellt? Falls letzeres, wie weit sind Sie denn im Verständnis gekommen und wo hakt es?

Bei 3. bin ich ganz ratlos. Was meinen Sie damit? Wo "generieren Sie denn bei dieser Aufgabe Codewörter"? Meinen Sie mit den "genutzten Zeichen" das $E$?
PS. Formalitäten sind uns ja eigentlich egal, aber Ihre Frage ist schon sehr hingeschlonzt. Ein bisschen mehr Höflichkeit und auch Rücksicht auf die freundlichen "Leute", die viel Zeit investieren, um Ihre Fragen zu beantworten, wäre angebracht.

2 Antworten

+1 Punkt
 
Beste Antwort
  1. Sie meinen die Turingtafel? Die müssen Sie weder immer selbst erstellen noch ist sie immer gegeben. Das machen wir, wie es uns gerade passt, und Sie müssen damit leben :-) Ist das denn wichtig für Sie?
  2. Die Turingmaschine muss über die ursprüngliche Eingabe laufen und für jede Eins, die sie findet eine Eins vor diese Eingabe schreiben. Damit sie weiß, welche Einsen sie schon abgearbeitet hat, schreibt sie statt Eins immer $E$ als Platzhalter. Diese Platzhalter müssen am Ende durch echte Einsen ersetzt werden. In Zustand $s_0$ läuft die Turingmaschine bis zur ersten echten Eins (dabei läuft sie über Nullen und $E$-Symbole hinweg), überschreibt diese mit $E$ und wechselt nach $s_1$. (Falls sie gar keine Eins mehr findet, also einen Stern liest, wechselt sie nach $s_2$, das passiert, wenn alle Einsen bearbeitet worden sind.) In $s_1$ läuft sie zurück über alle $E$ und Nullen hinweg und schreibt vor die Eingabe ein $E$. Danach wechselt sie wieder in $s_0$ und führt in einer Schleife diesen Vorgang so lange durch, bis alle Einsen durch $E$ ersetzt worden sind. Wie schon beschrieben, wechselt sie dann nach $s_2$, und in diesem Zustand überschreibt sie alle $E$ durch Einsen und bleibt schließlich im Endzustand $s_e$ stehen.

@[ID-C22881]@

Beantwortet 9, Feb 2017 von Lukas König Dozent (10,065,100 Punkte)  
ausgewählt 9, Feb 2017 von Lukas König
Hallo ,

grundsätzlich kappiere ich wie die längere Tabelle ihren Lauf nimmt , sofern ich die obere Tabelle der genannten Aufgabe gegeben habe.
Könnten Sie mir eventuell erklären , wie speziell die obere Tabelle zu Stande kam?
+1 Punkt
Zu erstens: Mit Tabelle selber erstellen oder gegeben meinst du eine zeichnen musst oder eine leere gegeben ist die du selber beschriften und ausfüllen musst?

soweit ich es beobachtet habe ist normalerweise eine leere gegeben, wobei Spalten- und Zeilenanzahl nicht ausgenutzt werden müssen -> wenn es eine Tabelle mit zwanzig Zeilen gibt, kann es sein, dass du nur zwölf benötigst. Ein Blick in die altklausurensammlung würde aber auch helfen. Z.B http://info2.aifb.kit.edu/secure/Klausuren/2015-Nach.pdf

 

Zu Drittens, ist sofern verlangt eigentlich auch klar definiert.

 

Zu Zweitens würde empfehlen, dich grundlegend mit der Turingmaschine zu beschäftigen und dann die Frage nochmals konkreter zu stellen.
Beantwortet 9, Feb 2017 von uahge uahge Info-Genie (25,640 Punkte)  
Bearbeitet 9, Feb 2017 von Lukas König
...