Kurze Einführung: Die Turing-Maschine

Ich befasse mich in meiner knappen Freizeit gerne mit esoterischen Programmiersprachen, wobei esoterisch nicht im Sinne von übersinnlich gemeint ist, sondern im Sinne von “theoretisch verwendbar”. Sie zeigen nur Möglichkeiten auf, die Programmiersprachen begehen können oder sind einfach nur ziemlich alt. Eine davon ist die Turing-Maschine.

Alan Turing war der Überzeugung das es möglich wäre jedes mathematische Problem, und sei es noch so schwierig, mit einer Maschine lösen zu können. Diese Idee einer Berechenbarkeitsmaschine, kurz Turing-Maschine genannt, hatte er bereits 1937. Aber erst nach dem zweiten Weltkrieg war es ihm möglich mit dem Bau zu beginnen. Leider scheiterte Turing bei der Verwirklichung an kleineren technischen Problemen, die sich aufsummierten und schließlich zur Einstellung des Projektes führte. Erst Jahre später, nach Turings Tod, wurde die Turing-Maschine zum ersten Mal gebaut.
In der Theorie funktionierte sie bereits zu Alans Lebzeiten, er konnte sie aber nie arbeiten sehen.
Die Turing-Maschine war in der Theorie der erste programmierbare Computer gleichzeitig mit Konrad Zuses Z1. Im wesentliche besteht Sie aus einem Endlosband mit Leerzeichen, $, 0, 1, x, y, und z die durch einen Lese und Schreibkopf verändert werden kann, eine Art Arbeitsspeicher, und dem eigentlichen Programm aufgeteilt in Register. Ein Leerzeichen wurde im Endlosband meistens mit einer # angegeben.

###1101#1xyz###

Zahlen, eine fünf z.B., konnten in zweierlei Methoden beschrieben werden. Entweder durch die Addition von einzelnen einsen, 11111, oder durch die heute bekannte Binäre Form, 101. Wir werden hier aber nur auf die von Turing gewählte Methode der Addition von einsen und nicht die binäre verwenden.
Ein Register bestand aus einem State, eine Art Sprungnummer, einem Read-Wert, einem Write-Wert, einem Move-Wert, der die Richtung des Lese-/ Schreibkopfes bestimmt und einem Goto-State das die nächste Sprungnummer angab.

Ein Register sah folgendermasen aus.

State	Read	Write	Move	Goto-State
0	x	y	R	1

Ein Register war nichts Anderes wie eine Art If-Anweisung die festlegte was geschehen sollte wenn der Lesekopf ein bestimmtes Zeichen las. Mehrere Register mit der selben Sprungnummer können bei unterschiedlich gelesene zeichen unterschiedlich Aktionen ausführen.
Das obige Register wird ausgeführt wenn das verwendete State 0 ist und am Lesekopf ein x anliegt. Der Schriebkopf soll daraufhin ein y schreiben und um eine Stelle nach Rechts fahren. Das nächste State ist dann 1.

Wie oben schon erwähnt können mehrere Register für ein und das selbe State vorhanden sein. Zum Beispiel:

State	Read	Write	Move	Goto-State
0	x	y	R	1
0	y	y	R	0

Liegt am Lesekopf ein x an wird das erste Register ausgeführt. Ist es ein y wird das zweite Register benützt. Wo der Lese/Schreibkopf anfängt ist eigentlich relativ egal, üblich ist eigentlich das er immer am ersten Zeichen ganz links steht.
Das Programm um eine Zahl im Endlosband um eins zu inkrementieren sieht so aus.

State	Read	Write	Move	Goto-State
0	1	1	R	0
0	#	1	L	h

State	Endlosband
0	 #<1>1 1 #
0	 # 1<1>1 #
0	 # 1 1<1>#
0	 # 1 1 1<1>
h	 # 1 1<1>1

Die eckigen Klammern geben die Position des Lese/Schreibkopfes an. Das Programm sucht in State 0 zunächst nach der ersten Leerstelle und schiebt den Lese/Schreibkopf solange nach Rechts bis es das erste Leerzeichen findet. Dieses überschreibt es dann mit einer 1 und übergibt dann an State h. Steht im Goto-State ein h bedeutet dies die Abbruchbedingung des Programms.

Eine Addition verläuft ähnlich einfach.

State	Read	Write	Move	Goto-State
0	1	1	R	0
0	#	1	R	1
1	1	1	R	1
1	#	#	L	2
2	1	#	L	h

State	Endlosband
0	<1>1 1 # 1 1 #
0	 1<1>1 # 1 1 #
0	 1 1<1># 1 1 #
0	 1 1 1<1>1 1 #
1	 1 1 1 1<1>1 #
1	 1 1 1 1 1<1>#
1	 1 1 1 1 1 1<#>
2	 1 1 1 1 1<#>#
h	 1 1 1 1<1># #

Im ersten State wird zunächst wieder die erste Leerstelle gesucht und mit 1 überschrieben, dann an State 1 übergeben. Im zweiten Teil des Programmes bewegt der Lese-/Schreibkopf sich nun an das Ende aller einsen, übergibt an das State 2 und schiebt den Lese-/Schreibkopf diesmal aber nach Links. Nun kann unter dem Lesekopf eigentlich nur noch eine 1 folgen die vom Register mit einer Leerstelle überschrieben wird und dann das Programm beendet.
Es werden also die Zahlen nicht wirklich miteinander addiert, sondern lediglich nur die Zwischenstelle entfernt und das Ende entsprechend gekürzt. Ein genialer Trick der auch nur wieder Informatikern einfallen kann. Jeder Mathematiker würde die Hände über dem Kopf zusammen schlagen. Aber da Turing selbst ein genialer Mathematiker war, ist diese Methode sozusagen abgesegnet. Schliesslich kommt es in der Informatik auf die Geschwindigkeit und Einfachheit besonders an. Beruhigend für die Mathermatiker wird es wohl sein das man es sich für die Subtraktion nicht mit einem Trick leicht machen kann und einfach zwei Stellen umändern um zum Ergebnis zu gelangen. Nein, wir benötigen sogar mehr als dreimal so viele Register wie für die Addition und verfahren wie einst in der Schule. Wir ziehen einen Apfel nach dem anderen voneinander ab.

State	Read	Write	Move	Goto-State
0	1	x	L	1
0	#	#	R	5
1	1	1	L	1
1	#	#	L	2
2	1	y	R	3
2	y	y	L	2
3	y	y	R	3
3	#	#	R	4
4	1	1	R	4
4	x	x	L	0
5	x	#	R	5
5	#	#	L	6
6	#	#	L	6
6	y	#	L	7
7	y	#	L	7
7	#	#	R	h
7	1	1	R	h

State	Endlosband
0	 1 1 1 # 1 1#
1	 1 1 1 # 1<1>x #
1	 1 1 1 #<1>1 x #
1	 1 1 1<#>1 1 x #
2	 1 1# 1 1 x #
3	 1 1 y<#>1 1 x #
4	 1 1 y #<1>1 x #
4	 1 1 y # 1<1>x #
4	 1 1 y # 1 1#
0	 1 1 y # 1x #
1	 1 1 y #<1>x>x #
1	 1 1 y<#>1 x x #
2	 1 1# 1 x x #
2	 1y # 1 x x #
3	 1 y# 1 x x #
3	 1 y y<#>1 x x #
4	 1 y y #<1>x x #
4	 1 y y # 1x #
0	 1 y y #x x #
1	 1 y y<#>x x x #
2	 1 y# x x x #
2	 1y # x x x #
2	y y # x x x #
3	 yy # x x x #
3	 y y# x x x #
3	 y y y<#>x x x #
4	 y y y #x x #
0	 y y y<#>x x x #
5	 y y y #<#>x x #
5	 y y y # #<#>x #
5	 y y y # # #<#>#
5	 y y y # # # #<#>
6	 y y y # # #<#>#
6	 y y y # #<#># #
6	 y y y #<#># # #
6	 y y y<#># # # #
6	 y y<#># # # # #
7	 y<#># # # # # #
7	<#># # # # # # #
h	 #<#># # # # # # 

Bei der Subtraktion müssen wir mit zwei Platzhaltern für die Einsen arbeiten die wir bereits voneinander subtrahiert haben. X für die Einsen des Subtrahend und y für die Einsen des Minuend, also der vorne stehenden Zahl von der wir abziehen. Wieder geben die eckigen Klammern die Stelle an, über dem der Lese-/Schreibkopf steht. Beim Start des Programmes steht der Lese-/Schreibkopf am Ende des Subtrahenden. Der Subtrahend ist vom Minuend durch eine Leerstelle getrennt. Der Subtrahend darf, nach Regel der natürlichen Zahlen, nicht größer sein als der Minuend . In State 0 stehen nun zwei Register. Eines für den Fall des Lesens einer 1, worauf ein Schreiben eines x folgt, und für den Fall des Lesens einer Leerstelle. Das letztere ist für das Einleiten des ‚Cleanup‘. Er ersetzt die Platzhalter x und y, die dafür sorgten das nicht zuviel und nicht zu wenig Subtrahiert wurden, und stoppt dann das Programm. Zum Schluss bleibt wie erwartet nur noch der Divident übrig. In unserem Fall 0.