Logo jkrieger.de section logo
invisible corner_top_left.gif
divider design elem. Home design elem.   design elem. Software design elem.   design elem. Links design elem.   design elem. Science design elem.   design elem. Photographie design elem.   design elem. everythingelse design elem.   design elem. eMail design elem.
divider_end corner_top_right
Verlauf

JKTuring 1.0

(c) 2002 by Jan Krieger, FREEWARE

 



Was sind Turing Maschinen?

Das Programm JKTuring 1.0 implementiert eine Turing-Maschine auf einem PC (MS Windows).

Alan Turing führte diese nach ihm benannten Maschien 1936 zum theoretischen Studium der Berechenbarkeit ein. Eine Turing-Maschine arbeitet auf einem einseitig unendlichen Band, das in unendlich viele Zellen an (n = 0, 1, 2, ...) aufgeteilt ist, die jeweils ein Wort aus dem verwendeten Alphabet E (z.B. E={1, 0} oder E={0, 1, X, Y} usw.) enthalten können. Die Maschine beginnt am Anfang des Bandes (Tape) mit ihrer Arbeit (a0). Die Maschine selber ist in einen festen ("Hardware") und einen variablen Teil ("Software" bzw. "Programm") aufgeteilt. Die Turing-Maschinen beschreiben also eigentlich eine ganze Klasse von Maschinen (unendlich viele!), weil das Programm, das nach bestimmten Regeln aufgebaut sein muss, unendlich lang und komplex sein kann. Den Aufbau einer Turing-Maschine zeigt die folgende Abbildung:



Die Maschine befindet sich zu jedem Zeitpunkt in einem definierten inneren Zustand Z. Zu Anfang ist dies der Startzustand Z*, der im Programm festgelegt wird. Sobald die Maschine mit ihrer Arbeit fertig geworden ist, befindet sie sich im Endzustand Z#, der ebenfalls im Programm definiert wird. Sie hört dann auf mit der Arbeit.

Ein Turing Maschine hat einen Schreib-/Lesekopf als einzige Hardware, der immer genau auf eine Zelle des Bandes am zeigt. Er stellt am Anfang eines Zykluses den Wert der Zelle unter ihm zur Verfügung und schreibt nach der Auswertung das Ergebnis an die selbe Stelle am des Bandes. Danach wandert er je nach Anweisung im Programm um eine Position nach rechts oder links. Zum Schluss geht die Maschine noch in einen neuen internen Zustand über.

Im Programm wird je nach innerem Zustand Z und gelesenem Wert am entschieden, was geschrieben werden soll und in welche Richtung sich der Schreib-/Lesekopf bewegen soll. Dabei muss immer etwas geschrieben werden und der Kopf muss sich immer bewegen (er kann also nicht stehen bleiben). Somit kann man ein Programm für eine Turing-Maschine als Tabelle schreiben, bei der jede Zeile genau einer Kombination von internem Zustand und gelesenem Wert entspricht. Der Ablauf eines solchen Zykluses wird in der folgenden Graphik leicht verständlich:



Hier ein beispiel für ein kleines Turing-Maschinen-Programm:
 

Zustand Eingabe Operation (Ausgabe, Verschiebung) Folgezustand Bemerkung
A 1 0,rechts A Anfangszustand Z*
  0 0,rechts B  
B       Endzustand Z#

Das Programm lässt sich auch als Graph darstellen und wird so leichter verständlich:

Das Programm besagt folgendes:

  • Zustand A ist der Anfangszustand der Maschine. Mit ihm beginnt die Ausführung.
  • Wenn sich die Maschine im Zustand A befindet und unter dem Schreib/Lesekopf eine "1" steht, dann schreibe eine "0" und gehe nach rechts. Bleibe im Zustand A.
  • Wenn sich die Maschine im Zustand A befindet und unter dem Schreib/Lesekopf eine "0" steht, dann schreibe eine "0" und gehe nach rechts. Gehe in den Zustand B (Endzustand) über.
  • Zustand B ist der Endzustand der Maschine und beendet die Ausführung.
Das Start-Tape zu diesem Programm könnte so aussehen:
 
1
1
1
1
1
1
1
1
0
0 ....

Auf diesem Tape würde das Programm alle "1" durch "0" ersetzen und bei der ersten "0" in den Endzustand übergehen und sich beenden.

Es gibt aber auch wesentlich komplexere Programme. Im Software-Paket JKTuring 1.0 ist etwa eines enthalten, dass eine "1"-Kette verdoppeln kann. Dies entspricht bei grundlegender Betrachtung der Mathematischen Rechenopertaion *2, wenn man Zahlen als ihrem Wert entsprechende Reihen von "1" darstellt.

Wie wir gesehen haben kann also eine Turing-Maschine von ganz einfachen Grundoperationen ausgehend, mit einem endlichen Programm viele Probleme lösen. Man muss das Problem nur in eine für die Maschine verständliche Form bringen und das Ergebnis der Maschine interpretieren können.

Wie JKTuring 1.0 zeigt ist es möglich eine Turing-Maschine auf dem PC zu simulieren. Viel beeindruckender ist jedoch, dass das umgekehrte ebenfalls möglich ist: Wenn das Programm nur genügend Koplex wird (es bleibt dabei aber immer noch endlich) kann man ohne weiteres einen PC auf einer Turing-Maschine simulieren! Dies besagt die sog. Church'sche These: Alles was man für intuitiv berechendbar hält kann man mit einer Turing-Maschine ausrechnen.

Intuitiv berechenbar heißt dabei, dass für ein Problem ein Lösungs-Algorithmus angegeben werden kann.


Beschreibung der Software:

Das Programm und der Anfangszustand des Tapes werden als Text in JKTuring eingegeben. Danach kann man die Maschine ihr Werk verrichten lassen. Über die rechte Maustaste können sowohl Programm, als auch Tape gespeichert und geladen werden.

Im unteren Teil des Fenster gibt es vier Buttons für die Bedienung der Programms und ein Eingabefeld, in das man ein Zeit-Intervall (in Millisekunden) eingeben kann, das zwischen zwei Zyklen der Maschine liegt.

Der aktuelle Zustand von Band und maschine wird ganz unten angezeigt.

Die Buttons haben folgende Bedeutung:

  • Reset: Setz die turing Maschine in den Ausgangszustand zurück und unterbricht die Ausführung.
  • Start: Startet die Turing-Maschine an Position 0 und im Startzustand. Die Zyklen werden automatisch ausgeführt.
  • Step: Führt einen einzelnen Zyklus aus.
  • Pause/Go on: Hält die Turing-Maschine an bzw. lässt sie weiterlaufen.



Eingabekonventionen für Programme:

Turing-Programme werden ähnlich wie in der Tabelle dargestellt eingegeben. Eine Tabellen-Zeile (also eine Kombination aus Zustand und gelesenem Wert) belegt genau eine Zeile des Programms. Die einzelnen Spalten werden dabei durch Tab-Stops getrennt. Es ist möglich Kommentare einzufügen. Diese beginnen immer mit dem Zeichen ";" und gehen bis ans Ende der aktuellen Zeile.

Ein Programm sieht folgendermaßen aus:

  • Zuerst wird der innere Zustand angegeben. Danach folgt (hinter einem Tab) die Eingabe. Nach einem weiteren Tab steht (durch "," -> Komma) getrennt die Ausgabe und die Richtung, in die sich der Kopf bewegen soll. Nach einem weiteren Tab folgt dann der Endzustand, in den übergegangen werden soll.
  • Kommentare dürfen ganze Zeilen belegen, oder hinter einer Befehlssequenz stehen.
  • Der Anfangszustand wird durch einen "*" (Asterisk/Stern) vor dem Zustandsbezeichner markiert.
  • Der Endzustand wird durch ein "#" (Doppelkreuz) vor dem Zustandbezeichner markiert. Er muss hinter dem Zustandsbezeichner keine weiteren daten enthalten (wie Eingabe, Ausgabe ...).
  • Der Bezeichner für einen Zustand und das Alphabet, das die Maschine benutzt dürfen aus beliebigen ASCII-Zeichen(folgen) bestehen. Nur die Zeichen ";", "#", "*" und der Tabulator dürfen nicht vorkommen.
Damit sieht das Programm zu obigem Beispiel wie folgt aus:
 
 
;Beispielprogramm: Löschen einer Kette aus dem Zeichen "1"

*1    1    0,rechts    1    ;Anfangszustand
1     0    0,rechts    2 
#2                          ;Endzustand


Links

 printable version Impressum
corner_top_right2
verlauf_right.gif
corner_bottom_left.gif corner_bottom_left2 Copyright (c) J. Krieger corner_bottom_right.gif
invisible
last updated: 18.06.2008
file: http://www.jkrieger.de/software/tools/jkturing.html
invisible