Beim Lösen einer recht simplen Aufgabe bin ich auf ein paar Fragen gestoßen. Zunächst die Aufgabe: Es soll eine Turing-Maschine beschrieben werden, die zu einer unär kodierten Zahl (n wird als 0^(n+1) kodiert) den Vorgänger liefert bzw. 0, falls die Eingabe 0 ist. Meine erste Lösung sah so aus:

[img]http://img442.imageshack.us/img442/5626/predyr6.jpg[/img]

s ist der Startzustand, das habe ich vergessen zu markieren.

Ich gehe also einfach mit dem Lesekopf eine Position nach rechts. Falls ich am Ende des Bands angekommen ist, war die Zahl bereits 0, und ich gehe wieder eine Position nach links.

Ist das so in Ordnung? Sprich: kann das Ergebniswort irgendwo auf dem Arbeitsband anfangen? Meine eigene Vermutung ist nein, denn q_0 w -*-> q_e v bedeutet ja, dass links vom Lesekopf nichts stehen darf. Richtig?

Darf ich dann einfach das erste Zeichen mit einem Schweinegatter ersetzen? Dann muss ich die 0 natürlich ggf. neu erzeugen, weil ich sie ja kaputt gemacht habe. Also so:

(|s) –0#R–> (p|) –##L–> (q) –#0R–> (o) –##L–> (0|)

Ich könnte mir einen Schritt sparen, wenn ich die 0 eine Position weiter rechts schreibe:

(|s) –0#R–> (p|) –#0L–> (q) –##R–> (0|)

Ist das in Ordnung, wenn ich am Anfang etwas vom Arbeitsband lösche? Oder muss ich erst ganz nach hinten gehen, um dann die letzte 0 zu löschen?

Ich bin mir nicht ganz sicher, ob die letzte Turing-Maschine (die mit den vier Zuständen) linear beschränkt ist. Ich denke nicht.

Pro: Das Ergebnis ist nicht größer als die Eingabe.
Kontra: Ich schreibe an Stellen, die vorher ungenutzt waren.

Wäre nett, wenn jemand meine Zweifel aus dem Weg räumen könnte. Georg? [25]

Und gleich noch eine Aufgabe: der Bandinhalt soll um eins nach rechts geschoben werden. Ziemlich ungenaue Aufgabenstellung, wie ich finde. Mein Ansatz:

(|s) –aaL–> ( ) –#0R–> ( ) –aaL–> (e|)

a steht hierbei für ein beliebiges Zeichen. Es ist also egal, womit die Eingabe anfängt, ich lasse das ersten Zeichen so, wie es ist und gehe eins nach links. Dort werde ich ziemlich sicher ein Schweinegatter finden, welches ich durch 0 ersetze. Dann noch einmal nach rechts und nach links gehen und fertig. (Wieso kann man nicht einfach den Kopf dort lassen, wo er ist??)

Scheint mir eine vernünftige Lösung zu sein. Kann man das ganze auch mit einseitig unbeschränkter TM lösen?

Kann man das ganze auch mit einseitig unbeschränkter TM lösen?

Hm, für ein zweielementiges Alphabet könnte man das doch so machen:

[img]http://img65.imageshack.us/img65/7448/verschiebennf4.jpg[/img]

Das erste Zeichen wird mit einer 0 überschrieben, und der aktuelle Zustand gibt dann immer an, was als letztes gelesen wurde - das Zeichen muss dann als nächstes geschrieben werden. Zum Schluss müssen wir wieder zum Wortanfang zurückkehren.

Die Aufgabe wäre doch geradezu prädestiniert für einen Moore-Automaten, der nur aus zwei Zuständen 0 und 1 besteht mit entsprechenden Ausgaben. Wenn wir 0 als Startzustand definieren, wird ja auch die führende 0 vor Verarbeitung der eigentlichen Ausgabe generiert.

Das erste Zeichen wird mit einer 0 überschrieben, und der aktuelle Zustand gibt dann immer an, was als letztes gelesen wurde - das Zeichen muss dann als nächstes geschrieben werden.

So weit gut, nur im Moment passiert nichts, wenn Du als letztes eine 0 (1) gelesen hast und als nächstes wieder eine 0 (1) kommt. Fehlt also noch ein 00R (11R) beim Zustand 0 (1).

/Edit: Außerdem finde ich das recht willkürlich, ausgerechnet eine 0 an den freiwerdenden Bandanfang zu schreiben… aber Du meintest ja schon, die Aufgabenstellung sei ungenau.

Fehlt also noch ein 00R (11R) beim Zustand 0 (1).

Tsss, in der Kladde hatte ich die Übergänge noch drin. Danke [25]

[img]http://img218.imageshack.us/img218/2846/verschiebenkorrektoa9.jpg[/img]

Irre ich mich, oder wird mit letzterer TM der Nachfolger berechnet?
Und warum behandelt die TM Eingaben, die Einsen enthalten?
Da soll doch gar nicht akzeptiert werden, oder?

Man könnte das ganze mit einer NTM machen:
0,0,R                                                                           0,0,L .------.       0,#,R        .------.       #,#,L      .------.     #,#,L        .------.      #,#,H       .------. ||     | -----------------> |      | ---------------> |      | ---------------> |      | ---------------> |     || `------'                    `------'                  '------'                  '------'                  '------'   |        .------.                     .------.                .------.   `----->  |      | ----------------->  |      | -------------> |     || 0,0,R      `------'      #,#,L          `------'  0,0,L         `------' (die Beschriftungen an den Zustanden sollen für Kanten auf den Zustand selbst stehen.)

Irre ich mich, oder wird mit letzterer TM der Nachfolger berechnet?

Und gleich noch eine Aufgabe: der Bandinhalt soll um eins nach rechts geschoben werden.

Ist das so in Ordnung? Sprich: kann das Ergebniswort irgendwo auf dem Arbeitsband anfangen? Meine eigene Vermutung ist nein, denn q_0 w -*-> q_e v bedeutet ja, dass links vom Lesekopf nichts stehen darf. Richtig?

Interessant, das ist je nach Literatur anders. Laut "Theoretische Informatik" (Asteroth, Baier) darf links vom Kopf ruhig irgendwas stehen, das dann halt ignoriert wird.