Das eindimensionale

Universum

Einführung in ein informationstheoretisches Weltbild

von

André Betz

Ausgabe 1, 2003

ISBN 3 - 8330 - 0370 - 7

Titelbild: http://hubblesite.org/

2

1. EINLEITUNG 3

2. WAS HAT MEIN COMPUTER MIT MATHEMATIK ZU TUN? 5

3. KOCHREZEPTE UND MINIMALISTISCHE MASCHINEN 10

4. FLEISSIGE TIERE 13

5. DIE ALLESKÖNNER 16

6. ICH BAUE MIR MEINE EIGENE CPU 26

6. ICH BAUE MIR MEINE EIGENE CPU 26

7. DER RIESE MIT DEM KLEINEN ALPHABET 47

8. KLEIN ABER FEIN 53

9. DER UNBESTIMMTE PFAD 62

10. DER AUTOMAT IN UNSEREM KOPF 71

11. DAS UNIVERSUM ALS TURING-MASCHINE 82

12. MACH ES NOCH MAL, FRED! 92

13. WIEVIEL WIEGT EINE INFORMATION? 95

14. ZUSAMMENFASSUNG 97

ANHANG 98

LITERATURVERZEICHNIS 112

3

1. Einleitung

Computer haben in den letzten Jahrzehnten zunehmend unseren

Alltag erobert. Es gibt fast keinen Beruf mehr ohne den berüchtigten

PC und kaum ein Hobby, in dem der Computer nicht auch seinen

Platz findet, selbst wenn es nur um die Verwaltung der einzelnen

Lokomotiven der eigenen Sammlung geht. Die Vielseitigkeit dieser

Maschine wird in Zukunft noch weitere Bereiche erschließen.

Doch was macht einen Computer so vielseitig, so universal

einsetzbar? Genau diese Universalität ist es, die mich mein Leben

lang fasziniert hat. Ich wollte schon immer wissen, welche

grundlegenden Strukturen ein Apparat benötigt, um eine solche

Vielfältigkeit zu erreichen.

In den Folgenden Kapiteln möchte ich zeigen, dass es möglich ist

unsere Welt durch ein informationstheoretisches System zu erklären.

Dabei will ich nicht so sehr in die Beschreibung von physikalischen

Vorgängen eingehen, sondern vielmehr dem Ganzen eine andere

theoretische Grundlage verleihen. Die Grundlage beruht auf einem

einfachen Maschinenmodell, nämlich der Turing-Maschine und ihrer

Artverwandten.

Zunächst stelle ich den Zusammenhang zwischen der Sprache der

Mathematik und die eines Computers her und gehe im nächsten

Kapitel auf die Erklärung der Turing-Maschine ein. Danach zeige ich

die Grenzen ihrer Fähigkeiten und führe den Begriff der universalen

Maschine ein. Da es oft einfacher ist, formale Dinge in einer

4

Computersprache zu beschreiben, zeige ich, dass ein Computer und

eine Turing-Maschine sehr ähnlich sind und nur unterschiedliche

Sprachen sprechen. Nach einem kurzen Ausflug in die Effizienz und

Universalität der Computer stelle ich in den darauffolgenden Kapiteln

weitere Automatenmodelle vor, die die Weltanschauung eines

räumlich eindimensionalen Universums erhärten sollen (Die Zeit wird

nicht als eine Raumdimension angesehen). Dabei zeige ich jeweils,

dass diese Modelle zur Turing-Maschine äquivalent sind.

Hinter jedem Kapitel steckt ein riesiges Forschungsfeld und ich habe

hier nur das wesentliche herausgenommen. Dabei habe ich versucht,

alles sehr einfach zu halten, musste aber dabei auf Tiefe verzichten.

Doch mein Ziel, einen kurzen Überblick über diese Themen zu geben,

hoffe ich, damit erfüllt zu haben. Zum besseren Verständnis sollte der

Leser zumindest schon einige Erfahrungen im Programmieren

gesammelt haben.

Für die Realisierung dieses Buches danke ich meiner Freundin Sylvia

für ihr Verständnis und Hilfe bei der deutschen Sprache, die mir als

Informatiker doch so manche Fallen gestellt hat. Weiterhin möchte

ich Ingo Schasiepen für die logische Korrektur danken. Ohne ihn

würden doppelt so viele logische Fehler enthalten sein. Da ein Buch

meistens genauso viele Fehler umfasst, wie ein Programm, bin ich

jedem Leser dankbar, der einen findet und ihn mir zusendet

(mail@andrebetz.de) .

Oberengstringen, Mai 2003

André Betz

5

2. Was hat mein Computer mit Mathematik zu tun?

Um diese Frage zu beantworten, muss zunächst geklärt werden, was

ein Computer überhaupt ist. Grundlegend besteht ein Computer aus

einem Speicher, in dem sich Symbole befinden, die als Bits

dargestellt sind. Die Symbole werden von einem Prozessor gelesen

oder von ihm in den Speicher geschrieben. Der Prozessor verarbeitet

diese Symbole. Wie die Symbole verarbeitet werden oder welche

Bedeutung das aktuell gelesene Symbol für den Prozessor hat, ergibt

sich aus dem momentanen Arbeitszustand, in dem sich der Prozessor

befindet. Aus der Kombination des Symbols und des Zustands

berechnet der Prozessor ein Ergebnis, das in den Speicher

geschrieben wird, und wechselt gegebenenfalls in einen anderen

Arbeitszustand. Was berechnet wird und welcher Arbeitsschritt als

nächstes folgt, ist durch die Schaltung und das Programm des

Prozessors definiert.

Ähnlich verhält es sich mit der Mathematik, denn Grundlage der

Mathematik ist die Symbolverarbeitung. Symbole stellen zum

Beispiel die in der Mathematik verwendeten Zahlen dar, wohingegen

Variablen den Speicher versinnbildlichen. Die Funktionen geben die

Hardware des Prozessors wieder. Während ein Computer in einer

Programmiersprache wie zum Beispiel Assembler programmiert

wird, werden Funktionen in einer mathematischen Schreibweise

definiert. Beide Sprachen sind somit äquivalent, das heißt, dass man

in beiden Sprachen das Gleiche ausdrücken beziehungsweise

6

berechnen kann (Beispiele dafür sind verschiedene algebraische

Systeme auf dem Computer, wie Maple oder Mathematica). Aus

diesem Grund handelt es sich bei der Mathematik und einer

Computersprache um nichts anderes als zwei unterschiedliche

formale Systeme, mit denen sich dieselben Dinge ausdrücken lassen.

Doch was kann man alles mit einer formalen Sprache beschreiben

oder anders ausgedrückt, was kann mit einem Computer

programmiert werden, wenn man über genügend Speicherkapazität

verfügt?

Um die Antwort gleich vorweg zu nehmen: Es kann auf einem

Computer alles programmiert werden, was es in diesem Universum

gibt. Die Speicherkapazität stellt die einzige Begrenzung dar. Doch

um die Frage genauer erörtern zu können, müssen zwei Begriffe

geklärt werden, die mit diesem Thema in Zusammenhang stehen.

Zum einen handelt es sich um den Begriff der universalen Maschine

und zum anderen um den Begriff der Berechenbarkeit.

Unter einer universalen Maschine versteht man zum Beispiel einen

Computer, der durch seine Schaltung in der Lage ist, andere

universale Maschinen zu simulieren oder, alle Funktionen berechnen

kann, die überhaupt berechenbar sind. Eine Programmiersprache

heißt zum Beispiel Turing-vollständig, wenn sie ebenfalls diese

Funktionen berechnen kann. Anstatt alle berechenbaren Funktionen in

dieser Programmiersprache zu implementieren, reicht es aber aus,

damit eine Maschine zu beschreiben, die alles, nämlich die Turing-

Maschine. Diese etwas umformulierte These ist unter dem Namen

7

Church-Turing-These bekannt geworden. Geht man davon aus, dass

ein Computer eine universale Maschine ist (abgesehen vom

begrenzten Speicher), so kann auf ihr jeder andere Computer

nachgebildet werden. Dies erklärt auch, warum es möglich ist, durch

PC-Emulatoren einen Computer auf einem anderen nachzuahmen.

Darüber hinaus können, mit einem Computer mathematische

Funktionen beschrieben werden. Vergleichbar mit einem Computer

als universale Maschine sind die in der Mathematik bekannten µ-

rekursiven Funktionen, mit deren Hilfe ein Computer in einem

mathematischen System ebenfalls abgebildet werden kann.

Der Frage, was alles mit einer universalen Maschine berechnet

werden kann, geht die Berechenbarkeit nach. Noch bis ins 19.

Jahrhundert hinein haben Mathematiker geglaubt, dass jedes

mathematische und damit auch programmierbare Problem gelöst

beziehungsweise bewiesen werden kann.

An einem Beispiel möchte ich verdeutlichen, was überhaupt ein

Beweis im mathematischen Sinne ist. Nehmen wir an, jemand wohnt

in Nürnberg und will mit ihrem Auto nach München fahren. Er fragt

sich, ob es einen Weg gibt, der diese beiden Orte miteinander

verbindet. Die Person weiß nur, dass Straßen von Nürnberg nach

Ingolstadt (N→I), Nürnberg nach Augsburg (N→A), Augsburg nach

Ulm (A→U), Ingolstadt nach Regensburg (I→R), Ulm nach

München (U→M), München nach Garmisch-Parteenlirchen (M→G)

und Regensburg nach Passau (R→P) existieren.

8

Um zu zeigen, dass es eine Möglichkeit gibt, von Nürnberg nach

München zu kommen, muss ein zusammenhängender Weg gefunden

werden. Die einzige Möglichkeit, die hier existiert, ist die Verbindung

von Nürnberg über Augsburg und Ulm nach München

(N→A→U→M) . Somit hat man bewiesen, dass es einen Weg gibt,

der aus den bestehenden Wegstrecken abgeleitet werden kann. Dabei

sind die einzelnen Verbindungsabschnitte sogenannte grundlegende

Verbindungen, die nicht weiter beweisbar sind und auch Axiome

genannt werden. Der Mathematiker Gödel hat aber gezeigt, dass jedes

vollständige formale System nicht widerspruchsfrei ist. Ist aber ein

System doch widerspruchsfrei, so ist es nicht vollständig. Anders

ausgedrückt, kann eine universale Maschine niemals alle wahren

mathematischen Aussagen beweisen. Da der Computer ebenfalls ein

formales System ist, gilt dies auch für ihn.

Zusammenhang von Logik und Axiomen

Die Grundlage jedes mathematischen Systems sind Axiome. Diese

entsprechen bei einem Computer den grundlegenden Befehlen.

Deshalb kann man auch ein Programm als einen Art Beweis für ein

Logik

Axiome

Mathematisches System

9

Problem ansehen. Viele Befehle einer Programmiersprache lassen

sich durch Kombination weniger Befehle meist rekonstruieren. Dies

zeigt, dass nicht alle Befehle unbedingt notwendig sind, sondern

einige existieren nur, um die Programmierung etwas einfacher zu

gestalten. Doch wenn man wissen möchte, was eigentlich einen

Computer ausmacht, dann muss man eine minimalistische Menge von

Befehlen suchen, mit denen sich alle anderen beschreiben lassen. In

der Mathematik entspricht dies der Suche nach den grundlegenden

Axiomen eines Systems.

10

3. Kochrezepte und minimalistische Maschinen

Alan Turing [1] entwickelte für seine Arbeit über die

Entscheidungsprobleme einen genauen Begriff des Algorithmus. Ein

Algorithmus ist im Prinzip nichts anderes als ein Kochrezept, das

dem Koch in endlichen, eindeutigen, in jeder Küche ausführbaren und

allgemein verständlichen Schritten erklärt, wie etwas gekocht wird.

Auf einem Computer entspräche dies einem Programm. Damit alle

Algorithmen in eine einheitliche Sprache übersetzt werden, hat

Turing eine Maschine definiert, die aus nur wenigen wesentlichen

Sprachelementen besteht. Die Maschine liest Zeichen von einem

Eingabemedium und schreibt Zeichen auf ein Ausgabemedium, und

zwar nur endlich viele, da der Algorithmus endlich ist.

Die Lese- und Schreibzeichen stammen also aus einer endlichen

Menge X. Im Prinzip kann die Maschine auf das gleiche Medium

schreiben, von dem es liest. Das Medium ist in einzelne Felder

aufgeteilt, die jeweils nur ein Zeichen aufnehmen können. Eine

eventuelle zweidimensionale Anordnung der Felder zum Beispiel auf

einem Bildschirm, kann auf eine Dimension (ein eindimensionales

Band) reduziert werden. Um die Ausgabe nicht zu beschränken,

können bei Bedarf an beiden Enden weitere Felder angefügt werden.

Das Medium ist also ein potentiell unendlich langes Arbeitsband, das

von einem Lese-/Schreibkopf abgetastet wird. Die Felder des

Mediums können mit beliebigen Symbolen aus der Menge X

vorbelegt sein.

11

Prinzipieller Aufbau einer Turing-Maschine

Der Algorithmus lässt sich in eine Folge elementarer Operationen

auflösen:

1. Lesen und Beschreiben eines einzelnen Feldes

2. Verschieben des Lese-/Schreibkopfes nach links oder rechts

Welche Operation die Maschine ausführt, kann von

Zwischenergebnissen abhängen, d.h. sie verfügt über ein Gedächtnis.

Zu jedem Zeitpunkt wird ihr daher ein innerer Zustand zugeordnet.

Da der Algorithmus endlich ist, benötigt die Maschine nur eine

endliche Zustandsmenge Z. Darin müssen genau ein Anfangszustand

und mindestens ein Endzustand ausgezeichnet sein. Ein besonderer

Zustand ist der Haltezustand. Geht sie in diesen Zustand über, dann

hält die Maschine an. Die Arbeitsschritte 1 und 2 werden folglich so

lange ausgeführt, bis sie anhält. Parallel zu Programmiersprachen ist

dies die einzige existierende Schleife, und sie beinhaltet auch nur eine

Abbruchbedingung, nämlich die Endbedingung, um in diesen

Endzustand zu gelangen.

Da der Algorithmus eindeutig ist, muss die Maschine zu jedem

Zeitpunkt wissen, welche Operation als nächste auszuführen ist. Das

bedeutet, dass sie in Abhängigkeit vom momentanen Zustand q und

L L1 0 x 1 0 0 y 1 0 0

q

Band

Kopf

12

dem gelesenen Zeichen p einen Arbeitsschritt ausführt, indem sie das

gelesene Zeichen durch p' überschreibt, in den Nachfolgezustand q'

übergeht und den Lese-/Schreibkopf z um ein Feld nach links (L)

oder nach rechts (R) bewegt. Ein solcher Arbeitsschritt lässt sich

formal durch eine Übergangsfunktion beschreiben: f(q ,p)→(q', p’, z),

wobei z = {L, R} ist.

Übergangsfunktion f dargestellt als Graph f(q,p) → (q’,p’,z)

Jeder Algorithmus ist nichts anderes als eine Turing-Maschine, da sie

aus Abfolgen von grundlegenden Befehlen aufgebaut sind, genau wie

Turing-Maschinen auch. Turing-Maschinen können in verschiedenen

Varianten auftreten. Sie können aus mehreren Bändern und mehreren

Köpfen aufgebaut sein oder besitzen ein nur einseitig beschränktes

Band, ein Alphabet aus zwei Zeichen oder nur zwei Zustände. Doch

all diese unterschiedlichen Konfigurationen sind äquivalent und

erweitern nicht die Fähigkeit der Turing-Maschine.

q q' (p, p’, z)

13

4. Fleissige Tiere

Mit Hilfe dieser Sprachelemente von Turing ist es möglich,

Vorgehensweisen zu beschreiben. Doch es gibt auch Dinge, für die

man kein Verfahren kennt oder keines existiert, oder zumindest kein

Verfahren, das effizient genug ist, in absehbarer Zeit mit einer

Lösung anzuhalten. Ein Beispiel dafür sind die fleißigen Biber. Dabei

handelt es sich um kleine Turing-Maschinen, die mit nur wenigen

Zuständen ein leeres Turing-Band mit endlich vielen Einsen

vollschreiben. Der fleißigste Biber einer Klasse mit gleicher Anzahl

der Zustände, ist derjenige, der die meisten Einsen auf das Band

schreibt, bevor er anhält.

f(0,0)→(1,1,R) F(0,1)→(2,0,R)

f(1,0)→(0,1,L) F(1,1)→(0,1,R)

f(2,0)→(H,1,R) F(2,1)→(3,1,R)

f(3,0)→(3,1,L) F(3,1)→(1,0,L)

Beispiel für einen Biber mit 4 Zuständen

Will man herausfinden, ob ein Biber nun der fleißigste ist, so stößt

man auf ein Problem. Es müssten nicht nur alle Kombinationen von

0 1

(1,1,R) (0,1,L)

2 3

(0,1,R)

(1,1,R)

(1,0,L) (1,0,R)

H (0,1,R) (0,1,L)

14

Zuständen und Zeichen einer Biber-Klasse ausprobiert werden,

sondern es kann darüber hinaus auch nicht gesagt werden, ob ein

Biber überhaupt irgendwann anhalten würde. Es existieren garantiert

in jeder Klasse Biber, die unendlich viele Einsen schreiben würden,

aber es besteht kein Entscheidungsverfahren hierfür. Dies wird auch

als das Halteproblem bezeichnet.

Doch das Halteproblem ist noch viel tiefgreifender. Es gilt nicht nur

für Biber-Programme, sondern es kann auch nicht entschieden

werden, ob andere komplexe Maschinen anhalten oder nicht. Turing

hat diesen Zusammenhang bewiesen, indem er versucht hat, von

einem Widerspruch auszugehen. Er nahm an, dass entschieden

werden kann, ob ein Programm hält oder nicht. Angenommen, es

existiert eine Turing-Maschine H(P,x).

Programm H( Programm P, Eingabe x)

{

Wenn P(x) anhält gebe „Ja“ aus, sonst „nein“

}

Programm S( Programm P, Eingabe x)

{

Solange H(P,x) „Ja“ zurückliefert

{

wiederhole diese Schleife

}

}

Beweis des Halteproblems in Pseudocode

H(P,x) liefert „ja“ zurück, falls ein beliebiges Programm P bei

beliebiger Eingabe x anhält, ansonsten „nein“. Außerdem gibt es ein

Programm S(P,x). Es enthält eine Schleife, in der H so lange

wiederholt wird, bis das ihr übergebene Programm P bei der Eingabe

x anhält. Setzt man nun P und x gleich S und übergibt dies der

15

Funktion S, so ergibt sich ein Widerspruch. Liefert H(S,S) = ‚Ja’

zurück, so läuft S in einer Endlosschleife. Ist H(S,S) = ‚Nein’, so

endet das Programm S. Anders ausgedrückt hält S nur dann an, wenn

es nicht anhalten würde.

1.) S(S,S) hält => H(S,S) sagt ‚Ja’ => S(S) hält nicht (Widerspruch)

2.) S(S,S) hält nicht => H(S,S) sagt ‚Nein’ => S(S) hält

(Widerspruch)

In beiden Fällen ergibt sich ein Widerspruch. Folglich existiert keine

Turing-Maschine H. Diese Tatsache hat auch Auswirkungen auf die

Informatik. Es wird nie ein Programm geben, das andere Programme

auf ihre Richtigkeit hin überprüfen kann, sobald es unendlich viele

Möglichkeiten der Eingabe zulässt. Eng verwandt mit dem

Halteproblem ist der Unvollständigkeitssatz von Gödel, der besagt,

dass es in einem vollständigem axiomatischen System wahre

Aussagen gibt, die nicht bewiesen werden können. Würde man dieses

System erweitern, so wäre es nicht mehr vollständig. Dieses Problem

hängt insofern mit dem Halteproblem so zusammen, als unlösbare

Probleme dadurch zu erkennen sind, dass sie als Algorithmus nicht

anhalten würden. Dies stellt Mathematiker vor eine Schwierigkeit,

denn es können mathematische Formulierungen existieren, die nicht

bewiesen werden können. Lange Zeit galt ja auch Fermat’s Letzter

Satz als wahr, aber unbeweisbar. Ob ein Programm hält, ist eine

unüberprüfbare Aussage. Sie kann wahr sein, aber kann nicht für alle

Programme bewiesen werden.

16

5. Die Alleskönner

Bis auf die genannte Einschränkung kann auf einer Turing-Maschine

alles simuliert (beschrieben) werden, was auch auf anderen

Maschinen läuft und berechenbar ist. Jede Maschine für sich stellt ein

eigenes Universum dar, man könnte sogar fast behaupten, dass unser

Universum auch nichts anderes ist als eine riesige Turing-Maschine.

Somit stellen die Turing-Maschine und alle zu ihr äquivalenten

Maschinen universelle Maschinen dar.

Da eine Turing-Maschine selbst universell sein soll, reicht es aus,

eine Beschreibung für eine universelle Turing-Maschine (UTM) auf

einer Turing-Maschine TM zu finden. In der folgenden Tabelle ist

eine solche Maschine dargestellt. Anstatt für jeden Übergang eine

Funktion zu schreiben, können die Transitionen (Übergangsfunktion)

tabellarisch auch gargestellt werden. Dabei bedeuten die Spalten das

Alphabet und die Zeilen die Zustände.

Der folgende Automat UTM [2] stellt ein solches universelles

Programm dar. Dabei arbeitet UTM auf dem Eingabeband B. Dieses

ist unterteilt in M und Z, wobei Z die Eingabe von M ist. Funktionell

lautet das Ganze dann UTM(B) = UTM(ZM) = UTM(M(Z)).

0 1 a b x y

00 00 a L 00 b L 00 a L 00 b L 00 x L 01 y R

01 01 0 R 01 1 R 02 0 R 04 1 R 06 x R

02 03 a L 05 b R 02 a R 02 b R 02 x R

03 03 0 L 03 1 L 03 a L 03 b L 03 x L 01 y R

17

04 05 a R 03 b L 04 a R 04 b R 04 x R

05 05 0 R 05 1 R 05 a R 05 b R 00 x L H y R

06 07 a L 08 b L 06 a R 06 b R 06 x R

07 07 0 L 07 1 L 07 a L 07 b L 07 x L 09 y R

08 08 0 L 08 1 L 08 a L 08 b L 08 x L 10 y R

09 11 a R 11 a R 09 a R 09 b R 12 x L

10 11 b R 11 b R 10 a R 10 b R 13 x L

11 11 0 R 11 1 R 11 a R 11 b R 06 x R

12 12 0 L 12 1 L 12 a L 12 b L 14 a R 12 y L

13 13 0 L 13 1 L 13 a L 13 b L 14 b R 13 y L

14 14 0 R 14 1 R 14 0 R 14 1 R 15 x R 14 y R

15 16 0 L 16 1 L 15 a R 15 b R 15 x R 15 y R

16 17 x R 18 x L 16 0 L 16 1 L 16 x L 16 y L

17 17 0 L 17 1 L 20 0 L 19 0 R 17 x L 17 y L

18 18 0 L 18 1 L 20 1 L 19 1 R 18 x L 18 y L

19 21 x R 22 x R

20 21 x R 22 x R

21 21 0 R 21 1 R 21 a R 21 b R 00 a L 21 y R

22 22 0 R 22 1 R 22 a R 22 b R 00 b L 22 y R

Transitionstabelle der UTM

Das Band B hat eine bestimmte Struktur, die die UTM verstehen

kann. Der erste Grobaufbau lautet also Z y R x M y. Die einzelnen

Transitionen von M befinden sich jeweils in einem Segment; die

Segmente sind miteinander durch ein x voneinander getrennt sind.

Jeder Befehl f(a,b)→(c,d,e) wird in einem Segment in der

Reihenfolge abcde abgelegt. Dabei besteht das endliche Alphabet von

b und d aus 0 und 1. Die Zustände a und c sind binär codiert, und die

Länge des Zustandes muss immer gleich sein. Bei der

18

Richtungsangabe e für den virtuellen Kopf steht eine 1 für rechts und

eine 0 für links.

Obwohl das Alphabet nur aus Null und Eins besteht, schränkt es die

Mächtigkeit gegenüber anderen Maschinen mit mehr Symbolen in

keiner Weise ein. Vergleichbar wäre diese Situation mit der

Darstellung von Zahlen. Man kann binär genauso viele Zahlen

darstellen wie mit Dezimalzahlen.

H

02

01

04 03

05

(0,0,R)

(1,1,R)

(a,0,R)

(b,1,R)

(y,y,R)

(0,a,L)

(1,b,L)

(1,b,L)

(0,a,L)

(x,x,L)

(y,y,R)

(a,a,R)

(b,b,R) (x,x,R)

(a,a,R)

(b,b,R) (x,x,R)

(0,a,R)

(1,b,R)

(a,a,R) (b,b,R)

(0,0,L)

(1,1,L)

(a,a,L)

(b,b,L) (x,x,L)

19

(0,0,R)

(1,1,R)

(a,0,R)

(b,1,R) (y,y,R)

(0,0,L)

(1,1,L)

(a,a,L)

(b,b,L) (y,y,L)

08 07

06

10 09

12 13

11

14

(x,a,R)

(x,b,R)

(0,0,R)

(1,1,R)

(a,a,R) (b,b,R)

(0,0,L)

(1,1,L)

(a,a,L)

(b,b,L) (y,y,L)

(x,x,L)

(x,x,L)

(0,a,R)

(1,a,R)

(0,b,R)

(1,b,R)

(y,y,R) (x,x,R)

(y,y,R)

(a,a,R)

(b,b,R)

(a,a,R)

(b,b,R)

(a,a,R)

(b,b,R)

(x,x,R)

(0,0,L)

(1,1,L)

(a,a,L)

(b,b,L) (x,x,L)

(0,0,L)

(1,1,L)

(a,a,L)

(b,b,L) (x,x,L)

(0,a,L)

(1,b,L)

(x,x,R)

01 (0,0,R)

(1,1,R)

20

Graphische Darstellung der UTM

(0,0,R)

(1,1,R)

(a,a,R)

(b,b,R) (y,y,R)

(0,0,L)

(1,1,L)

(x,x,L) (y,y,L)

(0,a,L)

(1,b,L)

(a,a,L)

(b,b,L) (x,x,L)

00

22 21

(x,a,L)

(x,b,L)

(0,0,R)

(1,1,R)

(a,a,R)

(b,b,R) (y,y,R)

19 20

(1,x,R)

(0,x,R)

(1,x,R)

(0,x,R)

18 17

(b,1,R)

(a,0,L)

(b,0,R)

(a,1,L)

(0,0,L)

(1,1,L)

(x,x,L) (y,y,L)

16

(a,0,L)

(b,1,L)

(x,x,L) (y,y,L)

(0,x,L)

(1,x,L)

15

(0,0,L)

(1,1,L)

(a,a,R)

(b,b,R)

(x,x,L) (y,y,L)

(y,y,R)

(x,x,R)

14

(0,0,R)

(1,1,R)

(a,0,R)

(b,1,R) (y,y,R)

01

(0,0,R)

(1,1,R)

21

Dabei befindet sich am Anfang das gelesene Zeichen zusammen mit

dem aktuellen Zustand schon im Zwischenspeicher, während der

Kopf von der UTM am Ende des Zwischenspeichers R steht. Der

virtuelle Kopf von M wird auf dem Eingabeband Z durch ein x

dargestellt.

Bei der Codierung unserer Beispielmaschine M ergibt sich folgendes

Problem: Wenn bei einer Transition der Haltezustand auftritt, hält die

Maschine sofort an und arbeitet nicht noch die weiteren Anweisungen

der Transition ab. Deshalb muss unsere Beispielmaschine M etwas

modifiziert werden, und zwar indem ein zusätzlicher Haltezustand

hinzugefügt wird. Da dies aber weniger anschaulich wäre, lasse ich

die Maschine der Einfachheit halber danach wieder von vorne

anfangen. Außerdem würde die komplette Betrachtung der

Abarbeitung dieser Maschine 1381 Schritte benötigen, was zu

umfangreich wäre, denn zum Verständnis der Funktionsweise reicht

die Besprechung einer einzigen Transition vollkommen aus.

Weiterhin besitzt die UTM kein eigenes Symbol für einen

Haltezustand. Dieser wird einfach durch eine nichtexistente

Transitions-Nummer realisiert.

f(0,0)->(0,0,R) 00001

f(0,1)->(1,1,R) 01111

f(1,0)->(0,1,R) 10011

f(1,1)->(1,1,R) 11111

Codierung der Beispielsmaschine M für UTM

Das Band Z ist am Anfang leer (000x000) und der Zwischenspeicher

enthält den Startzustand Null sowie das gelesene Zeichen Eins.

Zunächst beginnt die Maschine, die Zeichenkette ab im

22

Zwischenspeicher mit der Zeichenkette ab in M zu vergleichen, um

dadurch die passende Transition zu finden. Dabei markiert sie den

schon verglichenen Teil ab der Segmente. Markieren heißt hier, dass

die Symbole 1 und 0 durch a und b ersetzt werden. Diese

Suchfunktion befindet sich in den Zuständen 0 bis 5.

f(00,x)→(00,x,L) 11x1100y01x00001x01111x10011x11111y0

f(00,1)→(00,b,L) 11x1100y01x00001x01111x10011x11111y0

f(00,0)→(00,a,L) 11x1100y0bx00001x01111x10011x11111y0

f(00,y)→(01,y,R) 11x1100yabx00001x01111x10011x11111y0

f(01,a)→(02,0,R) 11x1100yabx00001x01111x10011x11111y0

f(02,b)→(02,b,R) 11x1100y0bx00001x01111x10011x11111y0

f(02,x)→(02,x,R) 11x1100y0bx00001x01111x10011x11111y0

f(02,0)→(03,a,L) 11x1100y0bx00001x01111x10011x11111y0

f(03,x)→(03,x,L) 11x1100y0bxa0001x01111x10011x11111y0

f(03,b)→(03,b,L) 11x1100y0bxa0001x01111x10011x11111y0

f(03,0)→(03,0,L) 11x1100y0bxa0001x01111x10011x11111y0

f(03,y)→(01,y,R) 11x1100y0bxa0001x01111x10011x11111y0

f(01,0)→(01,0,R) 11x1100y0bxa0001x01111x10011x11111y0

f(01,b)→(04,1,R) 11x1100y0bxa0001x01111x10011x11111y0

f(04,x)→(04,x,R) 11x1100y01xa0001x01111x10011x11111y0

f(04,a)→(04,a,R) 11x1100y01xa0001x01111x10011x11111y0

f(04,0)→(05,a,R) 11x1100y01xa0001x01111x10011x11111y0

f(05,0)→(05,0,R) 11x1100y01xaa001x01111x10011x11111y0

Dieses Vergleichen geht solange weiter, bis die passende Stelle

gefunden worden ist.

f(01,b)→(04,1,R) 11x1100y0bxaaaabxa1111x10011x11111y0

f(04,x)→(04,x,R) 11x1100y01xaaaabxa1111x10011x11111y0

f(04,a)→(04,a,R) 11x1100y01xaaaabxa1111x10011x11111y0

f(04,a)→(04,a,R) 11x1100y01xaaaabxa1111x10011x11111y0

f(04,a)→(04,a,R) 11x1100y01xaaaabxa1111x10011x11111y0

f(04,a)→(04,a,R) 11x1100y01xaaaabxa1111x10011x11111y0

f(04,b)→(04,b,R) 11x1100y01xaaaabxa1111x10011x11111y0

f(04,x)→(04,x,R) 11x1100y01xaaaabxa1111x10011x11111y0

f(04,a)→(04,a,R) 11x1100y01xaaaabxa1111x10011x11111y0

f(04,1)→(03,b,L) 11x1100y01xaaaabxa1111x10011x11111y0

f(03,a)→(03,a,L) 11x1100y01xaaaabxab111x10011x11111y0

23

Danach beginnt die Maschine. den neuen Zustand c in den

Zwischenspeicher R zu kopieren, und markiert ihn im Segment. Das

geschieht in den Zuständen 6 bis 11.

f(06,1)→(08,b,L) 11x1100y01xaaaabxab111x10011x11111y0

f(08,b)→(08,b,L) 11x1100y01xaaaabxabb11x10011x11111y0

f(08,a)→(08,a,L) 11x1100y01xaaaabxabb11x10011x11111y0

f(08,x)→(08,x,L) 11x1100y01xaaaabxabb11x10011x11111y0

f(08,b)→(08,b,L) 11x1100y01xaaaabxabb11x10011x11111y0

f(08,a)→(08,a,L) 11x1100y01xaaaabxabb11x10011x11111y0

f(08,a)→(08,a,L) 11x1100y01xaaaabxabb11x10011x11111y0

f(08,a)→(08,a,L) 11x1100y01xaaaabxabb11x10011x11111y0

f(08,a)→(08,a,L) 11x1100y01xaaaabxabb11x10011x11111y0

f(08,x)→(08,x,L) 11x1100y01xaaaabxabb11x10011x11111y0

f(08,1)→(08,1,L) 11x1100y01xaaaabxabb11x10011x11111y0

f(08,0)→(08,0,L) 11x1100y01xaaaabxabb11x10011x11111y0

f(08,y)→(10,y,R) 11x1100y01xaaaabxabb11x10011x11111y0

f(10,0)→(11,b,R) 11x1100y01xaaaabxabb11x10011x11111y0

f(11,1)→(11,1,R) 11x1100yb1xaaaabxabb11x10011x11111y0

Im nächsten Schritt wird das zu schreibende Zeichen d auf die gleiche

Art in den Zwischenspeicher R gebracht.

f(06,1)→(08,b,L) 11x1100yb1xaaaabxabb11x10011x11111y0

f(08,b)→(08,b,L) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(08,b)→(08,b,L) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(08,a)→(08,a,L) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(08,x)→(08,x,L) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(08,b)→(08,b,L) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(08,a)→(08,a,L) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(08,a)→(08,a,L) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(08,a)→(08,a,L) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(08,a)→(08,a,L) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(08,x)→(08,x,L) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(08,1)→(08,1,L) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(08,b)→(08,b,L) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(08,y)→(10,y,R) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(10,b)→(10,b,R) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(10,1)→(11,b,R) 11x1100yb1xaaaabxabbb1x10011x11111y0

f(11,x)→(08,x,R) 11x1100ybbxaaaabxabbb1x10011x11111y0

Nun wird die Bewegungsrichtung des virtuellen Kopfes der

simulierten Maschine M auf das Band Z kopiert, und zwar an die

Kopfposition. Der Ablauf ist in den Zuständen 12 bis 16 festgehalten.

24

f(06,1)→(08,b,l) 11x1100ybbxaaaabxabbb1x10011x11111y0

f(08,b)→(08,b,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(08,b)→(08,b,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(08,b)→(08,b,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(08,a)→(08,a,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(08,x)→(08,x,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(08,a)→(08,a,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(08,x)→(08,x,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(08,b)→(08,b,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(08,b)→(08,b,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(08,y)→(10,y,r) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(10,b)→(10,b,r) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(10,b)→(10,b,r) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(10,x)→(13,x,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(13,b)→(13,b,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(13,b)→(13,b,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(13,y)→(13,y,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(13,0)→(13,0,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(13,0)→(13,0,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(13,1)→(13,1,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(13,1)→(13,1,l) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(13,x)→(14,b,r) 11x1100ybbxaaaabxabbbbx10011x11111y0

f(14,1)→(14,1,r) 11b1100ybbxaaaabxabbbbx10011x11111y0

Nach der Aufhebung der Markierung der Segmente von M wird das

zu schreibende Symbol d, das sich noch im Zwischenspeicher R

befindet, an die mit der Richtungsangabe markierte Position auf dem

Band Z kopiert. Diese Funktion ist in den Zuständen 17 bis 22

beschrieben.

f(16,1)→(18,x,L) 11b1100y11x00001x01111x10011x11111y0

f(18,1)→(18,1,L) 11b1100y1xx00001x01111x10011x11111y0

f(18,y)→(18,y,L) 11b1100y1xx00001x01111x10011x11111y0

f(18,0)→(18,0,L) 11b1100y1xx00001x01111x10011x11111y0

f(18,0)→(18,0,L) 11b1100y1xx00001x01111x10011x11111y0

f(18,1)→(18,1,L) 11b1100y1xx00001x01111x10011x11111y0

f(18,1)→(18,1,L) 11b1100y1xx00001x01111x10011x11111y0

f(18,b)→(19,1,R) 11b1100y1xx00001x01111x10011x11111y0

f(19,1)→(22,x,R) 1111100y1xx00001x01111x10011x11111y0

Am Schluss wird der virtuelle Kopf auf die nächste Position gesetzt,

das Zeichen dort gelesen und in den Zwischenspeicher R übertragen.

25

Danach beginnt die ganze Prozedur wieder von vorne mit dem neuen

Zustand a und dem gelesenen Symbol b.

f(18,b)→(19,1,R) 11b1100y1xx00001x01111x10011x11111y0

f(19,1)→(22,x,R) 1111100y1xx00001x01111x10011x11111y0

f(22,1)→(22,1,R) 111x100y1xx00001x01111x10011x11111y0

f(22,0)→(22,0,R) 111x100y1xx00001x01111x10011x11111y0

f(22,0)→(22,0,R) 111x100y1xx00001x01111x10011x11111y0

f(22,y)→(22,y,R) 111x100y1xx00001x01111x10011x11111y0

f(22,1)→(22,1,R) 111x100y1xx00001x01111x10011x11111y0

f(22,x)→(00,b,L) 111x100y1xx00001x01111x10011x11111y0

f(00,1)→(00,b,L) 111x100y1bx00001x01111x10011x11111y0

26

6. Ich baue mir meine eigene CPU

Doch wer sagt mir, dass eine Turing-Maschine wirklich alles kann,

wozu mein Computer fähig ist? Im Folgenden will ich eine Turing

Maschine RAMonTM vorstellen, die mehrere Dinge gleichzeitig

beweisen soll. Zunächst einmal soll gezeigt werden, dass Turing-

Maschinen und Computer zueinander äquivalent sind. Diese Tatsache

wird zwar in vielen Büchern erwähnt, und andeutungsweise wird

manchmal auch ein theoretisches Beweisverfahren vorgestellt, aber

nie ausführlich dargestellt.

Da die Maschine ein nur einseitiges unendliches Band benötigt, ist

damit auch gezeigt, dass ein einseitig unendliches Band keine

Einschränkung für eine Turing-Maschine darstellt. Weiterhin wird

dadurch nachgewiesen, dass eine Turing-Maschine mit mehreren

Bändern äquivalent zu einer Maschine mit nur einem Band ist. Da

bereits viele Implementierungen von quasi parallel ablaufenden PC-

Programmen bestehen, ist somit auch gezeigt, dass eine

nichtdeterministische Turing-Maschine eine deterministische

abbilden kann.

0 1 x y P L D

000 000 0 L 000 1 L 000 x L 000 y L 001 P R 000 L L 000 D L

001 002 0 R 004 1 R 009 P R

002 003 x L 006 y R 002 x R 002 y R 002 P R 002 L R 002 D R

003 001 0 R 001 1 R 003 x L 003 y L 003 P L 003 L L 003 D L

004 006 x R 005 y L 004 x R 004 y R 004 P R 004 L R 004 D R

005 001 0 R 001 1 R 005 x L 005 y L 005 P L 005 L L 005 D L

27

006 110 x L 006 x R 006 y R 007 L L 006 D R

007 008 x L 007 y L 007 x L 007 y L 008 P L 007 L L 007 D L

008 008 x L 008 y L 008 x L 008 y L 001 P R

009 010 x R 011 y R 009 x R 009 y R 009 P R 009 L R 009 D R

010 012 x R 013 y R

011 014 x R 015 y R

012 012 x R 012 y R 012 L R 054 D R

013 013 x R 013 y R 013 L R 072 D R

014 014 x R 014 y R 014 L R 091 D R

015 015 x R 015 y R 015 L R 016 D R

016 017 x L 019 y L 016 x R 016 y R 016 P R 016 L R 016 D R

017 018 0 R 018 1 R 017 x L 017 y L 018 P R 017 L L 017 D L

018 021 0 R 021 0 R

019 020 0 R 020 1 R 019 x L 019 y L 020 P R 019 L L 019 D L

020 021 1 R 021 1 R

021 016 x R 016 y R 022 L R

022 023 xR 023 y R 022 x R 022 y R 022 P R 022 L R 022 D R

023 023 x R 023 y R 024 P L

024 024 x L 024 y L 024 0 L 024 1 L 025 P R 024 L L 024 D L

025 026 0 R 028 1 R 033 L L

026 027 x L 030 y R 026 x R 026 y R 026 P R 026 L R 026 D R

027 025 0 R 025 1 R 027 x L 027 y L 027 P L 027 L L 027 D L

028 030 x R 029 y L 028 x R 028 y R 028 P R 028 L R 028 D R

029 025 0 R 025 1 R 029 x L 029 y L 029 P L 029 L L 029 D L

030 030 x R 030 y R 030 P R 031 L L 030 D R

031 032 x L 032 y L 031 x L 031 y L 031 P L 031 L L 031 D L

032 032 x L 032 y L 025 P R

033 033 x L 033 y L 034 P L

034 034 x L 034 y L 035 P R

28

035 036 0 R 036 0 R

036 036 x R 036 y R 036 P R 037 L R

037 038 0 R 039 1 R 037 0 R 037 1 R 037 P R 037 L R 037 D R

038 038 0 R 039 1 L 045 L L

039 039 0 L 039 1 L 040 x R 040 y R 039 P L 039 L L 039 D L

040 040 x R 040 y R 041 D R 040 L R 040 D R

041 042 x L 043 y L 041 x R 041 y R 041 P R 041 L R 041 D R

042 044 x R 044 x R 042 x L 042 y L 042 P L 042 L L 042 D L

043 044 y R 044 y R 043 x L 043 y L 043 P L 043 L L 043 D L

044 041 0 R 041 1 R 000 P L

045 045 0 L 045 1 L 046 x L 046 y L 045 D L 045 L L 045 D L

046 046 x L 046 y L 047 P L

047 048 y L 047 x L 048 y L 047 x L 049 P R

048 048 x L 048 y L 048 x L 048 y L 049 P R

049 049 x R 049 y R 050 P L

050 051 y L 050 x L 051 y L 050 x L 052 P R

051 051 x L 051 y L 051 x L 051 y L 052 P R

052 052 x R 052 y R 053 P L

053 000 y L 053 x L 001 P R

054 055 x L 057 y L 054 x R 054 y R 054 P R 054 L R 054 D R

055 056 0 R 056 1 R 055 x L 055 y L 056 P R 055 L L 055 D L

056 059 0 R 059 0 R

057 058 0 R 058 1 R 057 x L 057 y L 058 P R 057 L L 057 D L

058 059 1 R 059 1 R

059 054 x R 054 y R 060 L R

060 061 0 L 061 1 L 060 x R 060 y R 060 P R 060 L R 060 D R

061 061 x L 061 y L 061 0 L 061 1 L 062 P R 061 L L 061 D L

062 063 0 R 065 1 R 069 L R

063 064 x L 067 y R 063 x R 063 y R 063 P R 063 L R 063 D R

29

064 062 0 R 062 1 R 064 x L 064 y L 064 P L 064 L L 064 D L

065 067 x R 066 y L 065 x R 065 y R 065 P R 065 L R 065 D R

066 062 0 R 062 1 R 066 x L 066 y L 066 P L 066 L L 066 D L

067 067 x R 067 y R 067 P R 068 L L 067 D R

068 068 x L 068 y L 068 x L 068 y L 062 P R 068 L L 068 D L

069 070 x R 070 x R 069 x R 069 y R 069 P R 069 L R 069 D R

070 070 x R 070 x R 071 L L

071 071 x L 071 x L 071 0 L 071 1 L 050 P L 071 L L 071 D L

072 073 x L 075 y L 072 x R 072 y R 072 P R 072 L R 072 D R

073 074 0 R 074 1 R 073 x L 073 y L 074 P R 073 L L 073 D L

074 077 0 R 077 0 R

075 076 0 R 076 1 R 075 x L 075 y L 076 P R 075 L L 075 D L

076 077 1 R 077 1 R

077 072 x R 072 y R 078 L R

078 079 0 L 079 1 L 078 x R 078 y R 078 P R 078 L R 078 D R

079 079 x L 079 y L 079 0 L 079 1 L 080 P R 079 L L 079 D L

080 081 0 R 083 1 R 087 L R

081 082 x L 085 y R 081 x R 081 y R 081 P R 081 L R 081 D R

082 080 0 R 080 1 R 082 x L 082 y L 082 P L 082 L L 082 D L

083 085 x R 084 y L 083 x R 083 y R 083 P R 083 L R 083 D R

084 080 0 R 080 1 R 084 x L 084 y L 084 P L 084 L L 084 D L

085 085 x R 085 y R 085 P R 086 L L 085 D R

086 086 x L 086 y L 086 x L 086 y L 080 P R 086 L L 086 D L

087 088 0 R 088 1 R 087 x R 087 y R 087 L R 087 D R

088 088 0 R 088 1 R 089 L L

089 090 1 L 089 0 L 071 D L

090 090 0 L 090 1 L 071 D L

091 092 x L 094 y L 091 x R 091 y R 091 P R 091 L R 091 D R

092 093 0 R 093 1 R 092 x L 092 y L 093 P R 092 L L 092 D L

30

093 096 0 R 096 0 R

094 095 0 R 095 1 R 094 x L 094 y L 095 P R 094 L L 094 D L

095 096 1 R 096 1 R

096 091 x R 091 y R 097 L R

097 098 0 L 098 1 L 097 x R 097 y R 097P R 097 L R 097 D R

098 098 x L 098 y L 098 0 L 098 1 L 099 P R 098 L L 098 D L

099 100 0 R 102 1 R 106 L R

100 101 x L 104 y R 100 x R 100 y R 100 P R 100 L R 100 D R

101 099 0 R 099 1 R 101 x L 101 y L 101 P L 101 L L 101 D L

102 104 x R 103 y L 102 x R 102 y R 102 P R 102 L R 102 D R

103 099 0 R 099 1 R 103 x L 103 y L 103 P L 103 L L 103 D L

104 104 x R 104 y R 104 P R 105 L L 104 D R

105 105 x L 105 y L 105 x L 105 y L 099 P R 105 L L 105 D L

106 107 0 R 107 1 R 106 x R 106 y R 106 L R 106 D R

107 107 0 R 107 1 R 108 L L

108 1081 L 109 0 L 071 D L

109 109 0 L 109 1 L 071 D L

RAM-Simulation auf einer Turing-Maschine

Was macht nun die Maschine RAMonTM? Bei diesem Programm

handelt es sich um die Simulation eines Speichers mit wahlfreiem

Zugriff (RAM), auf den mit bestimmten Operatoren zugegriffen

werden kann. Das gleiche Prinzip ist auch in einer herkömmlichen

CPU verwirklicht. Dabei ist das Band in bestimmte Segmente

unterteilt.

Segmentierung des Bandes

P1 P2 L D L D L D ...

31

Die Segmente P1 und P2 (Programmzähler), die sich ganz am linken

Rand befinden, sind spezielle Verwaltungsregister. Das Register L ist

eine sogenannte Kennung (Label) des Registers D, das als Datenfeld

wirkt. Dabei sollte die Kennung oder auch Speicheradresse eine

eindeutige Binärzahl sein, welche die Zellen in aufsteigender

Reihenfolge durchnummeriert. Beide Register zusammen ergeben

eine adressierbare Speicherzelle. Auf dem Band sind die jeweiligen

Segmente mit ihren Buchstaben gekennzeichnet. In den P-Registern

befinden sich Kennungen, nach denen in den L-Registern gesucht

wird.

Die Länge der Kodierung muss in allen Registern gleich lang sein.

Will man eine 8-bit-CPU simulieren, so müssen alle Register jeweils

mit führender Registerkennung 9 Felder umfassen. Weiterhin gibt es

für die Binärzahlen 1 und 0 zwei Markierungszeichen x und y, die zur

Kennzeichnung der momentanen Bearbeitungsposition in den

Registern zuständig sind.

Die zu simulierende CPU besteht aus 4 Befehlen (CLR, INC, DEC,

BNZ), aus denen, wie später gezeigt wird, alle gängigen Befehle einer

herkömmlichen CPU nachgebildet werden können. Diese Operatoren

beeinflussen die D-Register und haben eine bestimmte Kodierung, die

2 Bits lang ist und selbst in das Datenfeld D geschrieben wird.

Die Operatoren belegen noch ein weiteres Datenfeld, in dem sich eine

Kennung dafür befindet, auf welche Speicherzelle sich die Operation

auswirken soll. Der BNZ-Operator beinhaltet noch eine drittes

Datenfeld, mit einer Kennung, die auf eine Speicherzelle verweist,

32

mit der je nach Ergebnis im nächsten Schritt weiter gearbeitet werden

soll.

Operator Speicher

zellen

Codierung Beschreibung

CLR(A) 2 00 Löscht Datenfeld von Speicherstelle A

(A:=0)

INC(A) 2 01 Erhöht Inhalt von Speicherstelle A um 1

(A:=A+1)

DEC(A) 2 10 Erniedrigt Inhalt von Speicherstelle A um 1

(A:=A-1)

BNZ(A,B) 3 11 Springt zur Kennung B, wenn der Inhalt von A

ungleich 0 ist, sonst nächster Befehl

(if A!=0 goto B)

Befehle der simulierten CPU

Die Variablen in Klammern bei den Operatoren in der oberen Tabelle

stehen für Speicheradressen. Diese Variablen stehen in der

darauffolgenden Speicherzelle des Operators. Die Codierung umfasst

2 Bits, wobei der Code immer am Anfang der Speicherstelle stehen

und der Rest der Speicherstelle mit Nullen aufgefüllt werden muss,

falls es sich um eine CPU-Simulation mit mehr als 2 Bit handelt.

Ein wichtiger Operator fehlt, nämlich eine Stop-Anweisung HLT.

Dieser ist dadurch realisiert, dass eine Speicheradresse angesprungen

wird, die nicht existiert. Dabei gelangt die Turing-Maschine beim

Suchen an das Ende des Bandes und hält daraufhin an. Am folgenden

Beispiel zeige ich, wie die Konfiguration eines kleinen Programms

aussehen kann.

33

MAKRO:JMP(A)

BNZ(t1,A)

t1: 1

JMP-Befehl (goto A)

Im obigen Beispiel handelt es sich um die Realisierung einer

bedingungslosen Sprunganweisung, vergleichbar mit dem GOTO-

Befehl herkömmlicher Programmiersprachen mit RAMonTM-

Operatoren. Die Variable A beinhaltet eine beliebige Adresse, zu der

hingesprungen werden soll. Die Anweisungsfolge ist ein sogenanntes

Makro.

Bei diesem Makro fehlen die Speicheradressen, an denen die Befehle

stehen. Indem man die Adressen weglässt, kann die Befehlsfolge an

jeder beliebigen Stelle im Speicher platziert werden. Das Makro-

Label steht für die Anfangsadresse des Programms im Speicher. In

diesem Beispiel wäre das der Operator BNZ. Das Label t1 steht für

eine Variable im Speicher, die mit 1 initialisiert ist. Da BNZ 3

Speicherzellen in Anspruch nimmt, steht die Variable folglich an der

Adresse JMP+3. Im Computerbereich würde der Linker beim

Compiler die Befehle an die richtigen Adressen setzen.

Ausgeschrieben würde das obere Programm auf dem Turingband

dann folgendermaßen aussehen, wobei A=100 die Adresse des

Sprungzieles ist:

JMP(A) : PxxxPxxxL000D110L001D011L010D100L011D001Lx

Umsetzung des JMP(A)-Befehles mit einer 3-Bit-Maschine

Das Programm springt somit an die Adresse A, wenn die Variable t1

ungleich 0 ist. Da die Variable t1 mit 1 initialisiert ist, springt das

34

Programm immer an die Stelle A, was dem GOTO-Befehl entspricht.

Im Folgenden will ich anhand dieses Beispiels den Ablauf der

Maschine genauer vorstellen.

Die Grundkonfiguration der Maschine besteht darin, dass das erste P-

Register auf Null steht, da dies die erste Speicherstelle darstellt, in der

das Programm beginnt. P1 und P2 sind dabei im markierten Zustand.

Der Startpunkt der Maschine ist das erste linke Zeichen auf dem

Turing-Band. Die erste Aufgabe von RAMonTM besteht darin, nach

der Speicherstelle zu suchen, die im P1-Register steht. Dabei

vergleicht sie solange jedes L-Register mit dem P1-Register, bis das

passende gefunden wird.

f(000,P)→(001,P,R) PxxxPxxxL000D110L001D011L010D100L011D001Lx

f(001,x)→(002,0,R) PxxxPxxxL000D110L001D011L010D100L011D001Lx

…

f(002,L)→(002,L,R) P0xxPxxxL000D110L001D011L010D100L011D001Lx

f(002,0)→(003,x,L) P0xxPxxxL000D110L001D011L010D100L011D001Lx

f(003,L)→(003,L,L) P0xxPxxxLx00D110L001D011L010D100L011D001Lx

…

f(003,0)→(001,0,R) P0xxPxxxLx00D110L001D011L010D100L011D001Lx

f(001,x)→(002,0,R) P0xxPxxxLx00D110L001D011L010D100L011D001Lx

Ist die passende Speicherstelle gefunden, so wird ihr Inhalt gelesen

und als Operator interpretiert. In diesem Fall handelt es sich um den

BNZ-Operator.

f(002,0)→(003,x,L) P000PxxxLxx0D110L001D011L010D100L011D001Lx

f(003,x)→(003,x,L) P000PxxxLxxxD110L001D011L010D100L011D001Lx

…

f(003,0)→(001,0,R) P000PxxxLxxxD110L001D011L010D100L011D001Lx

f(001,P)→(009,P,R) P000PxxxLxxxD110L001D011L010D100L011D001Lx

f(009,x)→(009,x,R) P000PxxxLxxxD110L001D011L010D100L011D001Lx

…

f(009,1)→(011,y,R) P000PxxxLxxxD110L001D011L010D100L011D001Lx

f(011,1)→(015,y,R) P000PxxxLxxxDy10L001D011L010D100L011D001Lx

f(015,0)→(015,x,R) P000PxxxLxxxDyy0L001D011L010D100L011D001Lx

…

f(015,D)→(016,D,R) P000PxxxLxxxDyyxLxxyD011L010D100L011D001Lx

35

Jetzt wird der Inhalt des Datenfeldes in das zweite P-Register kopiert.

In diesem P2-Register steht die Adresse des Datenfeldes, das auf Null

getestet werden soll.

f(016,0)→(017,x,L) P000PxxxLxxxDyyxLxxyD011L010D100L011D001Lx

f(017,D)→(017,D,L) P000PxxxLxxxDyyxLxxyDx11L010D100L011D001Lx

…

f(017,P)→(018,P,R) P000PxxxLxxxDyyxLxxyDx11L010D100L011D001Lx

f(018,x)→(021,0,R) P000PxxxLxxxDyyxLxxyDx11L010D100L011D001Lx

f(021,x)→(016,x,R) P000P0xxLxxxDyyxLxxyDx11L010D100L011D001Lx

f(016,x)→(016,x,R) P000P0xxLxxxDyyxLxxyDx11L010D100L011D001Lx

Nun wird das Datenfeld markiert, in dem die Sprungadresse steht,

damit es später wiedergefunden werden kann. Anschließend wird

zum P2-Register zurückgegangen.

f(021,L)→(022,L,R) P000P011LxxxDyyxLxxyDxyyL010D100L011D001Lx

f(022,x)→(022,x,R) P000P011LxxxDyyxLxxyDxyyL010D100L011D001Lx

…

f(022,0)→(023,x,R) P000P011LxxxDyyxLxxyDxyyL010D100L011D001Lx

f(023,1)→(023,y,R) P000P011LxxxDyyxLxxyDxyyLx10D100L011D001Lx

f(023,0)→(023,x,R) P000P011LxxxDyyxLxxyDxyyLxy0D100L011D001Lx

f(023,D)→(024,P,L) P000P011LxxxDyyxLxxyDxyyLxyxD100L011D001Lx

f(024,x)→(024,0,L) P000P011LxxxDyyxLxxyDxyyLxyxP100L011D001Lx

…

f(024,P)→(025,P,R) P000PxyyL000D110L001D011L010P100L011D001Lx

Im Folgenden Schritt wird nach der Speicheradresse gesucht, die im

P2-Register steht. Dazu wird wieder jedes L-Register mit dem P2-

Register verglichen.

f(025,x)→(026,0,R) P000PxyyL000D110L001D011L010P100L011D001Lx

f(026,y)→(026,y,R) P000P0yyL000D110L001D011L010P100L011D001Lx

f(026,y)→(026,y,R) P000P0yyL000D110L001D011L010P100L011D001Lx

f(026,L)→(026,L,R) P000P0yyL000D110L001D011L010P100L011D001Lx

f(026,0)→(027,x,L) P000P0yyL000D110L001D011L010P100L011D001Lx

f(027,L)→(027,L,L) P000P0yyLx00D110L001D011L010P100L011D001Lx

f(027,y)→(027,y,L) P000P0yyLx00D110L001D011L010P100L011D001Lx

f(027,y)→(027,y,L) P000P0yyLx00D110L001D011L010P100L011D001Lx

f(027,0)→(025,0,R) P000P0yyLx00D110L001D011L010P100L011D001Lx

f(025,y)→(028,1,R) P000P0yyLx00D110L001D011L010P100L011D001Lx

f(028,y)→(028,y,R) P000P01yLx00D110L001D011L010P100L011D001Lx

…

36

f(028,1)→(029,y,L) P000P011LxxxDyyxLxxyDxyyLxyxPyxxLxy1D001Lx

…

f(029,1)→(025,1,R) P000P011LxxxDyyxLxxyDxyyLxyxPyxxLxyyD001Lx

Nachdem die Speicherstelle gefunden wurde, wird getestet, ob ihr

Inhalt ausschließlich aus Nullen besteht.

f(037,y)→(037,1,R) P0xxPxyyL000D110L001D011L010P100L01yD001Lx

f(037,D)→(037,D,R) P0xxPxyyL000D110L001D011L010P100L011D001Lx

f(037,0)→(038,0,R) P0xxPxyyL000D110L001D011L010P100L011D001Lx

f(038,0)→(038,0,R) P0xxPxyyL000D110L001D011L010P100L011D001Lx

f(038,1)→(039,1,L) P0xxPxyyL000D110L001D011L010P100L011D001Lx

Da der Inhalt der Speicherstelle ungleich Null ist, wird der Inhalt der

markierten Speicherstelle in das P1-Register kopiert und somit der

Sprung an diese Adresse durchgeführt.

f(039,y)→(040,y,R) P0xxPxyyL000D110L001D011L010P100L011D001Lx

f(040,L)→(040,L,R) P0xxPxyyL000D110L001D011L010P100L011D001Lx

…

f(040,P)→(041,D,R) P0xxPxyyLxxxDyyxLxxyDxyyLxyxP100L011D001Lx

f(041,1)→(043,y,L) P0xxPxyyLxxxDyyxLxxyDxyyLxyxD100L011D001Lx

f(043,D)→(043,D,L) P0xxPxyyLxxxDyyxLxxyDxyyLxyxDy00L011D001Lx

…

f(043,0)→(044,y,R) P0xxPxyyLxxxDyyxLxxyDxyyLxyxDy00L011D001Lx

f(044,x)→(041,0,R) PyxxPxyyLxxxDyyxLxxyDxyyLxyxDy00L011D001Lx

f(041,x)→(041,x,R) Py0xPxyyLxxxDyyxLxxyDxyyLxyxDy00L011D001Lx

…

f(041,0)→(042,x,L) Py0xPxyyLxxxDyyxLxxyDxyyLxyxDy00L011D001Lx

f(042,y)→(042,y,L) Py0xPxyyLxxxDyyxLxxyDxyyLxyxDyx0L011D001Lx

…

f(042,0)→(044,x,R) Py0xPxyyLxxxDyyxLxxyDxyyLxyxDyx0L011D001Lx

f(044,x)→(041,0,R) PyxxPxyyLxxxDyyxLxxyDxyyLxyxDyx0L011D001Lx

f(041,P)→(041,P,R) Pyx0PxyyLxxxDyyxLxxyDxyyLxyxDyx0L011D001Lx

…

f(041,0)→(042,x,L) Pyx0PxyyLxxxDyyxLxxyDxyyLxyxDyx0L011D001Lx

f(042,x)→(042,x,L) Pyx0PxyyLxxxDyyxLxxyDxyyLxyxDyxxL011D001Lx

…

f(042,0)→(044,x,R) Pyx0PxyyLxxxDyyxLxxyDxyyLxyxDyxxL011D001Lx

f(044,P)→(000,P,L) PyxxPxyyLxxxDyyxLxxyDxyyLxyxDyxxL011D001Lx

f(000,x)→(000,x,L) PyxxPxyyLxxxDyyxLxxyDxyyLxyxDyxxL011D001Lx

Ab hier beginnt die Maschine wieder von vorne, nur mit dem

Unterschied, dass der nächste abzuarbeitende Befehl, an der Stelle

37

steht, auf die das P1-Register zeigt. Wäre beim BNZ-Operator das zu

prüfende Feld Null gewesen, so wäre einfach das P1-Register um 3

erhöht worden, was dem nachfolgendem Befehl entsprechen würde.

Um nun zeigen zu können, dass eine CPU mit diesen 4 Befehlen

universell ist, reicht es aus, auf dieser Maschine wiederum eine

Turing-Maschine zu simulieren. Doch dazu werden noch einige

Makros benötigt, die das Ganze etwas übersichtlicher und leichter

gestalten lassen.

In der Beschreibung von RAMonTM sind CLR und INC

(beziehungsweise DEC) überflüssige Befehle und können durch BNZ

und DEC (beziehungsweise INC) ersetzt werden.

MAKRO:CLR(A)

Start:BNZ(t1,A)

JMP(End)

t1: DEC(A)

JMP(Start)

End:

CLR-Befehl (A=0)

Das CLR Makro zieht solange von der Variablen A eine 1 ab, bis sie

0 enthält. Da es sich bei der endlichen Registerbreite um einen

Zahlenring handelt, der nach einer gewissen Stelle (>2n-1, n: Anzahl

der Registerbreite) wieder von vorne anfängt, reicht es aus, dass nur

in eine Richtung gezählt wird. Folglich wird nur DEC oder INC

benötigt.

MAKRO:INC(A)

RLen: 0

CLR(RLen)

DEC(Rlen)

S1: DEC(A)

DEC(Rlen)

BNZ(RLen,S1)

MAKRO:DEC(A)

RLen: 0

CLR(RLen)

INC(Rlen)

S1: INC(A)

INC(Rlen)

BNZ(RLen,S1)

INC-Befehl (A=A+1), DEC-Befehl(A=A-1)

38

Lässt man die Befehle CLR und INC weg, so entfallen die Zustände

10-13 und 54-90. Die Maschine RAMonTM verkürzt sich von 110

auf nur noch 70 Zustände.

Nach dem JMP Makro möchte ich einen weiteren Verzweigungs-

befehl einführen, nämlich das BZ(A,B)-Makro. Im Gegensatz zu

BNZ-Makro verzweigt dieses Makro genau dann zur Adresse B,

wenn A Null ist.

MAKRO:BZ(A,B)

BNZ(A,End)

JMP(B)

End:

BZ-Makro (if A==0 goto B)

Die Variable A steht für die Adresse, deren Inhalt auf Null getestet

wird. Ist der Inhalt von A Null, so wird der nächste Befehl bearbeitet,

der ein Sprung an die Adresse B darstellt. Andernfalls wird an die

Adresse End im Makro gesprungen, die auch die Adresse des

nächsten auszuführenden Befehles darstellt.

Das nächste Makro CPY kopiert den Inhalt von einer Adresse A zu

einer anderen B.

MAKRO:CPY(A,B)

JMP(Start)

t1: 0

Start:CLR(B)

BZ(A,End)

S1: DEC(A)

INC(t1)

INC(B)

BNZ(A,S1)

S2: DEC(t1)

INC(A)

BNZ(t1,S2)

End:

CPY-Makro (B:=A)

39

Der erste Befehl in diesem Makro ist ein Sprung an die Adresse Start,

da vor dem eigentlichen Programm die lokale Variable t1 ihre

Adresse hat und mit Null initialisiert ist. Beim Kopieren wird der

Inhalt von A solange um 1 erniedrigt, bis er Null ist. Gleichzeitig

werden die Variablen t1 und B jeweils um 1 erhöht. Danach wird t1

wieder schrittweise bis Null erniedrigt und die Variable A erhöht.

Bei einer richtigen CPU dürfen auch arithmetische Befehle nicht

fehlen. Deshalb stelle ich zwei Makros für das Addieren (ADD) und

Subtrahieren (SUB) vor.

MAKRO:ADD(A,B,C)

JMP(Start)

t1: 0

t2: 0

Start:CPY(A,C)

CPY(B,t2)

BZ(t2,End)

S1: INC(C)

DEC(t2)

BNZ(t2,S1)

End:

MAKRO:SUB(A,B,C)

JMP(Start)

t1: 0

t2: 0

Start:CPY(A,C)

CPY(B,t2)

BZ(t2,End)

S1: DEC(C)

DEC(t2)

BNZ(t2,S1)

End:

ADD- und SUB-Makros (C:=A+B,C:=A-B)

Für viele Programme benötigt man zudem Vergleichsoperatoren. Der

einfachste ist der Gleichheitsoperator EQU. Sind zwei

Speicherinhalte A und B gleich, so wird an die Speicherstelle C

gesprungen, sonst wird der anschließende Befehl ausgeführt. NEQ ist

einfach das Gegenteil von EQU.

MAKRO:EQU(A,B,C)

JMP(Start)

t1: 0

Start:SUB(A,B,t1)

BZ(t1,C)

MAKRO:NEQ(A,B,C)

JMP(Start)

t1: 0

Start:SUB(A,B,t1)

BNZ(t1,C)

EQU- und NEQ-Makros (if A==B goto C, if A!=B goto C)

40

Weitere wichtige Vergleichsoperatoren sind GT und GTE. Der erste

überprüft, ob der Inhalt der Adresse A größer ist als der Inhalt von B,

und springt bei positivem Test nach C. Der zweite prüft ob A größer

gleich B ist.

MAKRO:GT(A,B,C)

JMP(Start)

t1: 0

t2: 0

Start:EQU(A,B,End)

CPY(A,t1)

CPY(B,t2)

S1: BZ(t1,End)

BZ(t2,C)

DEC(t1)

DEC(t2)

JMP(S1)

End:

MAKRO:GTE(A,B,C)

JMP(Start)

t1: 0

t2: 0

Start:EQU(A,B,C)

CPY(A,t1)

CPY(B,t2)

S1: BZ(t1,End)

BZ(t2,C)

DEC(t1)

DEC(t2)

JMP(S1)

End:

GT- und GTE-Makros (if A>B goto C, if A>=B goto C)

Weitere arithmetische Funktionen der Grundrechenarten sind MUL

und DIV. MUL multipliziert zwei Zahlen, während DIV eine Zahl

durch die andere teilt.

MAKRO:MUL(A,B,C)

JMP(Start)

t1: 0

t2: 0

t3: 0

Start:CLR(C)

CLR(t2)

BZ(A,End)

BZ(B,End)

CPY(B,t1)

S1: ADD(A,t2,t3)

CPY(t3,t2)

DEC(t1)

BNZ(t2,C)

CPY(t2,C)

End:

MAKRO:DIV(A,B,C)

JMP(Start)

t1: 0

t2: 0

t3: 0

Start:CLR(C)

CLR(t3)

BZ(A,End)

BZ(B,End)

GT(B,A,End)

CPY(A,t1)

S1: SUB(t1,B,t2)

CPY(t2,t1)

INC(C)

GT(B,t1,End)

JMP(S1)

End:

MUL- und DIV-Makros (C = A ⋅B, C= A / B)

41

Die heutigen Digitalrechner bestehen aus logischen Bausteinen, die

der boolschen Algebra gehorchen. Diese Gatter-Bausteine heißen

AND, OR und NOT. Alle drei Gatter lassen sich durch

Aneinanderreihung von NAND-Gatter simulieren.

Beschreibung einiger logischer Gatter durch NAND

MAKRO:NAND(A,B,C)

JMP(Start)

t1: 0

t2: 1

Start:CLR(C)

ADD(A,B,t1)

GT(t1,t2,End)

INC(C)

End:

NAND-Gatter

In vielen Programmiersprachen existieren Zugriffsmöglichkeiten auf

sogenannte Speicher-Arrays. Dabei handelt es sich um nichts anderes

als um zusammenhängende Speicherstellen, auf die durch eine

einzige Variable und einen Index zugegriffen werden kann. Diese

Funktionalität wird durch die Makros LD und ST realisiert.

Dabei ist A die Variable, ab der die zusammenhängenden

Speicherstellen stehen. B ist der Index, der auf die Position einer

Speicherstelle innerhalb dieses Speicher-Arrays zeigt, und C die

Speicherstelle, in die der Inhalt aus dem Array kopiert

beziehungsweise von dort aus in das Array gespeichert wird.

NOT(A) := NAND(A,A)

AND(A,B) := NOT(NAND(A,B)) OR(A,B) := NOT(AND(NOT(A,B),NOT(A,B)))

42

MAKRO:LD(A,B,C)

JMP(Start)

t1: 0

r0: 0

Start:ADD(R1,B,r0)

CPY(r0,R1)

CPY(r0,R2)

CPY(r0,R3)

CPY(r0,R4)

CLR(C)

BZ(R1:A,End)

S1: DEC(R2:A)

INC(t1)

INC(C)

BNZ(R3:A,S1)

S2: DEC(t1)

INC(R4:A)

BNZ(t1,S2)

End:

MAKRO:ST(A,B,C)

JMP(Start)

t1: 0

r0: 0

Start:ADD(R1,B,r0)

CPY(r0,R1)

CPY(r0,R2)

CLR(R1:A)

BZ(C,End)

S1: DEC(C)

INC(t1)

INC(R2:A)

BNZ(C,S1)

S2: DEC(t1)

INC(C)

BNZ(t1,S2)

End:

LD- und ST-Makros (C:=A[B], A[B]:=C)

Prinzipiell ähneln LD und ST dem CPY-Makro. Doch um den Array-

Zugriff über einen Index zu verwirklichen, muss ein Trick

angewendet werden. Dieser Trick beruht darauf, dass die Argumente

für die Operatoren selbst wieder an einer Speicherstelle stehen.

Daher kann der Inhalt der Speicherstelle, an der eine Adresse

enthalten ist, den Index zu addieren und das Ergebnis anschließend

wieder an die Position der Adresse zurück kopieren. Die

Speicherstellen, an denen die Adressen stehen, haben das Label R

(z.B.: BZ(R1:A,End) ). Nun sind alle nötigen Makros

zusammengetragen, um eine Turing-Maschine zu programmieren.

43

PROGRAM: UTM

JMP(Sart)

TMBand[40]: 0,0,0,0,0,…,0

TMDef[20]: 0,0,1,0,0,0,1,1,1,0,…,1

Length: 20

BandPos: 0

State: 0

Read: 0

Write: 0

Direct: 0

looptmp1: 0

gettag: 0

Start: CLR(looptmp1)

LD(TMBand,BandPos,read)

S1: LD(TMDef,looptmp1,gettag)

INC(looptmp1)

EQ(gettag,state,S2)

INC(looptmp1)

INC(looptmp1)

INC(looptmp1)

INC(looptmp1)

GT(length,lootmp1,S1)

JMP(End)

S2: LD(TMDef,looptmp1,gettag)

INC(looptmp1)

EQ(gettag,read,S3)

INC(looptmp1)

INC(looptmp1)

INC(looptmp1)

GT(length,lootmp1,S1)

JMP(End)

S3: LD(TMDef,looptmp1,state)

INC(looptmp1)

LD(TMDef,looptmp1,write)

ST(TMBand,BandPos,write)

INC(looptmp1)

LD(TMDef,looptmp1,direct)

INC(looptmp1)

BNZ(direct,BL)

INC(BandPos)

JMP(Start)

BL: DEC(BandPos)

JMP(Start)

End:

UTM-Programm

44

Einige Erklärungen sind noch wichtig, um das obige Programm zu

verstehen, nämlich die Definition der Variablen TMBand[40] und

TMDef[20]. Die Zahlen in den eckigen Klammern geben an, wie viel

Speicherplatz für dieses Feld ab der Adresse freigehalten werden soll.

Danach folgt die Belegung dieser Speicherzellen. Das Speicherfeld

TMBand entspricht dem Band der Turing-Maschine. Im Speicherfeld

TMDef stehen die Anweisungen für die Turing-Maschine. Diese

Anweisungen für die Turing-Maschine f(q ,p)→(q', p’, z) sind in

Fünfer-Blöcken angeordnet, die die Struktur (q,p,q',p’,z) besitzen.

Alle Belegungen der Variablen müssen übrigens binär sein und sind

nur zur besseren Lesbarkeit in dezimaler Schreibweise dargestellt.

Ein Compiler würde aber auch diese Aufgabe übernehmen.

Der Ablauf des Programms geht folgendermaßen vor sich: Zunächst

werden die Definitionen der Turing-Maschine durchgegangen, um

nach dem aktuellen Zustand zu suchen, der in der Variable State

enthalten ist. Stimmt dieser mit einem der Zustände der Anweisungen

q überein, so wird überprüft, ob das Zeichen auf dem Turing-Band,

dessen Position in BandPos abgelegt ist, mit dem Zeichen der

Definition p übereinstimmt.

Treffen beides zu, so wird der nächste Zustand q' in State gespeichert,

das Zeichen aus den Anweisungen p’ auf das Band geschrieben und

die Bandposition je nach Richtung z um eins erhöht oder erniedrigt.

Danach geht die Maschine wieder zurück zur Position Start. Dies

wird solange wiederholt, bis keine passende Anweisung mehr

gefunden wird.

45

Insgesamt habe ich gezeigt, dass eine normale CPU mit Speicher, auf

den wahlfrei zugegriffen werden kann, durchaus auf einer Turing-

Maschine simulierbar ist und damit auch nachgewiesen, dass mit

einer Turing-Maschine dasselbe machbar ist wie mit einem

gewöhnlichen Computer, allerdings mit einer Geschwindigkeits-

einbuße. Der Geschwindigkeitsverlust entsteht hauptsächlich beim

Suchen der entsprechenden Speicherzelle. Jeder Befehl muss zweimal

suchen. Weiterhin hängt die Dauer des Suchvorganges davon ab, wie

weit eine Speicherzelle von den P-Registern entfernt ist. Die

maximale Entfernung ist wiederum abhängig von der Anzahl der

Speicherzellen m, die durch die Anzahl der Bits n der Register

bestimmt ist (m(n)=2n).

Die Entfernung vom P-Register zur letzten Speicherzelle ist dann

folglich d(n)=2nm(n), da zum Adress-Label noch das gleich lange

Datenfeld dazu gezählt wird. Diese Strecke muss für das Suchen n-

mal durchlaufen werden, und da pro Befehl zweimal gesucht wird,

muss die Strecke d somit 2n-mal durchlaufen werden. Da dieser

Vergleich im schlimmsten Fall für jede Speicherstelle gemacht

werden muss, ergibt sich eine Gesamtbefehlszahl beim Suchen der

Turing-Maschine von S(n)=(2n2n)2.

Für obiges Beispiel benötigt eine Simulation einer 3-Bit-CPU im

schlechtesten Fall folglich S(3)=2304 Schritte für einen CPU-Befehl.

Nimmt man weiterhin an, dass für die Abarbeitung eines Befehls,

egal ob bei einer Turing-Maschine oder einer CPU, die Zeiteinheit

gleich ist, so würde die Simulation 2304-mal länger dauern. Jeder

46

Algorithmus, der auf der CPU läuft, würde auf der Turing-Maschine

linear um 2304 Zeiteinheiten anwachsen.

Ein Problem ist aber hier aus Gründen der Anschaulichkeit nicht

bewiesen worden, und zwar, dass ein Alphabet aus zwei Zeichen

vollkommen ausreicht, um eine universelle Maschine zu konstruieren.

Für die Maschine RAMonTM müssten alle sieben Zeichen in binäre

Darstellung umgewandelt und dementsprechend durch Turing-

Operationen interpretiert werden. Dies würde die Maschine um das

Dreifache anwachsen lassen. Im nächsten Kapitel wird jedoch die

Simulation einer solchen UTM kurz vorgestellt.

47

7. Der Riese mit dem kleinen Alphabet

Die Maschine U [3] zeigt, dass eine UTM mit einem Alphabet aus

nur zwei Symbolen, 0 und 1, konstruiert werden kann. Dabei bleibt

sie genauso mächtig wie eine Maschine mit mehreren Symbolen. Die

Minimierung auf zwei Symbole geht natürlich auf Kosten einer

Vervielfachung der Zustände, wie man hier an U sehen kann. Die

Codierung der Transitionen erfolgt nach der erweiterten binären

Darstellung. Dabei wird bei einer Transition f(a,b)→(c,d,e) nur der

hintere Teil cde benötigt. Der Zustand a ergibt sich aus der Position

auf dem Band B in der Transitionstabelle. Auch das gelesene Symbol

b resultiert aus der Position in der Tabelle, wobei die erste Transition

dem gelesenen Symbol 0 und die zweite dem Symbol 1 entspricht.

Die einzelnen Transitionen sind durch die eindeutige Kennzeichnung

der Bewegungsrichtung voneinander getrennt.

0 1 0 1 0 1

000 000 0 R 128 1 L 001 001 0 R 075 1 R 002 002 0 R 152 0 R

003 003 0 R 078 1 R 004 004 0 R 077 1 R 005 005 0 L 090 1 L

006 006 0 L 117 1 L 007 007 0 R 153 1 R 008 008 0 R 161 1 R

009 009 0 L 177 1 L 010 010 0 L 184 1 L 011 011 0 R 068 0 L

012 012 0 L 197 0 L 013 019 1 R 013 1 R 014 008 0 R 014 1 R

015 042 0 R 064 0 R 016 016 0 L 055 1 L 017 017 0 L 191 1 L

018 035 1 L 140 1 L 019 019 0 R 163 0 R 020 045 0 R 020 1 R

021 012 1 L 021 1 L 022 022 0 L 109 0 L 023 060 0 R 023 1 L

024 052 1 R 024 1 R 025 025 0 R 124 1 R 026 186 1 R 026 1 L

027 029 1 L 027 0 R 028 028 0 L 149 1 L 029 029 1 L 056 0 L

48

030 104 0 R 030 1 L 031 013 1 R 074 0 L 032 032 0 L 183 1 L

033 181 1 L 033 1 L 034 034 0 L 135 0 L 035 035 0 L 132 1 L

036 036 0 L 139 0 L 037 072 1 R 038 1 L 038 038 1 R 080 1 R

039 157 0 R 039 1 L 040 040 0 L 087 1 L 041 015 0 R 041 1 R

042 042 1 R 064 1 R 043 066 0 R 066 1 R 044 128 0 R 044 1 L

045 046 0 R 045 1 R 046 033 0 L 046 1 R 047 005 0 L 193 1 L

048 048 0 R 115 1 R 049 011 1 R 049 1 L 050 053 1 L 050 1 R

051 104 1 L 016 0 L 052 052 1 R 027 0 R 053 028 1 L 054 1 L

054 112 1 L 112 1 L 055 016 0 L 113 1 L 056 011 1 R 056 1 L

057 051 1 L 058 1 L 058 060 0 L 096 0 L 059 084 0 R 084 1 R

060 031 0 L 128 1 R 061 020 0 R 062 1 L 062 020 0 R 083 1 L

063 034 0 L 036 0 L 064 004 0 R 064 1 R 065 066 1 L 059 1 R

066 146 1 L 033 0 L 067 007 0 R 067 1 R 068 068 0 L 162 0 L

069 063 0 L 069 0 L 070 148 0 L 070 1 R 071 140 0 L 031 1 L

072 037 0 R 037 0 R 073 054 1 L 073 1 L 074 032 0 L 074 1 L

075 001 0 R 168 1 R 076 015 0 R 076 1 L 077 004 0 R 196 1 R

078 003 0 R 118 1 R 079 007 0 R 021 1 L 080 001 0 R 080 1 R

081 158 0 L 081 1 R 082 065 0 R 082 1 L 083 020 0 R 194 1 L

084 043 0 R 043 1 R 085 001 0 R 086 1 R 086 001 0 R 176 1 R

087 040 0 L 013 0 R 088 120 1 L 088 1 L 089 023 1 L 050 1 R

090 005 0 L 092 1 L 091 009 0 L 024 1 R 092 005 0 L 047 1 L

093 010 0 L 094 1 L 094 010 0 L 195 1 L 095 000 0 R 048 1 R

096 005 0 L 096 1 L 097 002 1 R 097 1 R 098 022 1 L 098 1 L

099 004 0 R 200 1 R 100 003 0 R 100 1 R 101 030 1 L 102 1 R

102 039 1 L 081 1 R 103 012 1 L 107 1 L 104 058 1 L 006 0 L

105 006 0 L 106 1 L 106 006 0 L 108 1 L 107 012 1 L 098 1 L

108 006 0 L 076 1 L 109 022 1 L 110 1 L 110 095 1 R 199 1 R

111 017 0 L 143 1 L 112 057 1 L 057 1 L 113 016 0 L 114 1 L

114 016 0 L 116 1 L 115 048 0 R 024 1 R 116 016 0 L 160 1 L

49

117 006 0 L 105 1 L 118 003 0 R 121 1 R 119 008 0 R 123 1 R

120 065 0 R 061 0 L 121 003 0 R 122 1 R 122 003 0 R 021 0 L

123 008 0 R 125 1 R 124 025 0 R 155 1 L 125 008 0 R 126 1 R

126 018 0 L 159 1 R 127 018 0 L 017 1 L 128 148 0 L 001 0 R

129 129 0 L 130 1 L 130 147 0 L 130 1 L 131 190 1 R 071 1 L

132 150 1 L 132 1 L 133 014 1 R 073 0 L 134 133 1 L 131 1 R

135 034 0 L 000 0 H 136 136 0 L 069 0 L 137 134 1 L 134 1 R

138 137 1 L 137 0 R 139 036 0 L 000 1 H 140 138 1 L 138 1 L

141 129 1 L 142 0 R 142 018 1 L 136 0 L 143 017 0 L 144 1 L

144 014 1 R 144 1 L 145 071 1 L 131 1 L 146 145 1 L 145 1 L

147 040 0 L 053 0 R 148 065 1 L 146 1 L 149 028 0 L 013 1 R

150 188 0 R 067 0 R 151 032 0 L 133 0 L 152 002 1 R 166 1 R

153 007 0 R 154 1 R 154 007 0 R 156 1 R 155 000 0 R 026 1 L

156 007 0 R 079 1 R 157 000 0 R 051 1 R 158 000 0 R 167 1 L

159 018 0 L 175 1 R 160 182 0 R 160 1 L 161 008 0 R 119 1 R

162 011 1 R 164 1 L 163 019 1 R 097 1 R 164 072 0 R 041 1 R

165 017 0 L 111 1 L 166 002 1 R 169 1 R 167 000 0 R 171 1 L

168 001 0 R 085 1 R 169 002 1 R 170 1 R 170 002 1 R 172 1 R

171 000 0 R 173 1 L 172 009 1 L 010 1 L 173 000 0 R 174 1 L

174 000 0 R 179 1 L 175 018 0 L 070 1 R 176 044 1 L 089 1 R

177 009 0 L 178 1 L 178 009 0 L 180 1 L 179 000 0 R 082 0 L

180 009 0 L 091 1 L 181 000 0 R 088 0 L 182 000 0 R 015 1 R

183 032 0 L 187 1 L 184 010 0 L 093 1 L 185 000 0 R 141 0 R

186 000 0 R 024 0 R 187 032 0 L 189 1 L 188 000 0 R 100 0 R

189 032 0 L 151 1 L 190 018 0 L 127 1 R 191 017 0 L 165 1 L

192 185 0 R 192 1 R 193 005 0 L 049 1 L 194 020 0 R 192 1 R

195 010 0 L 026 1 L 196 004 0 R 099 1 R 197 012 1 L 198 1 L

198 012 1 L 103 1 L 199 000 0 R 025 1 R 200 004 0 R 101 1 R

UTM mit 2-Zeichen-Alphabet

50

Das Eingabeband B von U ist so definiert, dass nach einer

Initialisierung 000...00 zuerst die entsprechend codierte

Transitionstabelle der Maschine M erscheint. Am Ende der Tabelle

befindet sich ein Trennzeichen 111110, welches das Eingabeband Z

von M teilt. Hinzu kommen noch ein paar Verbesserungen, um die

Codierung etwas effizienter zu machen. Zunächst lässt man bei jeder

Transition den Zustand und das zu lesende Zeichen weg, da diese

Information sich aus der Position in der Reihenfolge der Transitionen

ergibt. Eine weitere Vereinfachung besteht darin, dass die erste

Transition einer Maschine M immer als f(0,0)→(0,0,R) angenommen

wird und sie somit am Anfang weggelassen werden kann. Am Ende

von M wird die 110 weggelassen, da jede Maschine mit 110, 1110

oder 11110 enden wird. Darüber hinaus kann 00 am Anfang einer

Transition einfach weggelassen werden, und bei 01 reicht es aus, eine

1 zu schreiben. Zudem ist der Haltezustand nicht als Zustand

realisiert, sondern in der Bewegungsangabe codiert.

0 0 0

1 10 1

R 110 Rechts

L 1110 Links

H 11110 Halt

111110 Trennzeichen

Codierung der UTM

In der unteren Tabelle befindet sich ein Beispiel für die Maschine U.

f(0,0)->(0,0,R) 00R 110

f(0,1)->(1,1,R) 11R 1010110 1010110

51

f(1,0)->(H,1,R) 01H 1011110 1011110

f(1,1)->(1,1,R) 11R 1010110 1010

komplette Codierung mit Trennzeichen 101011010111101010111110

Beispiel einer Codierung der Maschine M

Jede natürliche Zahl kann man auch als eine Konfiguration einer

Turingmaschine interpretieren. Ob diese Maschine dann auch sinnvoll

ist, also irgendwann anhält, ist eine andere Frage. Diese zu

beantworten ist Teil des Halteproblems.

0 0 110 110 R R 00R 000R f(0,0)→(0,0,R)

f(0,1)→(0,0,R)

1 1 110 1110 R L 00R 00L f(0,0)→(0,0,R)

f(0,1)→(0,0,L)

2 10 110 10 110 R 1R 00R 01R f(0,0)→(0,0,R)

f(0,1)→(0,1,R)

3 11 110 11 110 R H 00R 00H f(0,0)→(0,0,R)

f(0,1)→(0,0,H)

4 100 110 100 110 R 10R 00R 10R f(0,0)→(0,0,R)

f(0,1)→(1,0,R)

5 101 110 101 110 R 01L 00R 01L F(0,0)→(0,0,R)

f(0,1)→(0,1,L)

6 110 110 110 110 R R R 00R 00R 00R f(0,0)→(0,0,R)

f(0,1)→(0,0,R)

f(1,0)→(0,0,R)

7 111 110 111 110 R ? 00R ? f(0,0)→(0,0,R)

f(0,1)→(undefiniert)

8 1000 110 1000 110 R 100R 00R 100R f(0,0)→(0,0,R)

f(0,1)→(10,0,R)

52

9 1001 110 1001 110 R 10L 00R 10L f(0,0)→(0,0,R)

f(0,1)→(1,0,L)

10 1010 110 1010 110 R 11R 00R 11R f(0,0)→(0,0,R)

f(0,1)→(1,1,R)

11 1011 110 1011 110 R 1H 00R 01H f(0,0)→(0,0,R)

f(0,1)→(0,1,H)

12 1100 110 1100 110 R R R 00R 00R 00R f(0,0)→(0,0,R)

f(0,1)→(0,0,R)

f(1,0)→(0,0,R)

Zahlen als Programme der UTM interpretiert

Ein weiteres interessantes Beispiel wäre, die UTM in erweiterte

binäre Darstellung umzuwandeln und sie sich selbst als Eingabe Z zu

geben. Dies bedeutet, dass eine Maschine auf einer Maschine

simuliert wird, die wiederum auf einer anderen Maschine

UTM(UTM(M(Z))) mit der Konfiguration 0...0 UTM 111110 0...0 M

111110 Z 0000 simuliert wird. Die Geschwindigkeit der Simulation

einer universalen Maschine wird dadurch natürlich langsamer. Bei

größeren Berechnungen empfiehlt sich eine Beschleunigung der

UTM. Dies kann erreicht werden, indem man der bisherigen

Konfiguration noch mehr Zustände zuweist.

53

8. Klein aber fein

Bei der obigen Maschine stellt man fest, dass sie sehr umfangreich

ist. Ein Maß für diesen Umfang erhält man aus dem Produkt von

Zuständen und Zeichen des Alphabetes. Die obere Maschine hat

somit einen Wert von 200 · 2 = 400. Will man diesen Wert für

universale Turing-Maschinen verkleinern, so stellt man fest, dass man

mit der Simulation von Turing-Maschinen nicht sehr weit kommt.

Deshalb versucht man, andere universale Systeme zu finden, die viel

kleinere Turing-Maschinen hervorbringen. Dies geht allerdings auf

Kosten der Komplexität der Programmierung.

Doch welche Erkenntnisse gewinnt man, wenn man die kleinste

universale Turing-Maschine gefunden hat? Dies Frage kann nur

schwer beantwortet werden. Möglicherweise weiß man, was die

Mindestanforderung an einen Computer ist, wenn man das kleinste

universale System kennt. Oder man kann sich in der Natur auf die

Suche nach solchen universalen Systemen machen, die vielleicht

schon in irgendeiner Form vorkommen, und die als Computer

zweckentfremdet werden könnten. Sieht man sich das folgende

System an, so meint man fast, dass jeder heiße Kaffee einen

Computer darstellen könnte. Bevor ich die universale Turing-

Maschine vorstelle, möchte ich ein bisschen weiter ausholen und

erklären, woraus sie besteht und welches System sie simuliert.

Ulam und von Neumann entwickelten 1940 ein formales System zur

Untersuchung komplexer Systeme. Zellulare Automaten (kurz ZA)

54

sind dynamische Systeme, in denen der Raum und die Zeit in diskrete

Abschnitte eingeteilt sind. Dabei ist der n-dimensionale Raum in

gleich große Zellen aufgeteilt, und jede Zelle besitzt L Nachbarn.

Weiterhin kann eine Zelle einen bestimmten Zustand q einnehmen.

Die Bestimmung des nächsten Zustandes wird über Regeln definiert

und hängt vom aktuellen Zustand und von den Nachbarzuständen ab.

Die Regeln können als Transitionen eines endlichen Automaten

aufgefasst werden. Die Zeit ist in diskrete Einheiten eingeteilt. Dies

bedeutet, dass alle Zellen, die sich im Zeitpunkt t befinden, ihren

neuen Zustand erst zum späteren Zeitpunkt t+1 einnehmen.

Allgemein kann ein zellularer Automat als ein Spezialfall eines

einschichtigen neuronalen Netzes aufgefasst werden. Auch hier ist die

Zelle wieder das berechnende Element, das als einfacher Prozessor

dargestellt ist. Dieses Automatenmodell gehört zu den parallelen

Modellen, da Algorithmen nur durch das gleichzeitige

Zusammenspiel mehrerer Zellen erfolgen kann. Besondere

Anwendungen findet man in der Chemie, Biologie, Physik,

Verkehrsplanung und im künstlichen Leben (Robotik).

Im eindimensionalen Fall besitzt jede Zelle zwei direkte Nachbarn.

Den kompletten eindimensionalen Raum kann man sich als ein

unendlich langes Band vorstellen, wobei das Band in diskrete Zellen

eingeteilt ist. Dabei besitzt eine Zelle zu einer Seite r Nachbarn. Zur

Bestimmung der Zustände werden also L=2r+1 Zellen herangezogen,

wobei die eigene Zelle mit gerechnet wird.

55

Eindimensionaler ZA mit sechs Nachbarn

In der unteren Tabelle ist eine Konfiguration für einen

Beispielautomaten mit r=1 Nachbarn und q=2 Zuständen dargestellt,

die mit 0 und 1 gekennzeichnet sind. Drei Zeichen werden folglich

verglichen, und das unterstrichene wird dann durch das untere ersetzt.

000 001 010 011 100 101 110 111

0 1 0 1 1 0 1 0

Beispielautomat

Zu Beginn besitzt das Band eine Startinitialisierung (Seed). Lässt man

den Automaten ein paar Generationen t durchlaufen, so kommt man

zu einem recht interessanten und auch gut aussehenden Ergebnis. Das

entstandene Gebilde wird Sierpinski-Dreieck genannt und findet unter

anderem in der Chaosforschung seine Anwendung.

r=3 r=3

L L

L L0 0 0 0 1 0 0 0 0 0t=0

L L0 0 0 1 0 1 0 0 0 0t=1

L L0 0 1 0 0 0 1 0 0 0

L L0 1 0 1 0 1 0 1 0 0

t=2

t=3

M

56

Von einer einfachen Formel zum Sierpinski-Dreieck

Interessant ist, wie viele verschiedene Möglichkeiten von Automaten

es gibt, die aus der Kombination r=1 und q=2 entstehen können. Da

der Wert L=3 ist, beträgt die Anzahl der Transitionen T=q(2r+1)=23=8

und somit die maximale Anzahl unterschiedlicher Konfigurationen

K=qT=28=256. Aufgrund der Symmetrie bleiben nur noch 128

Konfigurationen übrig. Dabei kann jede Konfiguration als eine binäre

Zahl interpretiert werden.

000 001 010 011 100 101 110 111

0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 1

2 0 0 0 0 0 0 1 0

...

30 0 0 0 1 1 1 1 0

...

110 0 1 0 1 1 1 1 0

57

...

254 1 1 1 1 1 1 1 0

255 1 1 1 1 1 1 1 1

256 verschiedene Konfigurationen für r=1, q=2

Besonders interessant ist die Konfiguration mit der Dezimalzahl 110.

Sie besitzt die Eigenschaft, ein Turing-vollständiges [4] System zu

sein, was Stephen Wolfram bewiesen hat. Eine Simulation dieser

Regel auf einer Turing-Maschine benötigt 2 Zustände und 5 Symbole,

folglich entspricht der Umfang dieser Maschine 10, wodurch sie

somit zu den bisher kleinsten universalen Turing-Maschinen zählt,

die bis heute bekannt sind.

y c b a x

0 1 c L 1 y R 0 x R 0 x R 0 y R

1 1 b L 1 y R 0 y R 0 x R 0 c R

Simulation der Regel 110 als Turing-Maschine

Doch die Programmierung eines solchen zellulären Automaten ist

nicht einfach. Im Folgenden ist kurz ein Beispielablauf gezeigt. Das

Band ist so aufgebaut, dass die Grenzen des zellularen Feldes durch a

gekennzeichnet sind, was aber durch jeden Generationsschritt

erweitert wird. Leere Felder werden durch ein x markiert und besetzte

durch ein y. Die Maschine startet am rechten Ende des Feldes und

arbeitet sich zunächst nach links vor, wobei alle unbesetzten Felder x

mit einem a markiert werden.

f(0,x)→(0,a,L) aaaaaxxxxxxxxxyxxxxxxxxxxxxxxxx

f(0,x)→(0,a,L) aaaaaxxxxxxxxxyxxxxxxxxxaxxxxxx

f(0,x)→(0,a,L) aaaaaxxxxxxxxxyxxxxxxxxaaxxxxxx

58

Trifft sie auf ein besetztes Feld y, so wird es mit einem c markiert.

f(0,x)→(0,a,L) aaaaaxxxxxxxxxyxaaaaaaaaaxxxxxx

f(0,y)→(1,c,L) aaaaaxxxxxxxxxyaaaaaaaaaaxxxxxx

f(1,x)→(0,c,L) aaaaaxxxxxxxxxcaaaaaaaaaaxxxxxx

f(0,x)→(0,a,L) aaaaaxxxxxxxxccaaaaaaaaaaxxxxxx

f(0,x)→(0,a,L) aaaaaxxxxxxxaccaaaaaaaaaaxxxxxx

Am linken Ende angekommen, kehrt die Maschine um und wandert

wieder ans rechte Ende; dabei wandelt sie jedes a wieder in ein x um.

f(0,x)→(0,a,L) aaaaaxaaaaaaaccaaaaaaaaaaxxxxxx

f(0,a)→(0,x,R) aaaaaaaaaaaaaccaaaaaaaaaaxxxxxx

f(0,a)→(0,x,R) aaaaxaaaaaaaaccaaaaaaaaaaxxxxxx

Trifft sie dabei beim Zurückgehen auf ein c, so wandelt sie dieses in

ein y um und das nachfolgende c in ein x. Ist sie am anderen Ende

angelangt, geht es wieder von vorne los.

f(0,a)→(0,x,R) aaaaxxxxxxxxaccaaaaaaaaaaxxxxxx

f(0,c)→(1,y,R) aaaaxxxxxxxxxccaaaaaaaaaaxxxxxx

f(1,c)→(1,y,R) aaaaxxxxxxxxxycaaaaaaaaaaxxxxxx

f(1,a)→(0,x,R) aaaaxxxxxxxxxyyaaaaaaaaaaxxxxxx

f(0,a)→(0,x,R) aaaaxxxxxxxxxyyxaaaaaaaaaxxxxxx

Die Frage ist nun: Was macht eigentlich Universalität aus? Oder gibt

es vielleicht noch einfachere Turing-Maschinen mit weniger

Zuständen und Symbolen als diese? Diese Fragen sind nur schwer zu

beantworten und bisher auch unbeantwortet geblieben. Doch wie

viele Möglichkeiten gibt es denn überhaupt noch, mit weniger als Q =

2 Zuständen und P = 5 Symbolen eine universale Turing-Maschine zu

konstruieren? Die Anzahl der möglichen Kombinationen aus

Zuständen Q, Symbolen P und Richtungen Z ist K = Q ⋅ P ⋅ Z. Die

Richtung besteht immer aus 2 Bewegungsmöglichkeiten, links und

rechts; somit folgt K = 2 ⋅ 5 ⋅ 2 = 20. Es existieren für die obige

Maschine 20 verschiedene Anweisungen. Will man alle möglichen

59

Programme erhalten, die mit dieser (Q,P)-Turing-Maschine

geschrieben werden können, so ist das M = (Q ⋅ P ⋅ Z)(Q ⋅ P) = 2010.

Stephen Wolfram[4] vermutet, dass (2,3)-Turing-Maschine existieren,

die universal sind. Wahrscheinlich gibt es keine universale Turing-

Maschine mit der Größe (2,2), da bei beliebiger Eingabe die

Komplexität der Ausgabe doch recht gering ist. Allerdings ist bei

manchen (2,3)-Maschinen die Ausgabe sehr komplex, weshalb

Wolfram ihre Universalität vermutet.

Der Verdacht liegt nahe, dass fast jede komplexe Funktion universell

ist und Universalität und Chaos sehr nahe beieinander liegen. Somit

kann auch eine Formel, die aus der Chaosforschung satmmt, für das

thermische Verhalten von Kaffe universell sein. Doch der Beweis

dürfte dafür sehr schwer sein, da die Codierung solcher Maschinen

einfach noch unbekannt ist.

A b c

0 1 b R 0 c L 0 b L

1 0 c L 1 c R 0 a R

Die vielleicht kleinste universale Turing-Maschine

Den Beweis, dass die Regel 110 universell ist, erbrachte Wolfram,

indem er ein zyklisches Produktionssystem (cyclic tag system) mit

Hilfe dieser Regel simulierte. Bei den zyklischen Produktions-

systemen [4] handelt es sich um Ersetzungssysteme, die nach jeder

Ersetzung ihr Regelsystem ändern und somit in unterschiedliche

Phasen aufgeteilt sind. Im einfachsten Fall existieren zwei Phasen mit

je einem Regelsatz, die abwechselnd angewendet werden. Ein

60

Produktionssystem hängt dabei gewisse Muster an eine Kette von

Symbolen an. Ersetzt wird immer das erste Symbol, das auch gelöscht

wird und angehängt wird nur, wenn das erste Symbol schwarz ist. Ist

das erste Symbol weiß, wird folglich nichts angefügt. Welche

Symbole ans Ende der Kette angehängt werden, bestimmen

Produktionsregeln. Die entsprechende Produktionsregel bei dem

Beispiel unten wird aus dem ersten Symbol bestimmt und aus der

Phase, in dem sich das System befindet. Da weiß immer gelöscht

wird, können die Regeln zusammengefasst werden.

Beispiel eines zyklischen Produktionssystems

Beispielablauf

Zusammenfassung:

61

Stephen Wolfram hat nun gezeigt, dass diese Systeme ebenfalls

universell sind. Da er belegen konnte, dass ein eindimensionaler

zellularer Automat, basierend auf der Regel 110 beliebige zyklische

Produktionssysteme simulieren konnte, bewies er damit auch, dass

diese ebenfalls universell sind.

62

9. Der unbestimmte Pfad

Bisher wurden ausschließlich Turing-Maschinen vorgestellt, deren

Ablauf eindeutig bestimmt ist. Das bedeutet, dass bei einer

bestimmten Eingabe die Turing-Maschine aus einem Zustand in einen

eindeutigen Folgezustand übergeht. Doch es gibt auch Turing-

Maschinen, die in einem Zustand bei gleicher Eingabe mehrere

Folgezustände besitzen können. Diese Systeme nennt man

nichtdeterministische Turing-Automaten. Der nachfolgende Zustand

besteht aus der Menge der möglichen Folgezustände. Dieser Zustand

kann aber nicht vorhergesagt werden. Dabei wird angenommen, dass

alle möglichen Folgezustände gleichzeitig parallel eintreten können.

Folglich kann man sagen, dass nichtdeterministische Turing-

Maschinen keinen eindeutigen Ablauf besitzen.

Nichtdeterministische Turing-Maschine

Diese nichtdeterministischen Turing-Maschinen können aber von den

bisher vorgestellten deterministischen Turing-Maschinen

nachgebildet werden, weshalb sie keine zusätzliche Mächtigkeit

besitzen. Ebenso kann ein Rechner mit nur einer CPU mehrere

q

q2'

(p, p2’, z2)

q1'

(p, p1’, z1)

63

Programme quasi gleichzeitig ausführen, was allerdings mehr Zeit

beansprucht. Doch welchen Vorteil besitzen solche Maschinen?

Um ihren Vorteil zu zeigen, werde ich zunächst auf das Anwachsen

der Rechenschritte von Turing-Maschinen eingehen, also

Algorithmen und deren Einteilung in zwei Klassen. Es gibt

deterministische Algorithmen, deren Anzahl an Rechenschritten

(Zeiteinheiten) im Vergleich zum Umfang der Eingabedaten in Form

eines Polynoms wächst (Polynome haben zum Beispiel die Form

aw3+bx2+cy1+d). Dies bedeutet, dass zum Beispiel ein

Sortieralgorithmus mit dem Wachstum n2 zum Lösen der Sortierung

10 Schritte benötigt. Verdoppelt man nun die Sortierdatenmenge, so

wächst die Anzahl der Rechenschritte auf 102 an. Diese Klasse von

Funktionen nennt man P, da die Anzahl der Rechenschritte

polynomial ansteigt (in polynomialer Zeit lösbar). Der Algorithmus

zur Simulation einer Turing-Maschine auf einer anderen liegt in der

Klasse P.

Darüber hinaus existiert noch eine weitere Klasse von

deterministischen Algorithmen, deren Anzahl an Rechenschritten zur

Eingabemenge exponentiell wächst 2n. Ist n sehr groß, so kann dieser

Algorithmus vielleicht nicht in der Zeit enden, über die unser

Universum verfügt oder ein Computer benötigt dafür mehr Energie,

als es darin gibt. Jedenfalls kann es passieren, dass wir das Ergebnis

nicht mehr erleben werden. Somit ist dieser Algorithmus damit

unpraktikabel und eigentlich nicht mehr berechenbar.

64

Hier kommen nun die nichtdeterministischen Turing-Maschinen zum

Einsatz. Da sie in im nichtdeterministischen Rechenschritt alle

Lösungen gleichzeitig produzieren und überprüfen, können sie diese

Klasse von Algorithmen mit polynomialen Wachstum der

Rechenschritte berechnen. Diese Klasse wird auch NP,

nichtdeterministisch polynomial genannt (nichtdeterministisch in

polynomialer Zeit lösbar), da diese Algorithmen auf einer

nichtdeterministischen Maschine in polynomialer Zeit lösbar sind.

Die Klasse P ist in NP enthalten (P⊆NP), da auch Algorithmen aus P

nichtdeterministisch berechnet werden können, allerdings dadurch

keinen Geschwindigkeitsvorteil haben. Im Folgenden möchte ich

einen Weg für ein bekanntes NP-Problem vorstellen, das

nichtdeterministisch in polynomialer Zeit gelöst werden kann.

Das NP-Problem ist als das Problem des Handlungsreisenden bekannt

geworden.

Strassennetz zwischen verschiedenen Orten

Regensburg

Stuttgart

München

Nürnberg

Würzburg

Augsburg

160 100

100

100

120 140

60

120

120

65

Dabei handelt es sich um eine Person, die eine Rundreise durch

verschiedene Orte unternimmt und dabei den kürzesten Weg durch

alle Orte geht. Diesen kürzesten Rundweg zu finden, ist ein NP-

Problem.

Eine mögliche Lösung für die Rundreise wäre zum Beispiel der Weg

(N)ürnberg, (W)ürzburg, (S)tuttgart, (A)ugsburg, (M)ünchen und

über (R)egensburg nach (N)ürnberg zurück. Eine andere mögliche

Route wäre S→A, A→R, R→M, M→N, N→W und W→S. Doch

welche ist die kürzeste Rundreise von allen Möglichkeiten? Dazu

müsste man alle Möglichkeiten durchgehen und für sie die Längen

untereinander vergleichen. Im schlimmsten Fall besteht von jedem

Knoten aus eine direkte Verbindung zu einem anderen Knoten. Es

gäbe folglich für n Knoten n! direkte Verbindungen und somit 2n

verschiedene Pfade, die alle Knoten miteinander verbinden. Ein

nichtdeterministischer Algorithmus würde nun alle möglichen Pfade

gleichzeitig parallel in einem Schritt generieren und sie miteinander

vergleichen. Dies würde im Vergleich zu einem deterministischen

Algorithmus, der alle Wege nacheinander durchgeht, die Rechenzeit

exponentiell verkürzen.

Doch wie werden diese Probleme in der Praxis gelöst? Da jeder

Computer, den man momentan kaufen kann, eine deterministische

Turing-Maschine ist, würde zum Beispiel das obige Rechenproblem,

dessen Eingabe meist viele Tausend Orte betragen kann, nicht mehr

berechenbar sein, wenn man an einem exakten Ergebnis interessiert

ist. Doch meistens genügt schon eine hinreichend gute Lösung und

66

hierfür gibt es verschiedene deterministische Ansätze, die diese in

polynomialer Zeit berechnen können, dafür aber vielleicht einen Pfad

finden, der eventuell nur zu 95% dem exakten Ergebnisses nahe

kommt. Viele Ansätze dafür kommen aus der künstlichen Intelligenz.

Das Gehirn des Menschen arbeitet nach diesem Prinzip. Es ist zum

Beispiel in der Lage, zwar keine exakte, aber dafür eine hinreichend

genaue praktische Lösung für das Problem des Handlungsreisenden

zu finden. Dies löst es durch erworbene Erfahrungen aus der

Vergangenheit und vergleicht das aktuelle Problem mit ähnlichen

bereits gelösten Problemen aus dem Gedächtnis.

Eine große Frage der Informatik ist P=NP. Dies würde übersetzt

bedeuten, dass nichtdeterministische Algorithmen auch in

polynomialer Zeit auf deterministischen Maschinen berechnet werden

könnten, wenn diese Behauptung wahr wäre. Das heißt zum Beispiel,

dass die Faktorisierung, die auch zu der Gruppe der

nichtdeterministischen Probleme gehört, kein zeitaufwendiges

Verfahren mehr wäre. Dadurch würden viele kryptografische

Verfahren an Bedeutung verlieren, da die Zerlegung großer Zahlen in

Rangfolge der Komplexitätsklassen

NP

NP-vollständig

P

67

ihre Faktoren dann nämlich nicht mehr exponentiell mit der Größe

der Zahl wachsen würde, worauf deren Sicherheit beruht. Weiterhin

hat man festgestellt, dass sich viele NP-Probleme ineinander

überführen lassen. Diese Probleme gehören der Klasse der NP-

vollständigen Probleme an. Hat man zum Beispiel einen Algorithmus

für eines der Probleme aus dieser Klasse gefunden, so hat man die

Lösung für alle NP-vollständigen Probleme gefunden. Die

Überführung innerhalb dieser Klasse geschieht in polynomialer Zeit.

Kann man für eines dieser Probleme zeigen, dass P = NP ist, so gilt

dies auch für alle NP-vollständigen Probleme. Wird es irgendwann

nichtdeterministische Turing-Maschinen geben? Diese Frage kann

hier auch nicht genau beantwortet werden, allerdings wird im

Moment sehr stark daran geforscht. Nichtdeterministische Turing-

Maschinen sind eigentlich nichts anderes als Parallelrechner, wobei

jeder Lösungsweg auf einem eigenen Prozessor abläuft. Aus diesem

Grund müsste ein solcher Rechner aus fast unendlichen vielen

Prozessoren aufgebaut sein. Dies wäre bei dem oben vorgestellten

Problem aber mit der momentan in Computern verbauten Hardware

undenkbar. Deshalb sucht man nach anderen Prozessoren, also kleine

Recheneinheiten, die massenhaft vorliegen.

Ein Idee wäre, einen Computer aus Gen-Basen zu bauen [7].

Betrachtet man das obige Beispiel mit dem Handlungsreisenden, so

könnten alle Lösungspfade in Gen-Strängen codiert und mit Hilfe der

Enzyme, die hier als Prozessoren agieren, die passende Lösung

herausgefiltert werden. Da Enzyme und Gene in fast unendlicher

68

Menge vorhanden sind, stellt es keine Schwierigkeit dar, NP-

Probleme mit sehr großen Eingaben damit in polynomialer Zeit

berechnen zu lassen.

Ein anderer Ansatz kommt aus der Quantenphysik. Hier hat man

festgestellt, dass sogenannte Qubits, die zum Beispiel aus den Spins

von Atomkernen bestehen, eine Superposition einnehmen können.

Dies bedeutet, dass nicht entweder der Zustand 0 oder 1 enthalten ist,

sondern beide gleichzeitig. Hätte man ein 8-qubittiges Register, so

wären alle 256 möglichen Zustände im selben Moment vorhanden.

Folglich können auf allen Werten Berechnungen durchgeführt

werden. Aus dieser Tatsache heraus lassen sich ebenfalls NP-

Probleme in polynomialer Zeit berechnen. Die Frage ist nur, ob es

jemals einen universalen Quantenrechner geben wird, da ein großes

Problem hierfür im zerstörungsfreien Auslesen der Werte besteht,

weil die Messung eines Ergebnisses die Überlagerung mit anderen

Zuständen zerstört.

Superpositionen eines Qbits

|1>

|0>

|0> + i|1>

|0> + |1>

69

Da es bisher keine Quantenalgorithmen für allgemeine Klassen von

NP-Problemen gibt, versucht man, heuristische Algorithmen für

solche Probleme zu finden. Der bekannteste ist der Faktorisierungs-

Algorithmus von Shor. Dieser benutzt zum zerstörungsfreien

Auslesen die diskrete Fouriertransformation.

Man kann sich nun fragen, ob es Maschinen gibt, die mächtiger sind

als die Turing-Maschine. Was müsste denn eine Maschine überhaupt

können, um mächtiger zu sein?

Wie vorgestellt, ist die Turing-Maschine nicht in der Lage, das

Halteproblem zu entscheiden. Folglich müsste eine Turing-Maschine

um diesen Mechanismus erweitert werden. Als Gedankenexperiment

existiert so eine Maschine schon, und selbst Alan Turing hat eine

vorgestellt, nämlich die sogenannte O-Maschine. Dabei steht das O

für ein Oracle.

Dieses Oracle hat die Aufgabe, über eine bestimmte natürliche Zahl z,

die ihr übergeben, wird eine Aussage zu helfen. Dabei kann jedes

Programm als Zahl dargestellt werden. In der O-Funktion existiert

eine unendlich lange Binärzahl U, an deren x-ter Stelle steht, ob das

Programm x hält oder nicht (h=O(x)), wobei in der Zahl x auch die

Eingabe codiert enthalten ist.

Mit dieser Funktion kann somit das Halteproblem gelöst werden.

Doch es kann nicht nur entschieden werden, ob ein Programm einen

Fehler enthält oder nicht, es können auch mathematische Aussagen

bewiesen werden. Weiterhin wäre es sogar möglich, Aussagen über

70

die Zukunft zu treffen und somit zum Beispiel Börsenergebnisse

vorherzusagen.

Doch kann es so eine O-Maschine geben? Die Antwort hängt davon

ab, ob so eine Binärzahl in h wirklich existiert und für unser

Universum überhaupt gefunden werden kann. Der Gödelsche Beweis

von der Unvollständigkeit eines Systems sagt weiter aus, dass es

unmöglich ist, mit unserem Gehirn das Universum ganz zu verstehen,

da wir selbst wieder ein Teil dessen sind. Aus diesem Grund werden

wir nie diese Zahl U finden können, da sie uns selbst enthalten müsste

und unsere Gedanken und Gefühle, die wir in diesem Moment haben.

Anders wäre es aber für ein Wesen außerhalb unseres Universums. Es

könnte diese Zahl U finden, allerdings nicht für sein eigenes

Universum.

71

10. Der Automat in unserem Kopf

Grundlage des „Automaten Gehirn“

Seit langem ist bekannt, dass der Sitz unseres Bewusstseins im

Gehirn zu finden ist. Doch welche Bausteine machen unser Gehirn zu

diesem leistungsfähigen Organ? Betrachtet man das Gehirn etwas

genauer, so stellt man fest, dass es aus bestimmten Zellen besteht, die

Neuronen genannt werden. Diese sind in einem Netz zusammen-

geschaltet. Nimmt man nun an, dass dieses neuronale Netz ein

Automat ist, so ist die grundlegende Berechnungseinheit das Neuron.

Diese Neuronen bestehen aus Dendriten, Synapsen, Zellkörper und

dem Axon [5]. Informationen kommen von anderen Zellen über die

Synapse auf den Dendrit des Neurons und werden dort zur Zelle

72

geführt. Von dort aus werden sie weiter an das Axon geleitet, das sie

an die anderen Nervenzellen übermitteln. Im Gehirn eines Säugetieres

ist jedes Neuron mit bis zu 1000 weiteren Neuronen verschaltet, von

den denen einige Milliarden existieren. Die Schaltgeschwindigkeit

einer solchen Zelle ist nicht sehr hoch; es können aber trotzdem sehr

schnell komplexe Prozesse berechnet werden (Mustererkennung).

Das Geheimnis hierfür liegt in der massiven parallelen Verschaltung

dieser Neuronen.

Um neuronale Netze auf einem Rechner zu simulieren, benötigt man

zunächst ein abstraktes mathematisches Modell. Dazu stellt man sich

das Netz zunächst als eine BlackBox mit n Eingängen und m

Ausgängen vor. Mathematisch betrachtet wäre dies eine Funktion mit

einem n-dimensionalen Eingabevektor, der auf einen m-

dimensionalen Ausgabevektor abgebildet wird. Öffnet man diese

Schachtel, so findet man zwei unterschiedliche Verschaltungsarten

der Neuronen. Zum einen kann die Eingabe von einem Neuron, das

einen Teil der Funktion g(x) berechnet, als Funktionseingabe an ein

weiteres Neuron als übergeben werden, das daraus die Funktion

f(g(x)) berechnet (siehe untere Abbildung). Eine zweite Möglichkeit

wäre, dass ein Neuron seine Ausgabe als eigene Eingabe erhält. In

diesem Fall entsteht eine sogenannte Rückkoppelung, mit der auch

rekursive Funktionen dargestellt werden können. Um zu bestimmen,

was zur Eingabe und was zur Ausgabe gehört, wird eine diskrete

zeitliche Dimension t eingeführt. Dabei berechnet das rückgekoppelte

73

Neuron zum Zeitpunkt t die Ausgabe, die ihm erst zum Zeitpunkt t+1

wieder als Eingabe zur Verfügung steht.

Neuronales Netz

McCulloch und Pitts [5] führten 1934 das erste Neuronenmodell ein.

Dabei handelt es sich um sehr einfache Neuronen, die nur binäre

Signale verwenden. Ein Neuron besteht aus n Eingangsleitungen, die

jeweils Null oder Eins enthalten. Das eigentliche Neuron bildet die

Summe dieser Eingaben, die folglich maximal n sein kann. Dieses

Ergebnis wird einer Schwellenwertsfunktion zugeführt, die es mit

einem Schwellenwert vergleicht. Liegt das Ergebnis unter diesem

McCulloch-Pitts-Neuron

f

1x

2x

nx

M M

1y

2y

myf

gx)(xg

))(( xgf

f

tx

..),...)...).(,(,( 21 −− ttt xfxfxf

1x

2x

nx

f )),...,,(( 21 nxxxgfg

74

Schwellenwert, so legt das Neuron eine Null auf die Ausgabeleitung.

Wenn der Wert größer gleich ist oder darüber liegt, dann sendet das

Neuron eine Eins aus.

Darüber hinaus existiert eine hemmende Leitung. Ist diese aktiviert

(also wenn der Wert 1 anliegt), so ist das komplette Neuron gehemmt,

und es sendet bei jeder Eingabe den Wert Null aus.

Im Folgenden sind einige Beispiele aufgeführt, in denen mit Hilfe der

McCulloch-Pitts-Neuronen logische Gatterbausteine nachgebildet

wurden. Die AND-Funktion besitzt zwei Eingänge und einen

Schwellenwert von zwei. Liegen beide Eingänge auf eins, so wird

auch am Ausgang eine Eins angelegt. Bei allen anderen Werten

sendet das Neuron eine Null aus.

AND- und NOR-Funktion

Bei der NOR-Funktion existieren zwei absolut gehemmte Eingänge

und ein Schwellenwert von 0. Liegt an allen Eingängen 0 an, so

sendet das Neuron eine 1 aus, weil der Schwellenwert 0 erreicht wird.

Liegt aber an einem der Eingänge eine 1 an, so wird das gesamte

Neuron blockiert und inaktiviert, und sendet somit eine 0 aus.

Prinzipiell können mit neuronalen Netzen beliebige Funktionen

nachgebildet werden. Will man nun eine logische Funktion mit einer

Ausgabeleitung und n Eingabeleitungen mit Hilfe von Neuronen

1x

2x

2

1x

2x

0

75

abbilden, so reicht ein zweischichtiges Netz vollkommen aus. Wie

man in der unteren Abbildung sehen kann, haben die Neuronen der

ersten Schicht die Aufgabe, die einzelnen Eingaben nach den

gewünschten Werten zu filtern. Ist die gewollte Eingabe dabei, dann

senden sie diese an die nächste Schicht, die als sogenannte ODER-

Funktion arbeitet. Ist also eine Eingabe als passend klassifiziert

worden, so wird auch dieses Neuron aktiviert. Da man mit Neuronen

alle grundlegenden Gatterbausteine AND, OR und NOT nachbilden

kann, ist es folglich auch möglich, jede logische Funktion damit zu

konstruieren. Sie sind damit universell einsetzbar. Aus der logischen

Funktion NAND können alle beliebigen anderen logischen Funktion

rekonstruiert werden.

Beispiel der logischen Funktion NAND

MAKRO:NEURON1(X1,X2,Out)

Start:CLR(Out)

BNZ(X1,End)

BNZ(X2,End)

INC(Out)

End:

MAKRO:NEURON2(X1,X2,Out)

Start:CLR(Out)

BNZ(X1,End)

BZ(X2,End)

INC(Out)

1x

2x0

1 1

Eingabevektor F (x1,x1) y (0,0) 1 (0,1) 1 (1,0) 1 (1,1) 0

1

y

76

End:

MAKRO:NEURON3(y1,y2,y3,Out)

JMP(Start)

t1: 0

t2: 0

Bias: 1

Start:CLR(Out)

ADD(X1,X2,t1)

ADD(X3,t1,t2)

GT(Bias,t2,End)

INC(Out)

End:

PROGRAM:NETZ

JMP(Start)

X1: 0

X2: 0

X3: 0

Out1: 0

Out2: 0

Out3: 0

Out: 0

Start: NEURON1(X1,X2,Out1)

NEURON2(X1,X2,Out2)

NEURON2(X2,X1,Out3)

NEURON3(Out1,Out2,Out3,Out)

End:

Neuronales Netz als RamOnTM-Programm

Wenn man Funktionen mit Neuronen parallelisieren möchte, dann

stellt man fest, dass sich nicht alle Teilschritte einer Funktion in

parallele Teilfunktionen umformen lassen. Es wird immer einen

Schritt geben, der die Teilergebnisse zu einem Gesamtergebnis

zusammenführen muss. Dies sieht man auch am Neuron in der

Ausgabeschicht in der oben dargestellten Abbildung.

Bei gewichteten Neuronen erhalten die Eingabeleitungen x jeweils

noch einen Faktor w, mit dem sie multipliziert werden. Da aber schon

das bisherige Neuronenmodell die allgemeinste Form darstellt, ist

diese zusätzliche Information redundant. Dies bedeutet, dass die

77

gewichteten Neuronen äquivalent zu den ungewichteten sind. Es ist

also möglich, gewichtete Neuronen durch McCulloch-Pitts-Neuronen

darzustellen.

Äquivalenz gewichteter und ungewichteter Neuronen

Aus dem Beispiel in der obigen Abbildung ist zu entnehmen, dass

man durch die Multiplikation der Gewichte (oberes Neuron) mit einer

Konstanten eine ganze Zahl erhält, die sich wiederum in der Anzahl

der Eingabeleitungen widerspiegelt (unteres Neuron).

Unter relativ gehemmten Neuronen versteht man Neuronen, die nicht

sofort blockiert werden, wenn eine hemmende Leitung aktiv ist.

Anders als bei den absolut gehemmten Neuronen, wird der Wert der

relativ hemmenden Leitung auf den Schwellenwert m addiert.

Alternativ kann man sich die relativ hemmende Leitung aber auch mit

einem Gewicht von –1 vorstellen. Um ein relativ hemmendes Neuron

mit n erregenden Eingängen, einer hemmenden Leitung und dem

Schwellenwert m zu blockieren, muss die Bedingung n-m+1 < 0

1x

3x

7,02x

2,0

4,0

3,0

7,03,04,02,0),,( 321321 ≥++= xxxxxxf

7342),,( 321321 ≥++= xxxxxxf

1x

3x

72x

78

gelten. Wie in der unteren Abbildung dargestellt, kann auch ein

relativ gehemmtes Neuron (links) durch McCulloch-Pitts-Neuronen

(rechts) dargestellt werden.

Äquivalenz relativ und absolut gehemmter Neuronen

Dabei muss jedoch die Netztopologie verändert werden. Das erste

Neuron erhält eine absolut hemmende Leitung und ist blockiert, falls

y auf Eins gesetzt ist. Das untere Neuron erhält alle anderen

erregenden Eingänge, wobei aber ein Schwellenwert m+g zum

Feuern erreicht werden muss. Die Variable g steht für das Gewicht

der relativ hemmenden Leitung und ist in diesem Fall 1.

Ein Automat ist ein System, das im Laufe der Zeit bestimmte

Zustände annimmt, je nach externer Eingabe seinen Zustand ändert

und eine entsprechende Ausgabe erzeugt. Endliche Automaten

besitzen nur endlich viele Zustände und reagieren auf endliche

Eingabesignale. Jeder Computer ist also ein endlicher Automat. Dabei

kann jeder endliche Automat mit McCulloch-Pitts-Zellen simuliert

werden. Von Marvin Minsky[2] (1967) stammt ein konstruktives

Verfahren, welches in der unteren Abbildung zu sehen ist. Es

existieren m Eingabesignale, die über die Leitung I decodiert

eingegeben werden. Dabei ist zu jedem Zeitpunkt t nur eine Leitung

1x

nxm

2x

y

1x2x m

1+m

1

ynx

79

aktiv (enthält eine 1) alle anderen Leitungen sind passiv (auf 0

gesetzt). Am Anfang befindet sich der Automat im Startzustand Qi,

dessen Eingansgleitung auf 1 gesetzt worden ist; alle anderen sind auf

0 gesetzt. Zu jedem Zeitpunkt t+1 kann also nur eine der AND-Zellen

eine 1 senden, nämlich genau diejenige, bei der sowohl

Zustandsleitung als auch Eingabeleitung aktiv sind.

Realisierung eines endlichen Automaten mit McCulloch-Pitts-Netz

Wenn zum Beispiel die Eingabeleitung I1 aktiv ist und der Zustand

Q1 einen Übergang zum Zustand Q2 bewerkstelligen sollen, dann

muss die Ausgangsleitung der obersten linken AND-Zelle an die

1 1 1

2 2 2

2

2

2 2

2 2

M M M

L

L

L

L

1I

2I

mI

1Q2Q

nQ

1Q2Q

kQ

80

Eingangsleitung der OR-Zelle geschaltet werden (siehe gestrichelte

Linie im oberen Kasten der Abbildung). Die Leitung Q2 wird dann

zum Zeitpunkt t+2 aktiv. Zu diesem Zeitpunkt muss eine neue

Leitung (zum Beispiel I3) aktiv sein, und ein neuer Zustandsübergang

wird berechnet. Ähnlich verhält es sich mit der Ausgabe, wobei die

aktive AND-Zelle auch mit der entsprechenden Ausgabe (unterer

Kasten) verbunden ist. Der Nachteil dieses Verfahrens besteht darin,

dass jeder endliche Automat für jede Funktion extra konstruiert

werden muss. Viel sinnvoller wäre ein universelles Netz, das

beliebige Funktionen berechnen kann, ohne deren Topologie zu

verändern. Zusätzlich sollte sich das Netz selbständig an das jeweilige

Problem anpassen und somit sich selbst programmieren. Hierfür gibt

es verschiedene Lernalgorithmen, die in diversen Büchern

nachzulesen sind und auf die ich hier nicht näher eingehen möchte.

Da unser Gehirn aus Neuronen aufgebaut ist, stellt sich die

philosophische Frage, ob das Bewusstsein und der angebliche freie

Wille des Menschen, der im Gehirn manifestiert sein soll, nichts

anderes ist als ein Programm, das durch Neuronen simuliert wird.

Diese Frage gehört auch zu den momentan noch unbeantworteten.

Vielleicht ist aber unser freier Wille eben nur eine Einbildung, und

wir handeln so, wie eine Funktion es uns vorschreibt, wobei wir aber

stets den Eindruck haben, dass wir eine freie Entscheidung treffen.

Das Gleiche könnte auch auf das Bewusstsein zutreffen, nämlich dass

es sich hier eventuell um eine selbstreflektorische Funktion handelt.

Doch diese Hypothesen gehören noch in den Bereich der Philosophie

81

und werden erst dann beantwortet, wenn es gelingt, das menschliche

Gehirn künstlich zu simulieren und man durch Kommunikation mit

diesem nicht mehr unterscheiden kann, ob es sich um einen echten

Menschen handelt oder um einen simulierten. Doch warum sollte

eigentlich nur das Gehirn ein Automat sein und nicht gleich unser

ganzes Universum?

82

11. Das Universum als Turing-Maschine

Am Anfang dieses Kapitels möchte ich eine philosophische Frage

formulieren. Angenommen, in einem Wald fällt ein Baum um. Wird

dadurch ein Geräusch erzeugt oder nicht? Die Antwort ist, so

verblüffend sie sein mag, „Nein“. Das kann dadurch erklärt werden,

dass der Baum beim Umfallen Druckunterschiede erzeugt, die sich in

der Luft als Schallwellen fortpflanzen. Erst wenn sie auf das

Hörorgan eines Lebewesens treffen würden, könnte dieses Ohr die

Schallwellen mit Hilfe der Sinneszellen in elektrische Impulse

umwandeln und an das Gehirn weiterleiten. Erst das Gehirn

interpretiert diese Signale als ein Geräusch. Folglich kann man sagen:

kein Gehirn, kein Geräusch.

Alle Sinneseindrücke, die wir erhalten, treffen im Gehirn in Form von

elektrischen Impulsen ein, die nur dadurch als das interpretiert

werden, was sie sind, dass sie an einer bestimmten Stelle im Gehirn

die entsprechenden Rezeptoren reizen. Unser ganzes Bild von der

Welt, die in unserem Kopf sozusagen abgebildet ist, basiert auf dieser

Art von Sinneswahrnehmung und deren Interpretation solcher

Signale. Die Welt, wie wir sie täglich erfahren, entspringt lediglich

aus der Art und Weise, wie wir diese Signale interpretieren. Doch das

bedeutet nicht, dass die Welt auch wirklich so ist. Das lässt natürlich

Raum für Spekulationen über die Realitäten zu, die alle richtig sein

können und nur vom Standpunkt der Interpretation abhängen.

83

Eine mögliche Behauptung wäre, dass unsere Welt gar nicht

dreidimensional ist, wie wir sie mit unseren Augen wahrnehmen,

sondern nur eindimensional, und unsere Augen Dreidimensionalität

nur vortäuschen. Dass unser Universum eindimensional sein kann, ist

durch die Existenz der Turing-Maschine mit seinem

eindimensionalen Band gegeben. Auf ihr lassen sich dreidimensionale

Welten mit dem dazugehörigen physikalischen System nachbilden

und berechnen. Einfache Beispiele dafür wären die seit einiger Zeit

beliebten 3D-Spiele.

Weiterhin gibt es einige Anzeichen dafür, dass physikalische

Vorgänge zwar nicht mit unseren klassischen mathematischen

Methoden berechnet werden können, aber auf einer logischen

Grundlage beruhen und mit Hilfe von iterativen Algorithmen

nachvollzogen werden können.

In den letzten Jahren hat sich ein Fachgebiet entwickelt, das sich mit

der Thematik beschäftigt, künstliches Leben auf algorithmischer

Basis zu simulieren. Zunächst einmal müsste definiert werden, was

„Leben“ überhaupt bedeutet. Dies ist nicht ganz einfach, und eine

genaue Grenze wurde bis heute noch nicht gefunden. Es wäre

möglich, dass im Universum Lebensformen existieren, die wir nicht

als solche wahrnehmen können. Doch zumindest kann man Leben als

etwas definieren, was sich reproduzieren kann, Energie aufnimmt und

diese in Form von Bewegung wieder abgibt.

In diesem Fachgebiet werden in einem begrenzten virtuellen Raum

Programme untersucht, die zum Beispiel nichts anderes machen, als

84

sich gegenseitig jagen, fressen und sich nach einer gewissen Zeit

reproduzieren. Diese sogenannten Agenten können aus einfachen

Algorithmen bestehen oder sogar ein neuronales Gehirn besitzen.

Dieses Gehirn kann mit der Zeit lernen, effektiver andere Agenten zu

jagen, oder die Agenten sind in der Lage, bei der Reproduktion eine

Art genetischen Code über ihren Aufbau weiterzugeben. Das alles

zusammen schafft ein sehr komplexes System, das nicht mehr

mathematisch exakt vorhergesagt werden kann, und jeder Ausgang

dieser Experimente muss iterativ vollzogen werden.

Systeme können nur dann mathematisch exakt vorhergesagt werden,

wenn man für ihren Algorithmus eine Abkürzung gefunden hat. Zum

Beispiel liefert die Mathematik Formeln für die Berechnung von

Planetenbewegungen, und man kann mit ihrer Hilfe vorhersagen, wie

die Planeten in 10 Tagen stehen werden. Doch in der komplexen

Simulation von künstlichem Leben ist eine solche Berechnung nicht

möglich oder zumindest nicht bekannt.

Hauptsächlich werden Agenten darauf untersucht, wie sie sich an ihre

Umgebung anpassen und welche von ihnen die beste

Überlebensstrategie entwickeln, die durch Mutation der Gene und

damit durch ihren körperlichen Aufbau und ihr Verhalten sowie durch

Lernprozesse in ihrem Gehirn bestimmt wird.

Ein sehr einfaches abstraktes Modell hierfür möchte ich im

Folgenden kurz vorstellen. Es beinhaltet keinerlei Möglichkeit,

komplexe Agenten zu erstellen, sondern besteht nur aus einem

zweidimensionalen Feld, dessen einzelne Felder lediglich zwei

85

Zustände annehmen können, die durch Nachbarzellen aus der

vorhergehenden Generation bestimmt werden. Dabei handelt es sich

um einen zweidimensionalen zellularen Automaten, dessen

Nachbarschaftsregeln Conway’s Game of Life genannt werden. Die

zwei Zustände einer Zelle werden als lebendig und tot bezeichnet.

Damit eine Zelle überlebt, also im nächsten Zyklus nicht stirbt,

müssen zwei oder drei der acht direkten Nachbarzellen lebendig sein.

Ist eine Zelle tot und drei der acht Nachbarn sind lebendig, wird diese

Zelle auch lebendig.

Zustand der Zelle bleibt gleich, da sie 2 bzw. 3 lebendige Nachbarn hat

Zelle wird lebendig, da sie genau 3 Nachbarn hat

Zelle stirbt, da sie nur einenlebendigen Nachbarn besitzt

t

t

t

86

In allen anderen Fällen stirbt eine lebendige Zelle, oder eine tote Zelle

verharrt in diesem Zustand. Dieser Regelsatz wird als S23B3-Regel

bezeichnet, wobei S für survive und B für birth steht.

In dieser S23B3-Regel existieren einige besondere Objekte. Im

unteren Beispiel sieht man ein Objekt, das Gleiter genannt wird, weil

es sich nach 4 Generationen wieder in das gleiche Objekt verwandelt.

Es ist dann nur um einige Zellen verschoben und gleitet somit

unaufhörlich über das Feld.

Gleiter

Weitere interessante Formen sind der Oszillator und ein stabiles

Element.

Oszillator und stabiles Element

Der Oszillator hat die Eigenschaft, am gleichen Ort in der

übernächsten Generation wieder in die Ausgangssituation zurück zu

kehren, während das stabile Element in jeder Generation gleich

aussieht und stehen bleibt. Interessante Objekte sind auch sogenannte

t

t

87

Kanonen. Diese feuern ab einer bestimmten Generation einen Gleiter

ab.

Kanone

Die oben genannten Objekte sind nur einige Beispiele von Objekten,

die zu einer größeren Maschine zusammengefügt eine Turing-

Maschine simulieren können. Im unteren Bild ist eine solche

Konfiguration eines zellularen Automaten der S23B3-Regel [6]

dargestellt. Die Turing-Maschine besteht dabei aus zwei Bändern, die

wie ein Stapel benutzt werden, wobei von einem Stapel ein Symbol

genommen und oben auf den anderen Stapel gelegt wird und

umgekehrt. Die Maschine beinhaltet als Programm eine leicht

modifizierte Version der universalen Turing-Maschine von Marvin

Minsky [2].

Im Folgenden möchte ich zeigen, dass ein zellularer Automat ZA auf

einer Turing-Maschine simulierbar ist, indem ich ihn in RAMonTM

M

88

programmiere. Da jede Zelle eines zellularen Automaten (ZA) einen

eigenen Prozessor darstellt, gehören diese zu den massiv parallelen

Automaten. Dies zeigt auch, dass Turing-Maschinen nichtdeter

ministische Maschinen simulieren können. Auf einem unendlich

großen Feld können wiederum unendlich viele Turing-Maschinen

beschrieben werden, wie sie in der unteren Abbildung gezeigt.

Simulation einer Turing-Maschine

89

MAKRO:GET1DFROM2DPOS(X,Y,LenX,Pos1D)

JMP(Start)

t1: 0

Start:MUL(LenX,Y,t1)

ADD(t1,X,Pos1D)

End:

PROGRAM: ZA

JMP(Start)

DimX: 20

DimY: 20

DimXa: 0

DimYa: 0

F1[20,20]:0,..,0

Ft[20,20]:0,..,0

CntX: 0

CntY: 0

Adr1D: 0

Dead: 0

Alife: 1

Cont: 0

t1: 0

Birth: 3

Birth2 6

Survive: 2

Start: SUB(DimX,Survive,DimXa)

SUB(DimY,Survive,DimYa)

S1: GET1DFROM2DPOS(CntX,CntY,DimX,Adr1D)

LD(F1,Adr1D,Sum)

INC(CntX)

GET1DFROM2DPOS(CntX,CntY,DimX,Adr1D)

LD(F1,Adr1D,Cont)

ADD(Cont,Sum,t1)

INC(CntX)

GET1DFROM2DPOS(CntX,CntY,DimX,Adr1D)

LD(F1,Adr1D,Cont)

ADD(Cont,t1,Sum)

INC(CntY)

GET1DFROM2DPOS(CntX,CntY,DimX,Adr1D)

LD(F1,Adr1D,Cont)

ADD(Cont,Sum,t1)

DEC(CntX)

DEC(CntX)

GET1DFROM2DPOS(CntX,CntY,DimX,Adr1D)

LD(F1,Adr1D,Cont)

ADD(Cont,t1,Sum)

INC(CntY)

GET1DFROM2DPOS(CntX,CntY,DimX,Adr1D)

90

LD(F1,Adr1D,Cont)

ADD(Cont,Sum,t1)

INC(CntX)

GET1DFROM2DPOS(CntX,CntY,DimX,Adr1D)

LD(F1,Adr1D,Cont)

ADD(Cont,t1,Sum)

INC(CntX)

GET1DFROM2DPOS(CntX,CntY,DimX,Adr1D)

LD(F1,Adr1D,Cont)

ADD(Cont,Sum,t1)

DEC(CntX)

DEC(CntY)

GET1DFROM2DPOS(CntX,CntY,DimX,Adr1D)

EQ(t1,Survive,Next)

EQ(t1,Birth,Set)

// EQ(t1,Birth2,Set) }

ST(Ft,Adr1D,Dead)

JMP(Next)

Set: ST(Ft,Adr1D,Alife)

Next: DEC(CntY)

GT(DimXa,CntX,S1)

CLR(CntX)

INC(CntY)

GT(DimYa,CntY,S1)

CLR(CntX)

CLR(CntY)

S2: GET1DFROM2DPOS(CntX,CntY,DimX,Adr1D)

LD(Ft,Adr1D,Cont)

ST(F1,Adr1D,Cont)

INC(CntX)

GT(DimX,CntX,S2)

CLR(CntX)

INC(CntY)

GT(DimY,CntY,S2)

CLR(CntX)

CLR(CntY)

JMP(S1)

ZA programmiert auf RAMonTM

Das oben vorgeführte Programm simuliert einen zellularen

Automaten mit der S23B3-Regel und wird mit den Befehlen von

RAMonTM beschrieben. Somit könnte er auch auf einer Turing-

Maschine laufen. Da für diesen Automaten ein zweidimensionales

Feld benötigt wird, RAMonTM aber nur ein eindimensionales Feld

unterstützt, muss dieses simuliert werden. Hierfür gibt es das Makro

91

GET1DFROM2D. Es wandelt eine zweidimensionale Ortsangabe (X

und Y) in eine eindimensionale Adresse Pos1D in einem Feld um. In

der Variablem DimX ist die Ausdehnung des zweidimensionalen

Feldes in X-Richtung enthalten.

Das Programm ZA enthält zwei zweidimensionale Felder F1 und Ft.

In den eckigen Klammern stehen die Ausdehnungen in X- und Y-

Richtung. Der ZA arbeitet so, dass zunächst für eine Zelle die Summe

der Zustände der acht Nachbarzellen gebildet wird. Abhängig davon

wird im Feld Ft das Feld an der gleichen Position auf den Zustand

Dead (lebendig) oder Alife (tot) gesetzt, abhängig von der S23B3-

Regel. Dies wiederholt sich für alle vorhandenen Zellen.

Anschließend werden die berechneten Zustände vom Feld Ft nach F1

kopiert, und das Spiel beginnt wieder von vorne.

Erweitert man die S23B3-Regel zur S23B36-Regel, so ergibt sich ein

interessantes Objekt, nämlich ein sich selbst reproduzierendes

Element. Selbstreproduzierende Objekte sind wichtige Bestandteile

des Lebens und kommen auch in Zellen vor. Im obigen Automat

müsste nur der auskommentierte (Kommentarzeichen //) Befehl

eingefügt werden.

Selbstreproduzierendes Objekt in S23B36

92

12. Mach es noch mal, Fred!

In diesem kurzen Kapitel möchte ich auf einen Automatentypen

eingehen, der besonders in letzter Zeit durch die Forschung über

Quantencomputer an Popularität gewonnen hat. Es handelt sich um

sogenannte reversible Automaten. Dabei bedeutet Reversibilität, dass

aus den Ergebnissen von Operationen auf die Eingabe

zurückgeschlossen werden kann. Betrachtet man das Beispiel mit den

Neuronen, so verschwindet am Ausgang die Eingabe unwiderruflich

und kann nicht rekonstruiert werden. Das gleiche geschieht bei

logischen Bausteinen aus der Elektronik (AND, OR, NAND,...).

Fredkin [8] entwickelte einen Gatterbaustein, F-Gatter. Es kann alle

herkömmlichen logischen Gatter nachahmen und leitet zusätzliche

Information weiter, um diese logischen Funktionen reversibel

betreiben zu können.

F-Gatter

Das F-Gatter beinhaltet eine Kreuzung, die nur dann aktiv ist, wenn

die Steuerleitung c auf Null ist. Andernfalls werden die Signale auf

die gegenüberliegende Seite durchgeschleust. Wird das

Funktionsresultat erneut dem Baustein zugeführt, so erhält man

c c

p

q

X:=OR(AND(C,P),AND(NOT(C),q)))

Y:=OR(AND(NOT(C),P),AND(C,q)))

93

wieder die ursprüngliche Eingabe. Folglich ist dieser Baustein

reversibel.

c p q c X Y

0 0 0 0 0 0

0 0 1 0 1 0

0 1 0 0 0 1

0 1 1 0 1 1

1 0 0 1 0 0

1 0 1 1 0 1

1 1 0 1 1 0

1 1 1 1 1 1

Wahrheitstabelle des F-Gatters

Aus der obigen Wahrheitstabelle des F-Gatters sieht man, wie daraus

herkömmliche logische Schaltungen gewonnen werden können.

X := AND(p,c) bei q=0

Y := OR(b,c) bei q=1

Y := NOT(c) bei q=0 und p=1

Abbildung logischer Gatter durch das F-Gatter

Das F-Gatter kann auch durch zwei S(chalt)-Gatter ersetzt werden,

wobei das eine ein inverses S-Gatter ist. Diese haben den Vorteil,

dass sie auch als Billard-Maschine umgesetzt werden können. Dies

entspricht sozusagen einem mechanischen Automaten, der mit

Kugeln rechnet.

S-Gatter und inverses S-Gate

Das S-Gatter dient auch als Grundlage für die Billard-Maschine,

wobei sie in umgekehrter Richtung als inverses S-Gatter funktioniert.

In der nächsten Abbildung ist ein solcher Apparat dargestellt.

c c

p

X:=AND(p,c)

Y:=AND(p,NOT(c))

c c

p:=OR(X,Y) X

Y

94

Billard-Ball-Maschine (BBM)

Aus dieser BBM und aus dem S-Gatter lässt sich das F-Gatter von

Fredkin nachbilden, wie es in der unteren Skizze dargestellt ist.

F-Gatter dargestellt durch S-Gatter

Interessant sind reversible Automaten aus dem Grund, weil

Quantencomputer auch reversibel sind. Ausserdem geht bei

reversiblen Automaten keine Information verloren. Das bedeutet, dass

verlorene Information nicht in Wärme umgewandelt wird und somit

die Entropie nicht erhöht. Somit dürften solche Automaten sparsamer

mit Energie umgehen.

c

p Y

X

c

c c

p

q

X

Y

95

13. Wieviel wiegt eine Information?

Alle bisher vorgestellten Programme und Algorithmen haben eines

gemeinsam: Sie verarbeiten Informationen. Jede Beschreibung der

Maschinen ist selbst wieder Information. Jede Struktur in unserem

Universum ist Information. Ob es sich um ein Goldatom oder um ein

Sauerstoffatom handelt, hängt lediglich von der darin steckenden

Information ab. In unserer Welt braucht Information immer ein

Medium, auf dem es abgebildet oder gespeichert werden kann. Doch

was ist überhaupt Information? Kann man sie messen?

Physiker glauben, dass es drei Dinge in unserer Welt gibt: Materie,

Energie und Information. Dabei ist Information absolut eigenständig

von den anderen beiden Komponenten, und jeglicher Aufbau oder

Struktur von Energie oder Materie ist wiederum Information.

Grundlegend kann man festhalten, dass Information eine Folge von

Signalen ist, die in bestimmter Häufigkeit oder Wahrscheinlichkeit

auftritt. Dabei können diese Signale mit 0 und 1 dargestellt werden.

Wie lässt sich Information von einer zufälligen Abfolge von Zahlen

unterscheiden?

Hierzu muss man Information als Abweichung der Signalverteilung

vom statistischen Durchschnitt unabhängig vom Inhalt betrachten.

Anders formuliert hieße das, dass jede Folge von 0 und 1, die nicht

zufällig ist, Information enthält und zwar unabhängig davon, ob sie

interpretiert werden kann oder nicht. Aus diesem Grund muss auch

zwischen Informationsgehalt und Informationsmenge unterschieden

96

werden, wobei die kleinste Informationseinheit das vom Inhalt

unabhängige Bit ist. Zum Beispiel ist die Informations- bzw.

Datenmenge einer Münze beim Münzwurf 1 Bit. Erst das Ergebnis

beim Wurf ergibt den Inhalt. Hier handelt es sich um eine

Zufallsinformation, die zwischen zwei Möglichkeiten entscheidet.

Dabei berechnet sich die Informationsmenge wie folgt: I=lg2Z, wobei

Z die Anzahl der Entscheidungsmöglichkeiten ist. Bei der Münze sind

es insgesamt 2, folglich ist der Informationsgehalt I=1, da jeder Wurf

nur eine Informationseinheit liefern kann.

Die Grenze zwischen Zufallsinformation und nicht zufälliger

Information kann nicht genau gezogen werden. Eine geordnete Folge

kann zum Beispiel: 010101010101 lauten, eine zufällige Folge

hingegen: 100111010110. Beide Reihen sind gleich lang, und doch

unterscheiden sie sich. Setzt man die Menge an Zufall mit Entropie

gleich, so besitzt die erste Reihe eine Entropie nahe Null, während sie

bei der zweiten 12 Bit beträgt. Die erste Folge kann sehr einfach auf

6·’01’ verkürzt werden, während die zweite Folge nicht

komprimierbar ist. Ein Programm, das die zweite Folge erzeugen soll,

müsste diese komplett selbst enthalten, da sie algorithmisch nicht

reproduzierbar ist. Folglich ist jeder Algorithmus nichts anderes als

eine Kompression. Andererseits gibt es Pseudozufalls-

zahlengeneratoren, die algorithmisch Zahlenfolgen liefern, die von

echten Zufallszahlen schwer zu unterscheiden sind. Hier stellt sich die

Frage, ob es überhaupt wirklichen Zufall gibt, oder ob das ganze

Universum auch auf einem Algorithmus beruht.

97

14. Zusammenfassung

Einen Beweis für die Eindimensionalität des Universums gibt es nicht

wirklich. Höchstwahrscheinlich ist es auch gar nicht möglich, sie zu

beweisen. In diesem Buch habe ich aber versucht, beides zu

verbinden. Auf der einen Seite steht der Computer, mit dessen Hilfe

sich viele physikalische und biologische System nachahmen lassen.

Auf der anderen Seite ist unser Universum, dessen Vorgänge sich in

Formeln abbilden lassen, und das dadurch einem formalen logischen

System sehr ähnlich ist. Da ein Computer zu einer Turing-Maschine

mit ihrem eindimensionalen Band äquivalent ist, behaupte ich, dass

das Universum aus nur einer Dimension besteht und unser Gehirn

drei Dimensionen vortäuscht.

Natürlich ist es gewagt zu behaupten, dass unser Gehirn und unsere

Umwelt nur eine Simulation auf einer riesigen Turing-Maschine sind,

allerdings spricht auch nichts dagegen. Viele Physiker versuchen

bereits, die Grundlage quantenmechanischer Vorgänge aus der

informationstheoretischen Sicht zu erklären. Doch welches universale

System das wirklich grundlegende ist, wird ewig ein Geheimnis

bleiben.

98

Anhang

Für diejenigen, die es gerne praktisch haben, befinden sich hier im

Anhang einige Beispiele für Turing-Maschinen, die unter einem C-

Compiler übersetzt und ausgeführt werden können. Der Code kann

auch auf meiner Seite im Internet http://www.andrebetz.de

heruntergeladen werden.

Jede Maschine ist durch Makros definiert, die am Anfang jeder

Maschine angegeben werden und somit in der Programmdatei stehen

müssen.

#include <stdio.h>

#define F(A,B,C,D,E) if((s==A)&&(i==B)){n=C;w=D;m=E;h=1;}

#define VAR void main(){int h=1,s,p,n,w,m,i;

long k=0;char b[]={

#define BEGIN(A,B) };s=A;p=B;while(h){h=0;i=b[p];k++;

#define DEBUG printf("%ld %d (%2d,%c)

(%2d,%c,%c)\t",k,p,s,i,n,w,m);

#define ENDE printf("%s\n",b);s=n;b[p]=w;

if(m=='R')p++;else p--;}}

Makroblock für die Turing-Maschinen

Das Makro VAR definiert den Inhalt des Turingbandes, das Makro

BEGIN den Startzustand und die Startposition. In dem Makro F

stehen die Transitionen für die Turing-Maschine. DEBUG und ENDE

ermöglichen eine Ausgabe auf dem Bildschirm. Die Maschine hält

an, wenn ein Zustand angesprungen wird, der nicht existiert.

99

UTM von Marvin Minsky

VAR "11x1100y01x00001x01111x10011x11111y"

BEGIN('00',10)

F('00','0','00','a','L') F('00','1','00','b','L')

F('00','a','00','a','L') F('00','b','00','b','L')

F('00','x','00','x','L') F('00','y','01','y','R')

F('01','0','01','0','R') F('01','1','01','1','R')

F('01','a','02','0','R') F('01','b','04','1','R')

F('01','x','06','x','R')

F('02','0','03','a','L') F('02','1','05','b','R')

F('02','a','02','a','R') F('02','b','02','b','R')

F('02','x','02','x','R') F('03','0','03','0','L')

F('03','1','03','1','L') F('03','a','03','a','L')

F('03','b','03','b','L') F('03','x','03','x','L')

F('03','y','01','y','R') F('04','0','05','a','R')

F('04','1','03','b','L') F('04','a','04','a','R')

F('04','b','04','b','R') F('04','x','04','x','R')

F('05','0','05','0','R') F('05','1','05','1','R')

F('05','a','05','a','R') F('05','b','05','b','R')

F('05','x','00','x','L') F('05','y','26','y','R')

F('06','0','07','a','L') F('06','1','08','b','L')

F('06','a','06','a','R') F('06','b','06','b','R')

F('06','x','06','x','R') F('07','0','07','0','L')

F('07','1','07','1','L') F('07','a','07','a','L')

F('07','b','07','b','L') F('07','x','07','x','L')

F('07','y','09','y','R') F('08','0','08','0','L')

F('08','1','08','1','L') F('08','a','08','a','L')

F('08','b','08','b','L') F('08','x','08','x','L')

F('08','y','10','y','R') F('09','0','11','a','R')

F('09','1','11','a','R') F('09','a','09','a','R')

F('09','b','09','b','R') F('09','x','12','x','L')

F('10','0','11','b','R') F('10','1','11','b','R')

F('10','a','10','a','R')

F('10','b','10','b','R') F('10','x','13','x','L')

F('11','0','11','0','R') F('11','1','11','1','R')

F('11','a','11','a','R')

F('11','b','11','b','R') F('11','x','06','x','R')

F('12','0','12','0','L') F('12','1','12','1','L')

F('12','a','12','a','L') F('12','b','12','b','L')

F('12','x','14','a','R') F('12','y','12','y','L')

F('13','0','13','0','L') F('13','1','13','1','L')

F('13','a','13','a','L') F('13','b','13','b','L')

F('13','x','14','b','R') F('13','y','13','y','L')

F('14','0','14','0','R') F('14','1','14','1','R')

F('14','a','14','0','R') F('14','b','14','1','R')

F('14','x','15','x','R') F('14','y','14','y','R')

F('15','0','16','0','L') F('15','1','16','1','L')

F('15','a','15','a','R') F('15','b','15','b','R')

F('15','x','15','x','R') F('15','y','15','y','R')

F('16','0','17','x','L') F('16','1','18','x','L')

F('16','a','16','0','L') F('16','b','16','1','L')

F('16','x','16','x','L') F('16','y','16','y','L')

F('17','0','17','0','L') F('17','1','17','1','L')

100

F('17','a','20','0','L') F('17','b','19','0','R')

F('17','x','17','x','L') F('17','y','17','y','L')

F('18','0','18','0','L') F('18','1','18','1','L')

F('18','a','20','1','L') F('18','b','19','1','R')

F('18','x','18','x','L') F('18','y','18','y','L')

F('19','0','21','x','R') F('19','1','22','x','R')

F('20','0','21','x','R') F('20','1','22','x','R')

F('21','0','21','0','R') F('21','1','21','1','R')

F('21','a','21','a','R') F('21','b','21','b','R')

F('21','x','00','a','L') F('21','y','21','y','R')

F('22','0','22','0','R') F('22','1','22','1','R')

F('22','a','22','a','R') F('22','b','22','b','R')

F('22','x','00','b','L') F('22','y','22','y','R')

DEBUG

ENDE

101

UTM von Penrose

VAR

"0000000000000000000000000101011010111101010111110000111100000000000"

BEGIN('000',0)

F('000','0','000','0','R') F('000','1','020','1','L')

F('001','0','001','0','R') F('001','1','155','1','R')

F('002','0','002','0','R') F('002','1','098','1','R')

F('003','0','091','1','L') F('003','1','041','1','L')

F('004','0','004','0','L') F('004','1','105','1','L')

F('005','0','005','0','L') F('005','1','111','1','L')

F('006','0','006','0','R') F('006','1','116','0','R')

F('007','0','007','0','L') F('007','1','121','1','L')

F('008','0','008','0','R') F('008','1','127','1','R')

F('009','0','009','0','L') F('009','1','150','1','L')

F('010','0','010','0','L') F('010','1','161','1','L')

F('011','0','011','0','L') F('011','1','166','1','L')

F('012','0','012','0','L') F('012','1','172','1','L')

F('013','0','013','0','R') F('013','1','179','1','R')

F('014','0','014','0','L') F('014','1','183','0','L')

F('015','0','015','0','R') F('015','1','192','1','R')

F('016','0','085','0','R') F('016','1','016','1','R')

F('017','0','024','1','R') F('017','1','017','1','R')

F('018','0','060','1','R') F('018','1','018','1','R')

F('019','0','019','0','R') F('019','1','064','0','L')

F('020','0','037','0','L') F('020','1','001','0','R')

F('021','0','022','1','L') F('021','1','139','1','R')

F('022','0','038','1','L') F('022','1','027','0','L')

F('023','0','002','0','R') F('023','1','023','1','R')

F('024','0','024','0','R') F('024','1','115','0','R')

F('025','0','066','0','R') F('025','1','026','0','R')

F('026','0','008','0','R') F('026','1','026','1','R')

F('027','0','140','1','L') F('027','1','027','1','L')

F('028','0','028','0','L') F('028','1','149','1','L')

F('029','0','154','1','R') F('029','1','029','1','L')

F('030','0','030','0','L') F('030','1','171','1','L')

F('031','0','014','1','L') F('031','1','031','1','L')

F('032','0','032','0','L') F('032','1','187','0','L')

F('033','0','033','0','R') F('033','1','190','1','R')

F('034','0','034','0','R') F('034','1','197','1','R')

F('035','0','035','0','L') F('035','1','199','0','L')

F('036','0','036','0','L') F('036','1','200','0','L')

F('037','0','021','1','L') F('037','1','038','1','L')

F('038','0','039','1','L') F('038','1','039','1','L')

F('039','0','040','1','L') F('039','1','046','1','L')

F('040','0','041','0','L') F('040','1','049','1','L')

F('041','0','042','1','L') F('041','1','042','1','L')

F('042','0','043','1','L') F('042','1','043','0','R')

F('043','0','044','1','L') F('043','1','044','1','R')

F('044','0','045','1','L') F('044','1','046','1','R')

F('045','0','023','1','R') F('045','1','051','0','L')

F('046','0','103','1','R') F('046','1','040','1','L')

F('047','0','023','1','R') F('047','1','047','1','L')

F('048','0','037','0','L') F('048','1','048','1','R')

102

F('049','0','017','1','R') F('049','1','050','0','L')

F('050','0','005','0','L') F('050','1','050','1','L')

F('051','0','052','1','L') F('051','1','051','1','L')

F('052','0','053','1','L') F('052','1','053','1','L')

F('053','0','054','1','L') F('053','1','054','1','L')

F('054','0','055','1','L') F('054','1','057','1','L')

F('055','0','056','1','L') F('055','1','011','0','L')

F('056','0','057','1','L') F('056','1','012','0','L')

F('057','0','058','0','L') F('057','1','081','0','L')

F('058','0','049','0','L') F('058','1','020','1','R')

F('059','0','006','1','R') F('059','1','059','1','R')

F('060','0','060','1','R') F('060','1','061','0','R')

F('061','0','062','1','L') F('061','1','061','0','R')

F('062','0','062','1','L') F('062','1','063','0','L')

F('063','0','019','1','R') F('063','1','063','1','L')

F('064','0','064','0','L') F('064','1','125','0','L')

F('065','0','025','0','R') F('065','1','065','1','R')

F('066','0','066','1','R') F('066','1','026','1','R')

F('067','0','133','0','L') F('067','1','067','1','R')

F('068','0','021','0','R') F('068','1','068','1','L')

F('069','0','070','0','R') F('069','1','070','1','R')

F('070','0','022','0','R') F('070','1','022','1','R')

F('071','0','141','1','L') F('071','1','071','1','L')

F('072','0','146','0','R') F('072','1','072','1','R')

F('073','0','073','0','L') F('073','1','074','1','L')

F('074','0','148','0','L') F('074','1','074','1','L')

F('075','0','076','0','R') F('075','1','076','0','R')

F('076','0','075','1','R') F('076','1','077','1','L')

F('077','0','077','1','R') F('077','1','078','1','R')

F('078','0','001','0','R') F('078','1','078','1','R')

F('079','0','080','1','L') F('079','1','079','1','R')

F('080','0','030','1','L') F('080','1','052','1','L')

F('081','0','010','0','L') F('081','1','081','1','L')

F('082','0','019','1','R') F('082','1','082','1','L')

F('083','0','165','0','R') F('083','1','083','1','L')

F('084','0','170','0','R') F('084','1','084','1','L')

F('085','0','086','0','R') F('085','1','085','1','R')

F('086','0','027','0','L') F('086','1','086','1','R')

F('087','0','058','0','R') F('087','1','087','1','L')

F('088','0','056','0','R') F('088','1','088','1','L')

F('089','0','025','0','R') F('089','1','089','1','L')

F('090','0','020','0','R') F('090','1','090','1','L')

F('091','0','091','0','L') F('091','1','092','1','L')

F('092','0','177','1','L') F('092','1','092','1','L')

F('093','0','013','0','R') F('093','1','093','1','R')

F('094','0','032','1','L') F('094','1','094','1','L')

F('095','0','015','0','R') F('095','1','095','1','R')

F('096','0','096','0','L') F('096','1','097','0','L')

F('097','0','198','0','L') F('097','1','097','0','L')

F('098','0','002','0','R') F('098','1','099','1','R')

F('099','0','002','0','R') F('099','1','100','1','R')

F('100','0','002','0','R') F('100','1','101','1','R')

F('101','0','002','0','R') F('101','1','102','1','R')

F('102','0','003','0','L') F('102','1','109','1','R')

F('103','0','003','0','L') F('103','1','104','1','R')

F('104','0','003','0','L') F('104','1','004','1','L')

103

F('105','0','004','0','L') F('105','1','106','1','L')

F('106','0','004','0','L') F('106','1','107','1','L')

F('107','0','004','0','L') F('107','1','108','1','L')

F('108','0','004','0','L') F('108','1','047','1','L')

F('109','0','003','0','L') F('109','1','110','1','R')

F('110','0','003','0','L') F('110','1','048','1','R')

F('111','0','005','0','L') F('111','1','112','1','L')

F('112','0','005','0','L') F('112','1','113','1','L')

F('113','0','005','0','L') F('113','1','114','1','L')

F('114','0','005','0','L') F('114','1','045','0','L')

F('115','0','024','1','R') F('115','1','059','1','R')

F('116','0','006','1','R') F('116','1','117','1','R')

F('117','0','006','1','R') F('117','1','118','1','R')

F('118','0','006','1','R') F('118','1','119','1','R')

F('119','0','006','1','R') F('119','1','120','1','R')

F('120','0','007','1','L') F('120','1','009','1','L')

F('121','0','007','0','L') F('121','1','122','1','L')

F('122','0','007','0','L') F('122','1','123','1','L')

F('123','0','007','0','L') F('123','1','124','1','L')

F('124','0','007','0','L') F('124','1','018','1','R')

F('125','0','019','1','R') F('125','1','126','1','L')

F('126','0','075','0','R') F('126','1','065','1','R')

F('127','0','008','0','R') F('127','1','128','1','R')

F('128','0','008','0','R') F('128','1','129','1','R')

F('129','0','008','0','R') F('129','1','130','1','R')

F('130','0','008','0','R') F('130','1','131','1','R')

F('131','0','088','1','L') F('131','1','132','1','R')

F('132','0','083','1','L') F('132','1','067','1','R')

F('133','0','000','0','R') F('133','1','134','1','L')

F('134','0','000','0','R') F('134','1','135','1','L')

F('135','0','000','0','R') F('135','1','136','1','L')

F('136','0','000','0','R') F('136','1','137','1','L')

F('137','0','000','0','R') F('137','1','138','1','L')

F('138','0','000','0','R') F('138','1','068','0','L')

F('139','0','069','0','R') F('139','1','069','1','R')

F('140','0','000','0','R') F('140','1','071','0','L')

F('141','0','021','0','R') F('141','1','142','0','L')

F('142','0','016','0','R') F('142','1','143','1','L')

F('143','0','016','0','R') F('143','1','144','1','L')

F('144','0','016','0','R') F('144','1','145','1','L')

F('145','0','016','0','R') F('145','1','072','1','R')

F('146','0','000','0','R') F('146','1','147','0','R')

F('147','0','073','1','L') F('147','1','176','0','R')

F('148','0','028','0','L') F('148','1','080','0','R')

F('149','0','028','0','L') F('149','1','017','0','R')

F('150','0','009','0','L') F('150','1','151','1','L')

F('151','0','009','0','L') F('151','1','152','1','L')

F('152','0','009','0','L') F('152','1','153','1','L')

F('153','0','009','0','L') F('153','1','029','1','L')

F('154','0','000','0','R') F('154','1','018','0','R')

F('155','0','001','0','R') F('155','1','156','1','R')

F('156','0','001','0','R') F('156','1','157','1','R')

F('157','0','001','0','R') F('157','1','158','1','R')

F('158','0','001','0','R') F('158','1','159','1','R')

F('159','0','090','1','L') F('159','1','160','1','R')

F('160','0','087','1','L') F('160','1','079','1','R')

104

F('161','0','010','0','L') F('161','1','162','1','L')

F('162','0','010','0','L') F('162','1','163','1','L')

F('163','0','010','0','L') F('163','1','164','1','L')

F('164','0','010','0','L') F('164','1','082','1','L')

F('165','0','000','0','R') F('165','1','055','1','R')

F('166','0','011','0','L') F('166','1','167','1','L')

F('167','0','011','0','L') F('167','1','168','1','L')

F('168','0','011','0','L') F('168','1','169','1','L')

F('169','0','011','0','L') F('169','1','084','1','L')

F('170','0','000','0','R') F('170','1','025','1','R')

F('171','0','030','0','L') F('171','1','017','1','R')

F('172','0','012','0','L') F('172','1','173','1','L')

F('173','0','012','0','L') F('173','1','174','1','L')

F('174','0','012','0','L') F('174','1','175','1','L')

F('175','0','012','0','L') F('175','1','089','1','L')

F('176','0','003','1','L') F('176','1','096','0','L')

F('177','0','178','0','R') F('177','1','095','0','R')

F('178','0','000','0','R') F('178','1','093','0','R')

F('179','0','013','0','R') F('179','1','180','1','R')

F('180','0','013','0','R') F('180','1','181','1','R')

F('181','0','013','0','R') F('181','1','182','1','R')

F('182','0','013','0','R') F('182','1','031','0','L')

F('183','0','014','1','L') F('183','1','184','1','L')

F('184','0','014','1','L') F('184','1','185','1','L')

F('185','0','014','1','L') F('185','1','186','1','L')

F('186','0','014','1','L') F('186','1','094','1','L')

F('187','0','032','1','L') F('187','1','188','1','L')

F('188','0','196','1','R') F('188','1','189','1','R')

F('189','0','000','0','R') F('189','1','033','1','R')

F('190','0','033','0','R') F('190','1','191','1','L')

F('191','0','000','0','R') F('191','1','029','1','L')

F('192','0','015','0','R') F('192','1','193','1','R')

F('193','0','015','0','R') F('193','1','194','1','R')

F('194','0','015','0','R') F('194','1','195','1','R')

F('195','0','015','0','R') F('195','1','031','1','L')

F('196','0','000','0','R') F('196','1','034','1','R')

F('197','0','034','0','R') F('197','1','018','1','R')

F('198','0','036','0','L') F('198','1','035','0','L')

F('199','0','035','0','L') F('199','1','201','1','R')

F('200','0','036','0','L') F('200','1','201','0','R')

DEBUG

ENDE

105

RAMonTM

VAR "PxxxPxxxL000D110L001D011L010D100L011D001Lx"

BEGIN('000',0)

F('000','0','000','0','L') F('000','1','000','1','L')

F('000','x','000','x','L') F('000','y','000','y','L')

F('000','P','001','P','R') F('000','L','000','L','L')

F('000','D','000','D','L')

F('001','x','002','0','R') F('001','y','004','1','R')

F('001','P','009','P','R')

F('002','0','003','x','L') F('002','1','006','y','R')

F('002','x','002','x','R') F('002','y','002','y','R')

F('002','P','002','P','R') F('002','L','002','L','R')

F('002','D','002','D','R')

F('003','0','001','0','R') F('003','1','001','1','R')

F('003','x','003','x','L') F('003','y','003','y','L')

F('003','P','003','P','L') F('003','L','003','L','L')

F('003','D','003','D','L')

F('004','0','006','x','R') F('004','1','005','y','L')

F('004','x','004','x','R') F('004','y','004','y','R')

F('004','P','004','P','R') F('004','L','004','L','R')

F('004','D','004','D','R')

F('005','0','001','0','R') F('005','1','001','1','R')

F('005','x','005','x','L') F('005','y','005','y','L')

F('005','P','005','P','L') F('005','L','005','L','L')

F('005','D','005','D','L')

F('006','x','110','x','L') F('006','0','006','x','R')

F('006','1','006','y','R')

F('006','L','007','L','L') F('006','D','006','D','R')

F('007','0','008','x','L') F('008','1','007','y','L')

F('007','x','007','x','L')

F('007','y','007','y','L') F('007','P','008','P','L')

F('007','L','007','L','L') F('007','D','007','D','L')

F('008','0','008','x','L') F('008','1','008','y','L')

F('008','x','008','x','L')

F('008','y','008','y','L') F('008','P','001','P','R')

F('009','0','010','x','R') F('009','1','011','y','R')

F('009','x','009','x','R') F('009','y','009','y','R')

F('009','P','009','P','R') F('009','L','009','L','R')

F('009','D','009','D','R')

F('010','0','012','x','R') F('010','1','013','y','R')

F('011','0','014','x','R') F('011','1','015','y','R')

F('012','0','012','x','R') F('012','1','012','y','R')

F('012','L','012','L','R') F('012','D','054','D','R')

F('013','0','013','x','R') F('013','1','013','y','R')

F('013','L','013','L','R') F('013','D','072','D','R')

F('014','0','014','x','R') F('014','1','014','y','R')

F('014','L','014','L','R') F('014','D','091','D','R')

F('015','0','015','x','R') F('015','1','015','y','R')

F('015','L','015','L','R') F('015','D','016','D','R')

F('016','0','017','x','L') F('016','1','019','y','L')

F('016','x','016','x','R') F('016','y','016','y','R')

F('016','P','016','P','R') F('016','L','016','L','R')

F('016','D','016','D','R')

106

F('017','0','018','0','R') F('017','1','018','1','R')

F('017','x','017','x','L') F('017','y','017','y','L')

F('017','P','018','P','R') F('017','L','017','L','L')

F('017','D','017','D','L')

F('018','x','021','0','R') F('018','y','021','0','R')

F('019','0','020','0','R') F('019','1','020','1','R')

F('019','x','019','x','L') F('019','y','019','y','L')

F('019','P','020','P','R') F('019','L','019','L','L')

F('019','D','019','D','L')

F('020','x','021','1','R') F('020','y','021','1','R')

F('021','x','016','x','R') F('021','y','016','y','R')

F('021','L','022','L','R')

F('022','0','023','x','R') F('022','1','023','y','R')

F('022','x','022','x','R') F('022','y','022','y','R')

F('022','P','022','P','R') F('022','L','022','L','R')

F('022','D','022','D','R')

F('023','0','023','x','R') F('023','1','023','y','R')

F('023','D','024','P','L')

F('024','0','024','x','L') F('024','1','024','y','L')

F('024','x','024','0','L') F('024','y','024','1','L')

F('024','P','025','P','R') F('024','L','024','L','L')

F('024','D','024','D','L')

F('025','x','026','0','R') F('025','y','028','1','R')

F('025','L','033','L','L')

F('026','0','027','x','L') F('026','1','030','y','R')

F('026','x','026','x','R') F('026','y','026','y','R')

F('026','P','026','P','R') F('026','L','026','L','R')

F('026','D','026','D','R')

F('027','0','025','0','R') F('027','1','025','1','R')

F('027','x','027','x','L') F('027','y','027','y','L')

F('027','P','027','P','L') F('027','L','027','L','L')

F('027','D','027','D','L')

F('028','0','030','x','R') F('028','1','029','y','L')

F('028','x','028','x','R') F('028','y','028','y','R')

F('028','P','028','P','R') F('028','L','028','L','R')

F('028','D','028','D','R')

F('029','0','025','0','R') F('029','1','025','1','R')

F('029','x','029','x','L') F('029','y','029','y','L')

F('029','P','029','P','L') F('029','L','029','L','L')

F('029','D','029','D','L')

F('030','0','030','x','R') F('030','1','030','y','R')

F('030','P','030','P','R') F('030','L','031','L','L')

F('030','D','030','D','R')

F('031','0','032','x','L') F('031','1','032','y','L')

F('031','x','031','x','L') F('031','y','031','y','L')

F('031','P','031','P','L') F('031','L','031','L','L')

F('031','D','031','D','L')

F('032','0','032','x','L') F('032','1','032','y','L')

F('032','P','025','P','R')

F('033','0','033','x','L') F('033','1','033','y','L')

F('033','P','034','P','L')

F('034','0','034','x','L') F('034','1','034','y','L')

F('034','P','035','P','R')

F('035','x','036','0','R') F('035','y','036','0','R')

F('036','x','036','x','R') F('036','y','036','y','R')

F('036','P','036','P','R') F('036','L','037','L','R')

107

F('037','0','038','0','R') F('037','1','039','1','R')

F('037','x','037','0','R') F('037','y','037','1','R')

F('037','P','037','P','R') F('037','L','037','L','R')

F('037','D','037','D','R')

F('038','0','038','0','R') F('038','1','039','1','L')

F('038','L','045','L','L')

F('039','0','039','0','L') F('039','1','039','1','L')

F('039','x','040','x','R') F('039','y','040','y','R')

F('039','P','039','P','L') F('039','L','039','L','L')

F('039','D','039','D','L')

F('040','0','040','x','R') F('040','1','040','y','R')

F('040','P','041','D','R') F('040','L','040','L','R')

F('040','D','040','D','R')

F('041','0','042','x','L') F('041','1','043','y','L')

F('041','x','041','x','R') F('041','y','041','y','R')

F('041','P','041','P','R') F('041','L','041','L','R')

F('041','D','041','D','R')

F('042','0','044','x','R') F('042','1','044','x','R')

F('042','x','042','x','L') F('042','y','042','y','L')

F('042','P','042','P','L') F('042','L','042','L','L')

F('042','D','042','D','L')

F('043','0','044','y','R') F('043','1','044','y','R')

F('043','x','043','x','L') F('043','y','043','y','L')

F('043','P','043','P','L') F('043','L','043','L','L')

F('043','D','043','D','L')

F('044','x','041','0','R') F('044','y','041','1','R')

F('044','P','000','P','L')

F('045','0','045','0','L') F('045','1','045','1','L')

F('045','x','046','x','L') F('045','y','046','y','L')

F('045','P','045','D','L') F('045','L','045','L','L')

F('045','D','045','D','L')

F('046','x','046','x','L') F('046','y','046','y','L')

F('046','P','047','P','L')

F('047','0','048','y','L') F('047','1','047','x','L')

F('047','x','048','y','L') F('047','y','047','x','L')

F('047','P','049','P','R')

F('048','0','048','x','L') F('048','1','048','y','L')

F('048','x','048','x','L')

F('048','y','048','y','L') F('048','P','049','P','R')

F('049','x','049','x','R') F('049','y','049','y','R')

F('049','P','050','P','L')

F('050','0','051','y','L') F('050','1','050','x','L')

F('050','x','051','y','L') F('050','y','050','x','L')

F('050','P','052','P','R')

F('051','0','051','x','L') F('051','1','051','y','L')

F('051','x','051','x','L') F('051','y','051','y','L')

F('051','P','052','P','R')

F('052','x','052','x','R') F('052','y','052','y','R')

F('052','P','053','P','L')

F('053','x','000','y','L') F('053','y','053','x','L')

F('053','P','001','P','R')

F('054','0','055','x','L') F('054','1','057','y','L')

F('054','x','054','x','R') F('054','y','054','y','R')

F('054','P','054','P','R') F('054','L','054','L','R')

F('054','D','054','D','R')

F('055','0','056','0','R') F('055','1','056','1','R')

108

F('055','x','055','x','L') F('055','y','055','y','L')

F('055','P','056','P','R') F('055','L','055','L','L')

F('055','D','055','D','L')

F('056','x','059','0','R') F('056','y','059','0','R')

F('057','0','058','0','R') F('057','1','058','1','R')

F('057','x','057','x','L') F('057','y','057','y','L')

F('057','P','058','P','R') F('057','L','057','L','L')

F('057','D','057','D','L')

F('058','x','059','1','R') F('058','y','059','1','R')

F('059','x','054','x','R') F('059','y','054','y','R')

F('059','L','060','L','R')

F('060','0','061','0','L') F('060','1','061','1','L')

F('060','x','060','x','R') F('060','y','060','y','R')

F('060','P','060','P','R') F('060','L','060','L','R')

F('060','D','060','D','R')

F('061','0','061','x','L') F('061','1','061','y','L')

F('061','x','061','0','L') F('061','y','061','1','L')

F('061','P','062','P','R') F('061','L','061','L','L')

F('061','D','061','D','L')

F('062','x','063','0','R') F('062','y','065','1','R')

F('062','L','069','L','R')

F('063','0','064','x','L') F('063','1','067','y','R')

F('063','x','063','x','R') F('063','y','063','y','R')

F('063','P','063','P','R') F('063','L','063','L','R')

F('063','D','063','D','R')

F('064','0','062','0','R') F('064','1','062','1','R')

F('064','x','064','x','L') F('064','y','064','y','L')

F('064','P','064','P','L') F('064','L','064','L','L')

F('064','D','064','D','L')

F('065','0','067','x','R') F('065','1','066','y','L')

F('065','x','065','x','R') F('065','y','065','y','R')

F('065','P','065','P','R') F('065','L','065','L','R')

F('065','D','065','D','R')

F('066','0','062','0','R') F('066','1','062','1','R')

F('066','x','066','x','L') F('066','y','066','y','L')

F('066','P','066','P','L') F('066','L','066','L','L')

F('066','D','066','D','L')

F('067','0','067','x','R') F('067','1','067','y','R')

F('067','P','067','P','R') F('067','L','068','L','L')

F('067','D','067','D','R')

F('068','0','068','x','L') F('068','1','068','y','L')

F('068','x','068','x','L') F('068','y','068','y','L')

F('068','P','062','P','R') F('068','L','068','L','L')

F('068','D','068','D','L')

F('069','0','070','x','R') F('069','1','070','x','R')

F('069','x','069','x','R') F('069','y','069','y','R')

F('069','P','069','P','R') F('069','L','069','L','R')

F('069','D','069','D','R')

F('070','0','070','x','R') F('070','1','070','x','R')

F('070','L','071','L','L')

F('071','0','071','x','L') F('071','1','071','x','L')

F('071','x','071','0','L') F('071','y','071','1','L')

F('071','P','050','P','L') F('071','L','071','L','L')

F('071','D','071','D','L')

F('072','0','073','x','L') F('072','1','075','y','L')

F('072','x','072','x','R') F('072','y','072','y','R')

109

F('072','P','072','P','R') F('072','L','072','L','R')

F('072','D','072','D','R')

F('073','0','074','0','R') F('073','1','074','1','R')

F('073','x','073','x','L') F('073','y','073','y','L')

F('073','P','074','P','R') F('073','L','073','L','L')

F('073','D','073','D','L')

F('074','x','077','0','R') F('074','y','077','0','R')

F('075','0','076','0','R') F('075','1','076','1','R')

F('075','x','075','x','L') F('075','y','075','y','L')

F('075','P','076','P','R') F('075','L','075','L','L')

F('075','D','075','D','L')

F('076','x','077','1','R') F('076','y','077','1','R')

F('077','x','072','x','R') F('077','y','072','y','R')

F('077','L','078','L','R')

F('078','0','079','0','L') F('078','1','079','1','L')

F('078','x','078','x','R') F('078','y','078','y','R')

F('078','P','078','P','R') F('078','L','078','L','R')

F('078','D','078','D','R')

F('079','0','079','x','L') F('079','1','079','y','L')

F('079','x','079','0','L') F('079','y','079','1','L')

F('079','P','080','P','R') F('079','L','079','L','L')

F('079','D','079','D','L')

F('080','x','081','0','R') F('080','y','083','1','R')

F('080','L','087','L','R')

F('081','0','082','x','L') F('081','1','085','y','R')

F('081','x','081','x','R') F('081','y','081','y','R')

F('081','P','081','P','R') F('081','L','081','L','R')

F('081','D','081','D','R')

F('082','0','080','0','R') F('082','1','080','1','R')

F('082','x','082','x','L') F('082','y','082','y','L')

F('082','P','082','P','L') F('082','L','082','L','L')

F('082','D','082','D','L')

F('083','0','085','x','R') F('083','1','084','y','L')

F('083','x','083','x','R') F('083','y','083','y','R')

F('083','P','083','P','R') F('083','L','083','L','R')

F('083','D','083','D','R')

F('084','0','080','0','R') F('084','1','080','1','R')

F('084','x','084','x','L') F('084','y','084','y','L')

F('084','P','084','P','L') F('084','L','084','L','L')

F('084','D','084','D','L')

F('085','0','085','x','R') F('085','1','085','y','R')

F('085','P','085','P','R') F('085','L','086','L','L')

F('085','D','085','D','R')

F('086','0','086','x','L') F('086','1','086','y','L')

F('086','x','086','x','L') F('086','y','086','y','L')

F('086','P','080','P','R') F('086','L','086','L','L')

F('086','D','086','D','L')

F('087','0','088','0','R') F('087','1','088','1','R')

F('087','x','087','x','R') F('087','y','087','y','R')

F('087','L','087','L','R') F('087','D','087','D','R')

F('088','0','088','0','R') F('088','1','088','1','R')

F('088','L','089','L','L')

F('089','0','090','1','L') F('089','1','089','0','L')

F('089','D','071','D','L')

F('090','0','090','0','L') F('090','1','090','1','L')

F('090','D','071','D','L')

110

F('091','0','092','x','L') F('091','1','094','y','L')

F('091','x','091','x','R') F('091','y','091','y','R')

F('091','P','091','P','R') F('091','L','091','L','R')

F('091','D','091','D','R')

F('092','0','093','0','R') F('092','1','093','1','R')

F('092','x','092','x','L') F('092','y','092','y','L')

F('092','P','093','P','R') F('092','L','092','L','L')

F('092','D','092','D','L')

F('093','x','096','0','R') F('093','y','096','0','R')

F('094','0','095','0','R') F('094','1','095','1','R')

F('094','x','094','x','L') F('094','y','094','y','L')

F('094','P','095','P','R') F('094','L','094','L','L')

F('094','D','094','D','L')

F('095','x','096','1','R') F('095','y','096','1','R')

F('096','x','091','x','R') F('096','y','091','y','R')

F('096','L','097','L','R')

F('097','0','098','0','L') F('097','1','098','1','L')

F('097','x','097','x','R') F('097','y','097','y','R')

F('097','P','097','P','R') F('097','L','097','L','R')

F('097','D','097','D','R')

F('098','0','098','x','L') F('098','1','098','y','L')

F('098','x','098','0','L') F('098','y','098','1','L')

F('098','P','099','P','R') F('098','L','098','L','L')

F('098','D','098','D','L')

F('099','x','100','0','R') F('099','y','102','1','R')

F('099','L','106','L','R')

F('100','0','101','x','L') F('100','1','104','y','R')

F('100','x','100','x','R') F('100','y','100','y','R')

F('100','P','100','P','R') F('100','L','100','L','R')

F('100','D','100','D','R')

F('101','0','099','0','R') F('101','1','099','1','R')

F('101','x','101','x','L') F('101','y','101','y','L')

F('101','P','101','P','L') F('101','L','101','L','L')

F('101','D','101','D','L')

F('102','0','104','x','R') F('102','1','103','y','L')

F('102','x','102','x','R') F('102','y','102','y','R')

F('102','P','102','P','R') F('102','L','102','L','R')

F('102','D','102','D','R')

F('103','0','099','0','R') F('103','1','099','1','R')

F('103','x','103','x','L') F('103','y','103','y','L')

F('103','P','103','P','L') F('103','L','103','L','L')

F('103','D','103','D','L')

F('104','0','104','x','R') F('104','1','104','y','R')

F('104','P','104','P','R') F('104','L','105','L','L')

F('104','D','104','D','R')

F('105','0','105','x','L') F('105','1','105','y','L')

F('105','x','105','x','L') F('105','y','105','y','L')

F('105','P','099','P','R') F('105','L','105','L','L')

F('105','D','105','D','L')

F('106','0','107','0','R') F('106','1','107','1','R')

F('106','x','106','x','R') F('106','y','106','y','R')

F('106','L','106','L','R') F('106','D','106','D','R')

F('107','0','107','0','R') F('107','1','107','1','R')

F('107','L','108','L','L')

F('108','0','108','1','L') F('108','1','109','0','L')

F('108','D','071','D','L')

111

F('109','0','109','0','L') F('109','1','109','1','L')

F('109','D','071','D','L')

DEBUG

ENDE

112

Literaturverzeichnis

[1] Allan M. Turing, On computable numbers, with an application to

the Entscheidungsproblem, 1936

[2] Marvin L. Minsky, Berechnung: Endliche und unendliche

Maschinen, Berliner Union, Stuttgart, 1971.

[3] Roger Penrose, The emporers new mind, Oxford University Press,

1989

[4] Stephen Wolfram, A new kind of science, ,2002

[5] Rojas, Theorie der neuronalen Netze; Springer, 1993

[6] Paul Rendell, A Turing Machine in Conway’s Game of Life

[7] http://www.usc.edu/dept/molecular-science/fm-adleman.htm

[8] http://www.alife.co.uk/ca/bbm/2d/

André BetzDas eindimensionale UniversumISBN: 3-8330-0370-7

Korrekturen:

Seite 2: Kapitel 6 kommt zweimal vorSeite 3: letzter Absatz: ... Mathematik und der eines ComputersSeite 37:

MAKRO:CLR(A)

Start:BNZ(A,t1)

JMP(End)

t1: DEC(A)

JMP(Start)

End:

CLR-Befehl (A=0)Seite 57:

y c b a x

0 1 c L 1 y R 0 x R 0 x R 0 y L1 1 b L 1 y R 0 y R 0 x R 0 c L