Turingmaschine - Tabelle gegeben?

Question

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 ??

Comments

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.

Answer 1

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]@

Comments

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?

Answer 2

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.