\renewcommand{\reftextbefore}{auf der vorherigen Seite} \renewcommand{\reftextfacebefore}{auf der vorherigen Seite} \renewcommand{\reftextafter}{auf der nächsten Seite} \renewcommand{\reftextfaceafter}{auf der nächsten Seite} \renewcommand{\figurename}{Abbildung} \begin{figure*}[b] \begin{center} \includegraphics[width=0.5\textwidth]{2007-0304/turingmaschineabb}\\ \end{center} \caption{\label{turingmaschineabb}Der Aufbau einer Turing--Maschine} \end{figure*} \begin{document} \title{Ist Forth Turing–vollständig?} \author{Ulrich Hoffmann} \maketitle \begin{multicols}{2} \emph{Ist Forth Turing--vollständig?}\\ Diese Frage wirft Fred Behringer in seinem Artikel False Forth (Seite \pageref{falseforth}) auf. Nun --- um der Antwort näher zu kommen, müssen wir erstmal ein wenig darüber erfahren, was Turing--Maschinen sind und was eigentlich Turing--Vollständigkeit bedeuten soll. Anfang des 20. Jahrhunderts --- als es noch gar keine Computer gab --- haben sich viele Mathematiker Gedanken darüber gemacht, welche Aufgaben Maschinen wohl verrichten können würden bzw. an welchen sie prinzipiell scheitern müssten. Mathematiker fassten das exakt in die Fragestellung, welche mathematischen Funktionen von einem Automaten berechnet werden können und welche eben nicht. Heute sind diese Fragestellungen Teil der theoretischen Informatik (in der Komplexitätstheorie fragt man zusätzlich, wie aufwändig eine Funktion berechenbar ist). In diesem Zusammenhang hat der britische Mathematiker Alan Turing 1936 ein einfaches Modell --- die Turing--Maschine --- für einen universellen Automaten vorgeschlagen, der in der Lage ist, alle berechenbaren Funktionen auch tatsächlich auszurechnen. Damit war auch eine Möglichkeit gefunden, von einer gegebenen Funktion zu entscheiden, ob sie berechenbar ist oder nicht: Kann man ein Programm für die Turing--Machine schreiben, das die Funktion ausrechnet, so ist sie berechenbar. Kann man beweisen, dass kein Programm der Turing--Maschine die Funktion ausrechnet, so ist sie nicht--berechenbar. Eine Turing--Maschine stellt man sich am besten folgendermaßen vor: Sie ist ähnlich aufgebaut wie ein Tonbandgerät, dessen Magnetband in Felder eingeteilt ist. Auf jedem dieser Felder kann höchstens ein Zeichen stehen (es kann auch leer sein). Wie in Abbildung \vref{turingmaschineabb} zu sehen ist, besitzt die Turing--Maschine $M$ einen Schreib--/Lesekopf und sie kann nur das Feld beschreiben oder auslesen, das sich unter dem Magnetkopf befindet. Das Band kann in einem Schritt um ein Feld nach links oder rechts bewegt werden. Für die Turing--Maschine wird zusätzlich eine endliche Menge möglicher Zustände definiert. Zu jedem Zeitpunkt befindet sie sich in einem dieser Zustände. In einer Zustandsübergangstabelle $T$ (dem Programm der Maschine) wird mit jeder Zeile festgelegt, in welchem Zustand und bei welchem Zeichen unter dem Kopf sich die Maschine wie verhalten soll: welches Zeichen soll sie auf das Band schreiben, wie soll sie den Kopf bewegen und welches ist der Nachfolgezustand. \begin{figure*}[t] \begin{center} \begin{tabular}{l|l||l|l|l|l} Zustand $s$ & Eingabe $c$ & Ausgabe & Kopfbewegung & Folgezustand & Kommentar\\ \hline 0 & \verb'|' & \verb'|' & nach rechts & 0 & überspringe alle Striche\\ 0 & \verb'_' & \verb'|' & nach rechts & 1 & schreibe einen Strich in die Lücke\\ &&&&&\\ 1 & \verb'|' & \verb'|' & nach rechts & 1 & überspringe alle Striche\\ 1 & \verb'_' & \verb'_' & nach links & 2 & auf den letzten Strich \\ &&&&&\\ 2 & \verb'|' & \verb'_' & nach links & 3 & letzten Strich löschen, auf vorletzten\\ 3 & \verb'|' & \verb'_' & nach links & 4 & vorletzten Strich löschen\\ &&&&&\\ 4 & \verb'|' & \verb'|' & nach links & 4 & überspringe alle Striche rückwärts\\ 4 & \verb'_' & \verb'_' & nach rechts & 5 & auf den ersten Strich positionieren\\ \end{tabular} \end{center} \caption{\label{turingaddition}Die Zustandsübergangstabelle einer Turing--Machine, die zwei Strichzahlen addiert} \end{figure*} Zu Anfang erwartet die Turing--Maschine die Eingabe der auszurechnenden Funktion (kodiert) auf dem Band und startet in einem vereinbarten Anfangszustand $s_0$. Sie arbeitet nun Schritt für Schritt, bis die Tabelle für den schließlich erreichten Zustand (und Wert unterm Kopf) keine Aktion festlegt. Dann hält die Maschine an und das Band enthält das (kodierte) Ergebnis der Berechnung. Gerät die Turing--Maschine in eine Endlosschleife, hat sie ihr Ziel verfehlt und liefert kein Ergebnis. Um einen Schritt durchzuführen, geht die Maschine folgendermaßen vor: Sie befindet sich in einem Zustand $s$ und kann unter dem Kopf das Zeichen $c$ lesen. Die Tabelle bestimmt für $s$ und $c$ die Aktionen der Maschine: Sie schreibt das angegebene Zeichen, bewegt den Kopf in die angegebene Richtung und wechselt in einen neuen Zustand. Damit ist dieser Schritt beendet und die Maschine ist bereit für den nächsten Schritt. Die Turing--Maschine ist ein theoretisches Werkzeug, um die Berechenbarkeit von Funktionen zu untersuchen. Sie ist aus zwei Gründen unpraktikabel: erstens ist ihr Befehlsvorrat sehr primitiv: sie kann nicht einmal elementar Zahlen addieren und benötigt schon dafür ein Programm, wie etwa das in Abbildung \vref{turingaddition}. Zweitens fordert Turing, dass das Band seiner Maschinen unendlich groß ist, d.h. rechts wie links beliebig viele Felder zur Verfügung stehen. Eine solche Maschine kann man nicht bauen.\footnote{Das Band ist übrigens das einzige Unendliche an der Turing--Maschine, der Zeichenvorrat für die Band--Symbole, die Menge der Zustände und auch die Zustandsübergangstabelle sind endlich. Alles, was die Turing--Maschine von einem endlichen Automaten unterscheidet, ist also ihr beliebig großes Band.} Aber --- das ist ja auch gar nicht Sinn und Zweck einer Turing--Maschine. Gibt es eigentlich Funktionen, die Turing--Maschinen ausrechnen können, die aber von einfacheren Mechanismen (etwa einfachen Keller--Automaten) nicht berechnet werden können? Ja --- das sind die nicht--primitiv--rekursiven (aber µ--rekursiven) Funktionen, etwa die Ackermannfunktion. Gibt es eigentlich Funktionen, die Turing--Machinen nicht ausrechnen können? Ja --- das sind u.~a.\ spezielle Fragestellungen über das Verhalten von Turing--Maschinen selbst, insbesondere das so genannte \emph{Halteproblem}: Hält eine gegebene Turing--Maschine, gestartet auf einer Eingabe, nach endlich vielen Schritten an oder läuft sie unendlich lange weiter? Tatsächlich kann eine Turing--Maschine die Antwort auf diese Frage nicht ausrechnen (selbst nach endlich vielen Schritten immer das richtige Ergebnis liefern). Auch kein anderer bekannter Mechanismus kann diese Frage beantworten. In diesem Sinne ist die Turing--Maschine universell: sie berechnet alle berechenbaren Funktionen. Betrachtet man nun andere Mechanismen, etwa Programmiersprachen, dann stellt sich die Frage, ob diese die gleichen Funktionen berechnen, wie Turing--Maschinen. Ist das der Fall, spricht man davon, sie seien \emph{Turing--vollständig}. Eine Technik, diese Frage zu beantworten, versucht Turing--Maschinen mit Hilfe des betrachteten Algorithmus zu simulieren. Dabei geht man davon aus, dass beliebig viel Speicher zur Verfügung steht. Gelingt die Simulation allgemein, so kann man jede von einer Turing--Maschine berechenbare Funktion selbst berechnen, indem man die zugehörige Turing--Maschine simuliert. Ist Forth also Turing--vollständig? Um das zu beantworten, müssen wir also einen Turing--Maschinen--Simulator in Forth programmieren. Das ist nicht schwer und im Listing unten zu sehen. Prima --- Forth ist also Turing--vollständig. Und jetzt? Der angegebene Simulator verwendet das Dictionary, um das Band zu realisieren. Wie wäre es aber, wenn man kein Dictionary hätte und nur die beiden Forth--Stacks (beide beliebig groß)? Wäre dann immer noch ein Simulator möglich? \end{multicols} % \hfill Ulrich Hoffmann \vspace{1ex} \begin{small} \begin{quote} \listinginput[1]{1}{2007-0304/turing.fs} % \caption{\label{turinglisting}Ein einfacher Turing--Maschinen--Simulator in Forth} \end{quote} \end{small}