Andreas Rozek
[ Impressum ]   [ Datenschutzerklärung ]   [ Kontakt ]   [ ]

Turing-Maschine

Experimente mit einem Simulator für Turing-Maschinen

Keine Grundlagen-Vorlesung der Informatik kommt ohne eine Erwähnung der Turing-Maschine aus.

Martín Ugarte hat einen sehr schönen programmierbaren Simulator für Turing-Maschinen geschrieben, der Studenten einen ganz praktischen Zugang zu diesem ansonsten eher theoretischen Thema ermöglicht.

Falls Sie die Vorlesung "Grundlagen der Informatik" an der HFT Stuttgart hören, finden Sie hier neben den dort bereits erläuterten Beispielen weitere Programme zur Vertiefung der Thematik und für eigene Experimente.

Programmierung

Ein Programm für den Turing-Simulator besteht aus einem Vorspann und einer Serie von Definitionen für die Zustandsübergänge der Turing-Maschine.

Der Vorspann definiert den Progammnamen sowie die Namen des Initialzustandes und der "akzeptablen" Endzustände. Befindet sich die Turing-Maschine am Ende eines Programmes (d.h., wenn kein passender Zustandsübergang mehr gefunden werden kann) in einem der genannten Endzustände, gilt das Programm als "akzeptiert" (d.h. fehlerfrei durchgelaufen) - ansonsten ist ein Fehler aufgetreten.

name: Programmname
init: Name des Initialzustandes
accept: Name eines Endzustandes, ..., evtl. weitere Namen

Die Definition eines Zustandsüberganges besteht aus jeweils zwei Zeilen:

  1. die erste Zeile definiert den Namen des Zustandes und das Symbol, das vom Speicherband gelesen werden muss, damit der gerade zu definierende Zustandsübergang stattfinden kann
  2. die zweite Zeile legt den Namen des Zielzustandes fest, gibt das in die aktuelle Zelle des Speicherbandes zu schreibende Symbol vor und definiert, in welche Richtung der Schreib-/Lesekopf anschließend zu bewegen ist
Name des aktuellen Zustandes,zu lesendes Symbol (oder _ für eine leere Zelle)
Name des Zielzustandes,zu schreibendes Symbol,Bewegung des Schreib-/Lesekopfes

Folgende Bewegungen kann der Schreib-/Lesekopf ausführen

  • < - ein Feld nach links
  • > - ein Feld nach rechts
  • - - Verharren auf demselben Feld

Zeilen, die mit einem doppelten Schrägstrich beginnen, gelten als Kommentarzeilen und werden ignoriert. Leerzeilen werden ebenfalls übersprungen:

// Kommentarzeile

Vorgehensweise

Im einfachsten Fall wird der Programm-Quelltext in das Eingabefeld des Turing-Simulators eingetippt (oder dort hinein kopiert) und mit einem Klick auf die grüne "Compile"-Taste übersetzt.

Nach einer erfolgreichen Übersetzung erscheint die Bedienoberfläche des Simulators oberhalb des Eingabefeldes - anderenfalls wird dort der erste gefundene Übersetzungsfehler angezeigt.

Über die Bedienoberfläche lässt sich das Speicherband vorbelegen (mit je einem Zeichen pro Feld, wie links von "Load" eingegeben) und der Simulator steuern.

Nota bene: Sie müssen "Load" auch anklicken, wenn Sie das Speicherband nicht vorbelegen, sondern leer lassen wollen

Ein paar Beispiele für Turing-Programme

Zunächst sind die Beispiele noch trivial, werden jedoch sukzessive komplizierter. Spätere Beispiele bauen meist auf vorangehenden (einfacheren) auf.

  • ein (fast) leeres Programm (um Übersetzer und Simulator zu testen)
  • Überspringen einer einzelnen "0"
    Das Überspringen von Feldern auf dem Speicherband gehört zu den häufigsten Aktionen in Turing-Programmen
  • Überspringen aller folgenden "0"
  • Überspringen eines einzelnen Bit
    Ein "Bit" sei hier ein Feld auf dem Speicherband mit dem Inhalt "0" oder "1"
  • Überspringen aller folgenden Bits
  • Invertieren eines einzelnen Bit
  • Invertieren aller folgenden Bits
    Laden Sie das Speicherband mit einer Bitfolge (d.h. einer Folge von "0" und "1") und sehen Sie der Turing-Maschine dabei zu, wie sie diese Bit für Bit invertiert
  • Schreiben eines Paritätsbits
    Dies ist das Beispiel aus der Vorlesung: laden Sie das Speicherband mit einer Bitfolge (d.h. einer Folge von "0" und "1") und sehen Sie der Turing-Maschine dabei zu, wie sie ein Paritätsbit hinzufügt
  • Rechts-Schieben eines einzelnen Bit
  • Rechts-Schieben aller folgenden Bits
  • Links-Schieben eines einzelnen Bit
  • Links-Schieben aller folgenden Bits
    Dieses Beispiel ist keine spiegelbildliche Kopie des Programmes für ein Verschieben mehrerer Bits nach rechts, sondern arbeitet die Bitfolge ebenfalls von links nach rechts ab
  • Inkrementieren einer einstelligen Binärzahl
    Laden Sie das Speicherband mit einer einzelnen "0" oder "1", das Programm wird dieses Binärzahl um 1 erhöhen
  • Inkrementieren einer mehrstelligen Binärzahl
    Dieses Programm inkrementiert eine beliebige, auf das Speicherband geschriebene Binärzahl
  • Bilden des 2er-Komplementes für eine gegebene Binärzahl
    Laden Sie das Speicherband mit einer beliebigen Binärzahl und verfolgen Sie, wie die Turing-Maschine das 2er-Komplement dieser Zahl bildet
  • Bitweise konjunktive Verknüpfung zweier Bitfolgen
    Laden Sie das Speicherband mit zwei beliebigen (aber gleich langen) Bitfolgen und lassen Sie dazwischen genau ein Feld frei - im Turing-Simulator erreichen Sie dies durch einen Unterstrich ("_"), ein Leerzeichen wird als Eingabe nicht akzeptiert. Die Turing-Maschine wird hinter der zweiten Bitfolge eine bitweise konjunktive Verknüpfung Ihrer Eingaben auf das Band schreiben.
  • Bitweise disjunktive Verknüpfung zweier Bitfolgen
    Laden Sie das Speicherband mit zwei beliebigen (aber gleich langen) Bitfolgen und lassen Sie dazwischen genau ein Feld frei - im Turing-Simulator erreichen Sie dies durch einen Unterstrich ("_"), ein Leerzeichen wird als Eingabe nicht akzeptiert. Die Turing-Maschine wird hinter der zweiten Bitfolge eine bitweise disjunktive Verknüpfung Ihrer Eingaben auf das Band schreiben.
  • Addition zweier vorzeichenloser Binärzahlen
    Laden Sie das Speicherband mit zwei beliebigen (aber gleich langen) vorzeichenlosen Binärzahlen und lassen Sie dazwischen genau ein Feld frei - im Turing-Simulator erreichen Sie dies durch einen Unterstrich ("_"), ein Leerzeichen wird als Eingabe nicht akzeptiert. Die Turing-Maschine wird die Summe Ihrer Eingaben hinter der zweiten Zahl auf das Band schreiben - sofern die Anzahl der von Ihnen vorgegebenen Bits dafür ausreicht.
    Das Programm geht dabei etwas anders vor als Sie es von der Vorlesung her gewohnt sind: die beiden Zahlen werden bitweise von links nach rechts aufsummiert und evtl. Stellenüberträge sofort eingepflegt - auf diese Weise kann ein finaler Überlauf u.U. schon recht früh während der Berechnung erkannt werden.
  • Addition zweier vorzeichenloser Binärzahlen (nach Coors)
    Falls Sie meine Vorlesung "Grundlagen der Informatik" hören, finden Sie in den Folien von Prof. Coors ein anderes Turing-Programm zur Addition von Binärzahlen.
    1. Wandeln Sie das Zustandsdiagramm aus den Folien von Prof. Coors in ein Programm für den Simulator um
      Nota bene: das Programm von Prof. Coors startet die Addition mitten auf dem Speicherband (was im Allgemeinen vollkommen zulässig ist). Damit der Simulator damit jedoch etwas anfangen kann, muss der Schreib-/Lesekopf durch folgende Anfangszeilen erst an diese Position bewegt werden:
      qPre,0
      qPre,0,>

      qPre,1
      qPre,1,>

      qPre,_
      q1,_,>
      Der neue Anfangszustand ist also nicht mehr q0, sondern qPre
    2. Testen Sie das Programm mit der Eingabe "1001_100"
      (wie führt das Programm die Addition durch?)

Fleissige Biber

Turing-Maschinen werden vor allem für theoretische Betrachtungen genutzt - in der Praxis haben sie keinerlei Bedeutung.

Eine bekannte Fragestellung lautet: wieviele "1" kann eine Turing-Maschine mit n Zuständen maximal auf ein anfangs mit lauter "0" gefülltes Speicherband schreiben und anschließend anhalten(!)?

Turing-Programme, die diese Bedingung erfüllen, heißen "fleissige Biber".

Die Lösung für ein Turing-Programm mit nur einem Zustand ist offensichtlich:

Abb. 18: Zustandsdiagramm für einen "fleissigen Biber" mit einem Zustand
Abb. 18: Zustandsdiagramm für einen "fleissigen Biber" mit einem Zustand

Nachstehend finden Sie die Beispiele für "fleissige Biber" mit bis zu sechs Zuständen. Die beiden letzten Programme gelten nur als "Kandidaten" für einen "fleissigen Biber", weil sie aufgrund ihrer immensen Laufzeit nicht mehr praktisch getestet werden können.

Die ersten vier Beispiele lassen sich jedoch auch im Simulator noch gut ausprobieren.

  • "fleissiger Biber" mit einem Zustand
  • "fleissiger Biber" mit zwei Zuständen
  • "fleissiger Biber" mit drei Zuständen
  • "fleissiger Biber" mit vier Zuständen
  • Kandidat für einen "fleissigen Biber" mit fünf Zuständen
  • Kandidat für einen "fleissigen Biber" mit sechs Zuständen