Home -> Themen -> Universelle TM


Turing-Werkstatt

Theoretische Informatik am PC


O.Pletsch 1862 Eine universelle Turing-Maschine

Eine universelle Turing-Maschine U kann wie ein Computer durch Eingabe unterschiedlicher Programme, unterschiedliche Aufgaben erledigen. Damit U die Aufgaben einer anderen Turing-Maschine M übernehmen kann, benötigt U die Befehlstafel TM von M und die Eingaben, die zum Start für M nötig sind. Startet man U mit diesen Eingaben so liefert U die Ergebnisse, die auch M liefern würde.

TM universell

Historische Anmerkung :
A. Turing beschreibt in seinem Artikel "ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM" von 1936 nach zwei einfachen Beispielen eine universelle Maschine U mit einem Band.

Beispiel : Universell.tm
Universell.tm ist eine Maschine mit drei Bändern, die die Arbeitsweise jeder Maschine mit einem Band simulieren kann. Da Maschinen mit drei Bändern nicht mehr können als solche mit einem Band, muss es auch eine Maschine Universell.tm mit einem Band geben.
Band 1  enthält die Befehlstafel von M in codierter Form :
     *Befehl1* Befehl2* --- * Befehl n*,
dabei hat ein Befehl das Format :
     Zustand '_' Zeichen Zeichen Bewegung Zustand.
Zustand bedeutet dabei die Zustandsnummer in unärer Form d.h. als Strichzahl.
Ein Befehl ( Z1 a : b R Z2 ) hätte die Übersetzung : II_abRIII.
Start am linken Rand von Band 1.
Band 2  enthält den Zustand von M in unärer Form. Start am linken Rand von Band 2 mit dem Anfangszustand von M.
Band 3  enthält dieselbe Belegung, die auch das Band von M beim Start hat.

Arbeitsweise von Universell.tm

Wiederhole
   suche auf Band1 einen passenden Befehl für M,
   wenn ein passender Befehl gefunden wurde, dann
         führe den Befehl aus,
         wenn der Befehl kein Stoppbefehl war, dann
              bereite die nächste Befehlssuche vor,
bis ein Stopp ausgeführt wurde oder kein Befehl passt.


Download aller Beispiele
zur Simulation mit Turing-Werkstatt.exe

Turing-Werkstatt,Teil3
In diesem Video bei Youtube wird Universell.tm in Aktion gezeigt und erklärt.

Hinweis :
Universell.tm hat bereits alle Eingaben zur Simulation der Maschine Plus1.tm, die in einer Endlosschleife eine Zahl in Dualschreibweise um 1 erhöht.
Bevor Sie Universell.tm laufen lassen, sehen Sie sich den Ablauf von Plus1.tm genauer an.
Beim Start von Universell.tm erscheint die Anfangskonfiguration :

Anfangskonfiguration

Die rote Markierung kennzeichnet den Befehl von Plus1.tm, der als nächstes abgearbeitet wird.
Universell.tm ist durch die Verwendung von Joker-Zeichen so allgemein formuliert, dass Turing-Maschinen mit einem Band simuliert werden können, die beliebige Bandsymbole verwenden mit Ausnahme der Joker-Zeichen.
Der Befehl von Universell.tm mit dem die Simulation eines Befehls von Plus1.tm beginnt ist mit '*' markiert. Stellen Sie den Sprungmodus für Universell.tm ein und aktivieren Sie die Marke '*'. Mit jedem Sprung sehen Sie dann wie ein Befehl von Plus1.tm bearbeitet wurde. Achten Sie dabei nur auf Band 3.

Übung :
Simulieren Sie andere Turing-Maschinen mit Universell.tm wie zum Beispiel mal2.tm.
Dazu müssen sie die Befehlstafel dieser Maschine kodieren und die Eingaben für die drei Bänder von Universell.tm machen.


Letzte Änderung : 4.9.2017