Eine universelle Turingmaschine
Turingmaschinen als spezielle Verarbeitungssysteme
Wir haben Turingmaschinen bisher als spezielle Verarbeitungssysteme benutzt: Für jedes Problem wurde hierzu eine spezielle Turingmachine entwickelt.
Zur Verdeutlichung betrachten wir das Problem, eine 0-1-Zeichenfolge zu invertieren.
Beachte, dass das Ende der zu verarbeiten 0-1-Folge hier mit dem Symbol "#" gekennzeichnet ist.
Eine Turingmaschine zur Lösung dieses speziellen Problems lässt sich leicht konstruieren.
Aufgabe 1
Teste diese Turingmaschine.
Fachkonzept - universelle Turingmaschine
Haben wir mit der Turingmaschine als Berechnungsmodell tatsächlich das erfasst, was reale Computer im Kern ausmachen, wenn wir von bequemen Eingabe-, Ausgabe- und Speichermöglichkeiten einmal absehen?
Eine wesentliche Eigenschaft ist noch nicht erkennbar. Reale Computer sind programmierbare Systeme.
Sie sind in der Lage, beliebige vorgegebene Programme bei beliebig vorgegebenen Daten auszuführen. Sie sind also universell in dem Sinne, dass sie nicht nur für eine Aufgabe konzipiert sind, sondern zur Ausführung beliebiger Lösungsalgorithmen.
Ist das Berechnungsmodell Turingmaschine ebenfalls in der Lage, als programmierbares System zu fungieren? Es müsste dann eine "universelle Turingmaschine" existieren, die als eine Art Turingmaschinen-Interpreter arbeitet.
Eine universelle Turingmaschine besitzt die Fähigkeit, beliebige andere Turingmaschinen zu simulieren. Als Eingabe erhält sie die Beschreibung der zu simulierenden Turingmaschine und der Daten auf dem Eingabeband für diese Turingmaschine. Die universelle Turingmaschine erzeugt dann die Daten, die die zu simulierende Turingmaschine bei der Verarbeitung der übergebenen Daten erzeugen würde.
Aufgabe 2
Wenn man im Weltfenster von TuringKara die Schaltfläche [Aufgaben] anklickt, erhält man ein Auswahlmenu mit vielen Aufgaben, von leichten bis sehr schwierigen. Zu den sehr schwierigen gehört auch die Aufgabe "Die Universelle Turingmaschine".
(a) Wähle die Welt "Invertieren einer Zeichenkette" aus und führe das vorgegebene Steuerprogramm aus. Die Arbeitsweise dieser Turingmaschine ist zunächst etwas undurchsichtig. Aber mit etwas Geduld kann man doch einige Verhaltensmuster erkennen. Kannst du insbesondere nachvollziehen, in welcher Weise hier eine Zeichenkette invertiert wird?
(b) Lies dir jetzt auch die Hinweise unter "Codierung" durch. Hier erfährst du, wie eine (einfache) Turingmaschine auf dem zweidimensionalen Raster dargestellt wird.
(c) Wenn Du alles verstanden hast, dann solltest du in der Lage sein, eine (einfache) Turingmaschine zur Verdopplung einer Strichzahl mit der universellen Turingmaschine zu simulieren.
Eine universelle Turingmaschine
Es gibt sie tatsächlich, Turingmaschinen, die das Verhalten beliebig vorgegebener Turingmaschinen simulieren.
Die Abbildung zeigt ein mögliches Steuerprogramm. Dieses Programm ist auf die in der folgenden Abbildung gezeigte Codierung von Turingmaschinen (einschließlich des Bandes) zugeschnitten.
Beachte, dass die zu simulierenden Turingmaschinen hier einfache Einband-Turingmaschinen sein müssen, während die universelle Turingmaschine hier eine zweidimensionale Turingmaschine ist.
Man kann zeigen, dass es auch universelle Turingmaschinen in Form von einfachen Einband-Turingmaschinen gibt. der Nachweis ist aber recht aufwendig und soll daher hier nicht erbracht werden. Wir beschränken uns auf die Formulierung der fundamentalen Erkenntnis.
Satz (über die Existenz universeller Turingmaschinen)
Es gibt eine (einfache) Turingmaschine, die als universelle Turingmaschine jede andere (einfache) Turingmaschine simulieren kann.
Damit ist gezeigt, dass das Berechnungsmodell Turingmaschine so mächtig ist, dass es Programmierbarkeit zur Verfügung stellen kann. Die Turingmaschine ist damit trotz ihrer Einfachheit ein ernst zu nehmender Kandidat für die Präzisierung der "Idee Computer".
Ausblick
Wir wollen noch einen Schritt weiter gehen, indem wir folgende Frage aufwerfen: Ist das Berechnungsmodell Turingmaschine so mächtig, dass es alle denkbaren Algorithmen (in geeignet codierter Form) ausführen kann? Die Klärung dieser Frage wird uns im folgenden Abschnitt beschäftigen.