Zwei Turingmaschinen |
| 30.05.2016, 08:33 | Enigma2 | Auf diesen Beitrag antworten » |
| Zwei Turingmaschinen [attach]41836[/attach] Was tut die linke Turingmaschine, wenn man sie auf ein Band voller Nullen ansetzt? Und was tut die rechte Turingmaschine, wenn man sie auf die folgenden Startmuster ansetzt: (a) ....00001110000.... (b) ....000011110000.... (c) ....0000111110000.... (d) ....000012110000.... (e) ....000011221210000.... (f) ....000011221210010000.... Meine Ideen: Lässt sich das Verhalten in nur einem Satz beschreiben? |
||
| 30.05.2016, 11:49 | HAL 9000 | Auf diesen Beitrag antworten » |
Die Maschine rechts sieht ja recht einfach aus: Sie schreibt immer das gerade gelesene Symbol, d.h. ändert den Bandinhalt nicht, und geht immer nach rechts, Bei 1 wechselt sie von A nach B und zurück, bei 0 in Zustand B stoppt sie. Zusammenfassend, wenn ich mal annehme dass die Maschine in Zustand A startet: Das Band wird nach rechts gehend solange abgeklappert, bis man eine Null findet unter der Zusatzbedingung, dass auf dem Weg bis dahin eine ungerade Anzahl Einsen lag. Die Maschine stoppt dann genau eine Position rechts der Null. Das links sieht schon ein ganzes Stück komplizierter aus, da sowohl Bandänderungen als auch Links-/Rechtsbewegungen stattfinden. Einfach mal durchexerzieren, bis man ein "Muster" sieht. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |