Erklärung der Turingmaschine – Wie funktioniert sie?!

Erstellt am 4. Juni 2012 von Texblock

Die Imitationsmaschine schlechthin!

Mit der Turingmaschine bewies der britische Logiker und Mathematiker Alan Mathison Turing, dass jedes mathematische Problem zu lösen ist, sofern die Aufgabe auch mit einem Algorithmus lösbar ist. Dabei ist die Turingmaschine eines der grundlegenden Modelle der Informatik, ohne die kein einziger Computer oder jegliches Programm funktionieren könnte. Aber wie funktioniert diese Maschine und wie werden Zahlen berechnet?

Alan Mathison Turing beschreibt schon im Jahr 1935 in seiner Abhandlung »On Computable Numbers«, wie ein Computer als universelle Maschine funktioniert und mit welchen Faktoren Berechnungen erfolgen. Noch bevor er die Turingmaschine baute, simulierte er seine Idee mit einer Art »Papiermaschine« und demonstrierte so den Ablauf. Das Besondere an der Turingmaschine ist, dass jedes erdenkliche mathematische Problem gelöst und entziffert werden kann. So kam es sogar zu dem Ernstfall, dass Alan Mathison Turing mit seiner Maschine im zweiten Weltkrieg die Enigma-Verschlüsselung knacken konnte. Die Enigma-Verschlüsselung war eine Schlüsselmaschine, die das deutsche Militär einsetzte, um im Krieg ihre Botschaften verschlüsselt im Nachrichtenverkehr zu senden. Wenn so eine wichtige Verschlüsselung durch eine andere Maschine geknackt werden konnte, so kann die Turingmaschine auch jedes andere erdenkliche mathematische Problem lösen – ziemlich überwältigend! Man kann also sagen, dass diese Maschine jede andere Maschine imitieren und nahezu ersetzen kann.

Turingmaschine als menschliche Lebensform?

Wenn die Turingmaschine die Fähigkeit besitzt, Maschinen zu imitieren… kann sie dann auch als normaler Mensch durchgehen und »denken«? In einem philosophischen Aufsatz von 1950 schlägt Alan Mathison Turing die Lösung vor: Der so genannte Turing-Test. Es ist ein einfaches Imitationsspiel und funktioniert mithilfe von zwei Testpersonen sowie der Turingmaschine. Ein Mann und eine Frau spielen die Testpersonen, die sich in zwei unterschiedlichen Räumen befinden. Die Turingmaschine, die sich wiederum auch in einem anderen Raum befindet, stellt Fragen an beide Personen und muss anhand der Antworten herausfinden, ob es sich um eine männliche oder weibliche Person handeln muss. Anscheinend sind die Antworten eines Mannes bzw. einer Frau so eindeutig, dass eine Maschine diesen logischen Schritt selbst erdenken und nachvollziehen kann, um letztendendes zu wissen, ob ein Mann oder eine Frau hinter den Antworten steckt. Im zweiten Schritt wird der Fragesteller, also die Maschine, durch den Mann ersetzt, um die Fehlerquote der Antworten zu vergleichen.

Doch was verbirgt sich hinter diesem Test? Es soll eine Trennung zwischen den physischen sowie den intellektuellen Fähigkeiten finden. Allein durch die textliche Kommunikation soll bewiesen werden, dass die Turingmaschine, nicht durch das Lösen der Fragen, sondern vielmehr durch das Imitieren eines Geschlechtes durchaus die Fähigkeit hat, denken zu können.
Dieses Phänomen erleben wir selbst in unserem alltäglichen Leben, genauer gesagt im Internet auf sozialen Netzwerken! So nimmt die Turingmaschine den Platz des Internets ein und übernimmt die Kommunikation mittels Fernschreiber. Man denke da nur an die Partnervermittlungen auf Dating-Webseiten. Dabei ist auch das Imitieren ein beliebtes Spiel in Internet-Chatrooms. So berichtete das Magazin Stern im Jahr 1994, dass 60% der Chatter sich als lüsterne Frau ausgeben… in Wirklichkeit aber Männer sind. Die Strategie der Frau muss höchstwahrscheinlich das wahrheitsgetreue Antworten sein. Die Turingmaschine als Imitationsspiel für Lustmolche und das noch vor der Erfindung von Cybersex – entschuldigt diese Aussage…!

Nachdem wir nun so viel zur Turingmaschine erfahren haben, ist es sicherlich sehr spannend zu erfahren, wie die Turingmaschine in der Praxis funktioniert und wie mathematische Probleme berechnet werden. Zuerst schauen wir uns die einzelnen Komponenten der Maschine an, sie besteht aus:

  • einem Speicher für das Programm
  • Datenspeicher für Ein. und Ausgabedaten
  • Steuerwerk mit Schreib- und Lesekopf

Der Speicher der Turingmaschine merkt sich die Schritte, die ausgeführt wurden und auch als nächstes ausgeführt werden, es ist das »Gehirn« der Maschine. Der Datenspeicher ist im Grunde genommen ein endloses Band, das vom Steuerwerk beschriftet wird, typischerweise mit »0« oder »1«. Das Steuerwerk ist hierbei die Visualisierung der Berechnungen bzw. Aktionen für den Menschen. Schauen wir uns das mal in einem Beispiel an:

s0,0 s1,0>

Diese Operation ist sehr einfach: Wenn im Zustand »s0« nach dem Komma eine 0 gelesen wird, so soll die Turingmaschine in den Zustand s1 wechseln und das Steuerwerk um eine Position nach rechts verschieben. Warum ist das so? Die Zahl 0 repräsentiert eine 1, die Zahl 1 eine 2…

0=1, 1=2, 2=3, 3=4, 4=5, 5=6, 6=7, 7=8, 8=9 und so weiter

Im Beispiel steht nach dem Zustand »s0« eine 0. Da die Null für die Eins steht, wechsle ich in den Zustand, der eine »1« im Namen trägt, also eben »s1«. Der Zustand »s1« sagt jedoch aus, dass ich mich mit »Null«, also mit »Eins« nach rechts bewegen soll (> = rechts).
Das nächste Beispiel soll eine Rechenoperation darstellen, nehmen wir doch die Aufgabe 2 + 6. Die Turingmaschine wird diese Aufgabe wie folgt darstellen:

… 0111011111110…

Wir wir bereits gelernt haben, steht die »2« für die »3«, weswegen 3 Einsen zu sehen sind. Zwischen den Summanden steht stets eine 0, die die Zahl von der anderen trennt. Für die Sechs werden demzufolge sieben Einsen aufgeschrieben. Die Punkte vor und nach der Rechnung sollen lediglich darstellen, dass das Band weitergeht und unendlich ist – für Berechnungen also irrelevant.
Damit die Turingmaschine die Aufgabe nun berechnen kann, muss das Steuerwerk auf den Anfang der Rechnung zeigen, also auf die erste Eins (im Beispiel unterstrichen). Die Aufgabe für die Turingmaschine würde folgendermaßen lauten:

s0,1 s0,1,1> und s0,0 s1,1

Im Klartext bedeutet das: Im Zustand »s0« soll das Steuerwerk sich so lange nach rechts bewegen, solange eine »1« gelesen werden kann. Sobald die Maschine eine Null liest, wird in den nächsten Zustand gewechselt, der wiederum aussagt, dass die Null durch eine Eins ersetzt werden soll. Demzufolge bekommen wir folgendes Ergebnis:

…0111111111110…

Das Ergebnis unserer Aufgabe 2 + 6 lautet 8. Da die Acht für die Neun steht (siehe oben), bekommen wir als Ergebnis exakt 9 Einsen! Wenn man erstmal dahinter gekommen ist, versteht man die Rechenoperationen der Turingmaschine sehr schnell. Und wer sich das Ganze etwas bildhafter anschauen möchte, sollte sich mal folgendes Video näher anschauen, ziemlich gut gemacht: