computerfeld robert grübel / cfinf

Dabei seien c1, ..., cM verschiedene natürliche ZahIen >=0 und c'j Elemente aus {c1, ..., cM}
für j=1, ..., MN+M. Ferner soll jedes vj ein Element von {a0, ..., aN, r, l, s} sein.

Wir können eine Turingmaschine mit ihrer Tafel identifizieren.

DefEnde

Die Turingmaschine ist ein typisches akademisches Spielzeug - überhaupt nicht verspielt, sondern grau in grau und kochentrocken. Der englische Mathematiker Alan Turing hat sie 1936 zur Untersuchung von Fragen der "Berechenbarkeit" entwickelt. Turing hat mit dieser Maschine die Zerlegung von Algorithmen in einfach Operationen bis an die Grenze getrieben - bis fast nichts mehr übrig blieb. Allerdings gelang es ihm damit herauszufinden, daß man alles, was man überhaupt berechnen kann, mit dieser Maschine berechnen kann. Die Maschine hat sich so als eines der mächtigsten Instrumente der Mathematik erwiesen.

Die obige Definition der Turingmaschine ist zwar mathematisch korrekt, für den Hausgebrauch aber eher ungeeignet, weil irgendwie unhandlich - und man sieht auch nicht so richtig wirklich richtig eine Maschine...

Deshalb verwendet man besser folgende Darstellung:

Eine Turingmaschine besteht aus
1. dem Rechenband (Endlosband),
2. dem Register und
3. dem Lese/Schreibkopf.

Wenn man das Alphabet der Maschine noch auf A={+, 1} beschränkt (mit "+" als dem leeren Symbol), dann erhält man:

Auf dem Rechenband können - entsprechend dem Alphabet A={+, 1} - die Symbole "+" oder "1" vorkommen. Der Schreib-/Lesekopf (der Pfeil) zeigt immer eindeutig auf eines dieser Symbole (auf ein Feld des Rechenbandes). Das Register enthält die Arbeitsvorschrift, das "Programm", für die Maschine. Es setzt sich aus einzelnen "Karten" zusammen, die wiederum jeweils aus einer Matrix mit 2 Zeilen und 4 Spalten bestehen. Jede Karte gibt für einen "Rechenschritt" an, wie der Schreib-/Lesekopf sich verhalten soll und mit welcher Karte das Programm weitergeht.
Die Zeile "+,1,L,2" auf der Karte 1 des obigen Bildes bedeutet z.B., daß, wenn unter dem Schreib-/Lesekopf eine "+" steht, ein "1" geschrieben, der Schreib-/Lesekopf nach links wandern und das Programm mit Karte 2 fortfahren soll. Die Zeile "+,+,R,3" (Karte 2) sagt dem entsprechend: wenn "+" gefunden wird, "+" schreiben, nach rechts gehen und mit Karte 3 fortfahren.

Vereinbart man, daß Zahlen als Folgen des Zeichens "1" dargestellt werden, "111" also z.B. gleich 3 oder "1111111"=7 ist, dann kann man mit der Maschine wirklich rechnen. Folgendes Programm z.B. addiert 1 zu einer beliebigen Zahl:

1
1	1	R	1
+	1	L	2

2
1	1	L	2
+	+	R	3

3
1	1	S	3
+	+	S	3

Programm Pinc

Also, wenn "111" auf dem Rechenband steht, dann steht nach Ablauf des Programms "1111" da (wir nennen das Progamm Pinc, weil es eine beliebige Zahl um 1 inkrementiert). Ein weiters Programm:

1
1	1	R	1
+	1	R	2

2
1	1	R	2
+	+	L	3

3
1	+	L	4
+	+	S	3

4
1	1	L	4
+	+	R	5

5
1	1	S	5
+	+	S	5

Programm Padd

Hier werden zwei Zahlen addiert, wenn also auf dem Rechenband "1111+111" steht, also eine 4 und eine 3, dann steht nach Programmablauf "1111111" da, also 7. (Beachten Sie bitte, daß das "+"-Zeichen hier nicht die Addition bedeutet, sondern das leere Zeichen repräsentiert!)

Kehrt man zurück zur obigen Definition der Turingmaschine, dann würde man das Programme Pinc so notieren:

1
1
2
2
3
3

1
+
1
+
1
+

R
1
L
R
S
S

1
2
2
3
3
3

Maschine Minc

und gemäß der Definition wäre das eine Turingmaschine M, identifiziert durch ihre Tafel. Wir wollen sie - entsprechend dem Programm Pinc - Minc nennen.

Die c1,..., cM entsprechen den Nummern der Registerkarten, die a0,..., aN den Symbolen aus dem Alphabet (hier nur "+" und "1"). Die v1 bis vMN+M sind die Vorschriften, ein bestimmtes Zeichen zu Schreiben, den Schreib-/Lesekopf nach links/rechts zu schieben oder ihn stehen zu lassen. Die c'1,... , c'MN+M sind die jeweiligen Nummern der Registerkarten, mit denen weitergemacht werden soll.
ACHTUNG: Die Definition sieht nicht vor, daß ein neues Zeichen geschrieben und gleichzeitig der Schreib-/Lesekopf verschoben wird, deshalb entsprechen sich die beiden zweiten Zeilen aus Programm und Maschine nicht! Im Programm steht "+, 1, L, 2", bei Minc steht jedoch "1, +, 1, 2". Während im ersten Fall also "+" gelesen, "1" geschrieben und der Kopf nach links geschoben wird, wird im zweiten Fall nur "+" gelesen und "1" geschrieben. Minc funktioniert aber trotzdem genauso wie das Programm.
Das gilt nicht für das Programm Padd, hier muß man ein bißchen knobeln und einen zusätzlichen Programmschritt einfügen. Wir geben hier ohne weiteren Kommentar "die Lösung" an:

1
1
2
2
3
3
4
4
5
5
6
6

1
+
1
+
1
+
1
+
1
+
1
+

R
1
R
L
+
S
L
L
L
R
S
S

1
2
2
3
4
3
4
5
5
6
6
6

Maschine Madd

Diese Tafel identifiziert eine weitere Turingmaschine, die wir Madd nennen.

Wenn Sie sich jetzt brennend für Turingmaschinen interessieren, gibt es hier weitere Informationen.


Informatik	Webdesign	Lösungen	über uns	Kontakt	Home