Kleines Nachschlagewerk Informatik
Gekoppelte Turingmaschinen
Worum geht es?
Man sieht, dass Turingmaschinen recht schnell sehr komplex werden können. Da sich aber gewisse Teile wiederholen, kann man diese auch zusammen fassen.

Man definiert also kleine Turingmaschinen, die nur ganz spezielle Aufgaben erldigen. Komplexere maschinben setzt man aus diesen Turingmaschinen zusammen.

Eckart Modrow entwickelte dazu auch eine Sprache, mit der sich diese Maschinen sehr kompakt aufschreiben lassen.
Basismaschinen
Folgende elementaren Basismaschinen lassen sich definieren:





Die Einsmaschine, sie schreibt eine 1 und macht sonst nichts.





Die Nullmaschine, sie schreibt eine 0 und macht sonst nichts.





Die Rechtsmaschine, sie geht eine Position nach rechts und lässt sonst alles unverändert.





Die Linksmaschine, sie geht eine Position nach links und lässt sonst alles unverändert.





Die Prüfmaschine, sie kann verzweigen.

Nicht mehr elementar, aber ganz sinnvoll, sind Maschinen, die solange nach links oder rechts gehen, bis eine Null kommt.







Modrows Sprache GT
Zur Abkürzung verwendet Eckart Modrow in seinem Buch "Theoretische Informatik mit Delphi" und auch in den VLIN-Materialien folgende Sprache, welche die Elementarmaschinen mit je einem Buchstaben beschreibt: Folgende Maschine schreibt drei Einsen auf das Band:

      1r1r1
            
Es lassen sich die Maschinen, die den linken oder rechten Rand eines Einserblocks suchen, nun so beschreiben:





Eine Maschine, von links kommend einen Bloick Einsen löscht, sieht dann so aus: