Auf den Spuren von Alan Turing
Das Problem der algorithmischen Lösbarkeit
Wann ist ein Problem algorithmisch lösbar? Man könnte es ganz einfach so formulieren:
Wenn es eine Verarbeitungsvorschrift gibt, die so präzise formuliert ist, dass sie auch von einer Maschine (also automatisiert) abgearbeitet werden kann.
Allerdings stellt sich dann sofort die Frage, was man unter "automatisiert" verstehen will bzw. welche Anfordungen eine Maschine erfüllen sollte, die (beliebige) Verarbeitungsvorschriften automatisiert abarbeiten kann.
Der britische Mathematiker Alan Turing versuchte diese Schwierigkeit zu lösen, indem er eine einfache Maschine als Rechner-Prototyp entwickelte. Diese Maschine - man nennt sie auch Turingmaschine - soll die Idee der algorithmischen Verarbeitung konkretisieren.
Bevor wir dieses Unterfangen beurteilen können, müssen wir uns erst einmal mit den Details beschäftigen.
Turing erfindet eine Rechenmaschine
Im Jahr 1936 veröffentlichte der britische Mathematiker Alan Turing die Arbeit On Computable Numbers, With an Application to the Entscheidungsproblem. Große Teile dieser Arbeit wirst du nicht verstehen können, da sie zu abstrakt und komplex sind. Nachvollziehbar sind allerdings seine Erläuterungen zur (automatisierten) Ausführung von Berechnungen in §9. Hier geht Turing der folgenden Frage nach: What are the possible processes which can be carried out in computing a number? Zur Klärung entwickelt Turing eine Maschine, die in der Lage sein soll, möglichst alle automatisierten Berechnungen ausführen zu können. Inwieweit das gelingt, werden wir in Abschnitt Church-Turing-These diskutieren. Zuerst folgen wir seinen Ausführungen.
Turing beginnt seine Ausführungen mit Überlegungen zum schriftlichen Rechnen.
Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book.
Eine Rechenmaschine soll also in der Lage sein, schriftliche Rechnungen nach bestimmten Regeln durchzuführen, so wie man es als Kind gelernt hat.
The behaviour of the computer at any moment is determined by the symbols which he is observing and his “state of mind” at that moment.
Die Rechenmaschine soll die Symbole erkennen können, die in den Feldern eines Rechenblatts abgelegt sind. Beachte, dass Turing hier beliebige Symbole zulässt und nicht nur Zahlsymbole. Zudem soll die Rechemaschine sich immer in einem bestimmten "Berechnungszustand" befinden.
We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at one moment.
Die Anzahl der Symbole, die auf dem Rechenblatt stehen können, soll endlich sein. Ebenso die Anzahl der Felder, die die Rechenmaschine zu einem bestimmten Zeitpunkt beobachtet.
Let us imagine the operations performed by the computer to be split up into “simple operations” which are so elementary that it is not easy to imagine them further divided. [...] The simple operations must therefore include: (a) Changes of the symbol on one of the observed squares. (b) Changes of one of the squares observed to another square within L squares of one of the previously observed squares.
Hier werden jetzt die Operationen festgelegt, die die Rechenmaschine ausführen können soll. Zum einen soll sie das Symbol des beobachteten Feldes des Rechenblatts austauschen können, zum anderen soll sie das beobachtete Feld wechseln können.
It may be that some of these changes necessarily involve a change of state of mind. The most general single operation must therefore be taken to be one of the following: A. A possible change (a) of symbol together with a possible change of state of mind. B. A possible change (b) of observed squares, together with a possible change of state of mind.
Zu beachten ist zudem, dass die oben beschriebenen Operationen einen Wechsel des Berechnungszustands erforderlich machen können.
Zur Verdeutlichung von Turings Ideen betrachten wir im Folgenden die Addition von Dualzahlen.
Aufgabe 1
Die Abbildung zeigt, wie man zwei Dualzahlem schriftlich addiert (hier 110 + 11). Man geht dabei völlig analog zur schriftlichen Addition im Zehnersystem vor.
(a) Berechne entsprechend 1011 + 110 sowie 1001 + 1111.
(b) Nach welchen Regeln bestimmt man für jede Stelle die Summe und den Übertrag? Wie geht man dabei schematisch vor?
Aufgabe 2
Wir benutzen einen Simulator, der im Browser läuft, zur Simulation von Turingmaschinen. Im linken Teil des folgenden Simulators steht ein Steuerprogramm für eine Turingmaschine. Im rechten Teil siehst du die Welt, in der die Turingmaschine arbeitet.
Drücke den Button mit dem Pfeil, um die Turingmaschine zu starten. Drücke anschließend mehrmals den Button vor. Beobachte genau, was passiert.
Analysiere anschließend das Steuerprogramm:
- Welche Bedeutung haben die Zustände
keine Ziffer, - Wie sind die Zustandsübergänge hier festgelegt?
0, 1, 0 0, 0 1 und 1 1?
(c) Lies dir noch einmal die Ausführungen von Turing durch (s.o.) und erläutere die Entscheidungen von Turing anhand der durchgeführten Simulation (zur Addition von Dualzahlen).
Aufgabe 3
Entwickle im Simulator unter dieser Aufgabe selbst Steuerprogramme für folgende Probleme:
(a) Eine 0-1-Folge soll invertiert werden. Z.B. soll aus der Folge 10011 die Folge 01100 erzeugt werden.
(b) Eine Dualzahl soll um 1 erhöht werden. So soll aus der Dualzahl 1010 die neue Zahl 1011, aus der Dualzahl 10111 die neue Zahl 11000 erzeugt werden.
Beachte, dass beide Probleme in einer eindimensionalen Welt gelöst werden können. Eine solche eindimensionale Welt kannst du im Bereich [Größe] festlegen.
Aufgabe 4
Zunächst stehen auf dem Band einige Nullen gefolgt von einigen Einsen.
Erstelle eine Turingmaschine, die feststellt, ob die Zeichenfolge aus gleich vielen Nullen und Einsen besteht.
Falls es sich um eine solche Zeichenkette handelt, soll die Turingmaschine ihre Arbeit mit einem leeren Band beenden.
Falls es sich nicht um eine solche Zeichenkette handelt, darf das Band am Ende nicht leer sein.
Aufgabe 5
Ein Palindrom ist eine Zeichenkette, die von vorne und von hinten gelesen gleich ist.
z.B.: "neben", "1001", "0001000"
Erstelle eine Turingmaschine, die für eine beliebige Zeichenkette aus Nullen und Einsen feststellt, ob sie ein Palindrom ist.
