Städtisches Labenwolf-Gymnasium Nürnberg Kollegstufe 2001/2003 Schuljahr 2002/2003 Facharbeit aus dem Fach Mathematik Thema: Die Turingmaschine Verfasser: Stefan Thomas Schorsch Kursleiter: Hans Gaab Abgabetermin: 3.Februrar 2003 Wertung: Erzielte Punktzahl (einfache Wertung): ....... in Worten: ............................................................... ................................................................................................................................... Kursleiter Hans Gaab
Transcript
Städtisches Labenwolf-Gymnasium Nürnberg
Kollegstufe 2001/2003 Schuljahr 2002/2003
Facharbeit aus dem Fach Mathematik
Thema: Die Turingmaschine Verfasser: Stefan Thomas Schorsch Kursleiter: Hans Gaab Abgabetermin: 3.Februrar 2003 Wertung: Erzielte Punktzahl (einfache Wertung): ....... in Worten: ............................................................... ................................................................................................................................... Kursleiter Hans Gaab
1. Einleitung Seite 03 2. Das Prinzip Seite 04
2.1. Das Prinzip allgemein Seite 04 2.1.1. Turingmaschine als Blackbox Seite 04 2.1.2. Das Turingband Seite 05 2.1.3. Der Lese- bzw. Schreibkopf Seite 05 2.2. Möglicher mechanischer Aufbau Seite 05 2.3. Mathematische Definition Seite 06
3. Beispielanwendungen Seite 07 3.1. Schreibweise für Turingprogramme Seite 07 3.2. Addition unärer Zahlen Seite 10 3.3. Verdopplung einer unären Zahl Seite 13 3.4. Multiplikationsprogramm Seite 16
4. Theorie zur Turingmaschine Seite 21 4.1. Mehrbändige Turingmaschinen Seite 21 4.2. Größe des Bandalphabetes Seite 21 4.3. Berechenbarkeitstheorie Seite 22 4.4. Formale Bedeutung der Turingmaschine Seite 22 4.4.1. Turingmaschine als Generator Seite 22 4.4.2. Turingmaschine als Akzeptor Seite 22
5. Das Busy-Beaver-Problem Seite 23
6. Turingsimulatoren Seite 25 6.1. „Freeware-Turing-Maschine“ Seite 25 6.2. „Facharbeitsturingmaschine“ Seite 25 6.3. „Visual Turing“ Seite 26
7. Schluss und Quellenangabe Seite 27 7.1. Bilder(Quellennachweis) Seite 27 7.2. Sonstige Quellen Seite 28 7.3. Abschlusserklärung Seite 30
- Seite 3 -
1. Einleitung Alan Mathison Turing ist einer der bedeutendsten Mathematiker des 20. Jahrhunderts, berühmt für seine Grundlagenarbeit auf dem Gebiet der Mathematik und Informatik. Zu Lebzeiten genoss er kein hohes Ansehen und beendete sein Leben schließlich durch Selbstmord; erst nach seinem Tod erkannte man das volle Ausmaß seiner Leistungen und die Auswirkungen seiner Arbeiten.
Geboren am 23. Juni 1912 in Paddington (London), als zweites Kind von Julius Mathison and Ethel Sara Turing, ging vom Elternhaus zunächst wenig Interesse an Forschungsarbeiten aus; einzig sein Onkel, der irische Physiker George Johnstone Stoney (1826-1911), könnte einen Einfluss auf ihn gehabt haben. Turings Kindheit verlief in ruhigen Bahnen. Obwohl er zu diesem Zeitpunkt in keiner Weise gefördert wurde, erwachte sein Interesse an der Wissenschaft und äußerte sich schon in einigen simplen Chemieversuchen. Er besuchte die "Sherborne School“, deren Direktor folgenden Satz gesagt haben soll: "If he is to be solely a Scientific Specialist, he is wasting his time at a Public School“ (Der Schuldirektor der Sherborne School über Alan Turing, gefunden auf Hodges, Andrew „Alan Turing: a short biography“, Internetseite http://www.truing.org.uk/bio/part1.html von 1995,
aufgerufen am 30.12.2002) „Wenn er ausschließlich ein Wissenschaftsexperte werden wird, verschwendet er seine Zeit an öffentlichen Schulen“. Damit lag der Schulleiter erstaunlich nahe an der Zukunft.
Abbildung 1
Von 1931 an war Turing Student am „Kings College“ in Cambridge, wo sich ihm mehr denkerische Freiheiten eröffneten. Hier arbeitete er erfolgreich an verschiedenen Projekten und gewann sogar einige Preise, bis er sich entschied, eine andere Richtung zu beschreiten. Die damals aktuelle Diskussion über nicht beweisbare Axiome und besonders das vom deutschen Mathematiker David Hilbert gestellte Entscheidungsproblem vereinnahmten ihn: "Could there exist, at least in principle, a definite method or process by which it could be decided whether any given mathematical assertion was provable?“ (Das „Entscheidungsproblem“, gefunden auf Hodges, Andrew „Alan Turing: a short biography“, Internetseite http://www.truing.org.uk/bio/part2.html von 1995, aufgerufen am 30.12.2002); „Existiert, zumindest im Prinzip, eine sichere Methode oder ein sicheres Verfahren, durch welches man entscheiden könnte, ob ein beliebiger mathematischer Ausdruck beweisbar wäre?“. Diese Fragestellung führte schließlich zur Turingmaschine: Turing analysierte den Denkprozess eines Menschen und versuchte ihn derart zu vereinfachen, dass eine theoretisch physikalisch konstruierbare Maschine den Denkprozess nachvollziehen könnte. Der Erfinder konnte ebenfalls beweisen, dass diese Maschine alles berechnen konnte, was in der Mathematik fortan als „bestimmter Algorithmus“ definiert war. Damit ließ sich nun auch Hilberts Fragestellung sehr schnell mit „nein“ beantworten: eine solche Methode kann nicht existieren. Mit dieser Turingmaschine beschäftigt sich nun die Facharbeit.
Natürlich war dies nicht die letzte Arbeit von Alan Turing: von großer Bedeutung waren noch seine Arbeiten zur Entschlüsselung der deutschen Engima-Verschlüsselungsmaschine und zu den Themen neuronale Netze und künstliche Intelligenz. Später erhielt er unter anderem einen Posten an der Universität von Manchester, wo er für die Elektronikentwicklung der britischen Atombombe eingesetzt wurde. Es folgten einige nicht weniger bedeutsame Werke, auf die jedoch nicht näher eingegangen werden soll. Im weiteren Verlauf wurde Turing vom Glück verlassen. In der damalig vorherrschenden Zeitströmung, bedingt durch den Kalten Krieg und den amerikanischen Einfluss, verlor Turing nicht nur seine Sicherheitsfreigaben der britischen Regierung, sondern sollte sogar für seine homosexuellen Neigungen eingesperrt werden. Dies alles führte vermutlich am 7. Juni 1954 zu seinem durch Zyanid herbeigeführten Selbstmord. Erst Jahre nach seinem Tod erhielten seine Arbeiten die Anerkennung, die ihm ungerechterweise zu Lebzeiten verwehrt blieb. Auch heute, mehr als 60 Jahre nach der Erfindung der Turingmaschine, ist sie noch Lehrstoff der meisten Informatikstudiengänge. Es existiert bis dato kein besseres Modell, um mit der Berechenbarkeitstheorie zu arbeiten. Was ist also eigentlich eine Turingmaschine? 2. Das Prinzip der Turingmaschine Zunächst ist es wichtig, hervorzuheben, dass eine Turingmaschine keinesfalls mit einem heute gebräuchlichen PC vergleichbar ist, sondern vielmehr ein Gedankenmodell bzw. die Konkretisierung eines solchen darstellt. Darüber hinaus muss auch sorgfältig zwischen Hard- und Software unterschieden werden. Ein möglicher mechanischer Aufbau wird in Kapitel 2.2 vorgestellt. Hier zunächst eine allgemeine Einführung in die Turingmaschine. 2.1. Das Prinzip allgemein Eine Turingmaschine besteht stets aus den gleichen elementaren Bestandteilen:
- Ein Steuermechanismus (Kapitel 2.1.1.) - Das Turingband (Kapitel 2.1.2.) - Der Lese- und Schreibkopf (Kapitel 2.1.3.)
2.1.1. Turingmaschine als Blackbox Der Steuermechanismus der Turingmaschine kann auch als Blackbox verstanden werden. Es ist für den Anwender nicht wesentlich, wie die Turingmaschine ihre Berechnungen intern durchführt, er muss nur wissen, welche Eingaben möglich, und welche Ausgaben zu erwarten sind (= Blackboxprinzip). Insofern hat der mechanische innere Aufbau auch keine große Bedeutung. Der Steuermechanismus muss lediglich dazu in der Lage sein, die Eingabe aufzunehmen und entsprechend darauf einen Befehl
- Seite 5 -
für die Ausgabe (in Form des zu schreibenden Symbols und der Bewegungsrichtung des Bandes) abzusetzen. Darüber hinaus muss in dieser Blackbox auch noch festgelegt sein, wie die Turingmaschine auf bestimmte Eingaben reagieren soll (im Normalfall gespeichert in sogenannten Registern). 2.1.2. Das Turingband Das sog. Turingband ist der Speicherort der Turingmaschine. Das Band ist in einzelne Zellen eingeteilt, die jeweils ein Zeichen aufnehmen und speichern können. Für die Berechenbarkeitstheorie relevant ist die Tatsache, dass dieses Band per Definition unendlich lang sein muss (um eine Funktion nicht einfach aufgrund mangelnder Speicherkapazität nicht berechnen zu können). Praktisch lässt sich ein unendlich langes Band natürlich mit keinem bisher bekannten Verfahren simulieren. Das Band lässt sich sowohl nach links als auch nach rechts bewegen, so dass eine entsprechende Lesevorrichtung jedes Bandfeld erfassen bzw. beschreiben kann. 2.1.3. Der Lese- bzw. Schreibkopf Der Lese-/Schreibkopf ist das Datenerfassungs- und Ausgabeelement der Turingmaschine. Er kann ein Zeichen vom Turingband einlesen, es an den Steuerungsmechanismus weiterleiten. Dieser verarbeitet das gesendete Symbol und gibt an den Schreibkopf die Anweisung für das neu in die gleiche Zelle zu schreibende Zeichen. Darüber hinaus erhält er die Anweisung, in welche Richtung das Turingband nun zu bewegen ist. 2.2. Möglicher mechanischer Aufbau Wie bereits erwähnt, ist die Turingmaschine nicht dafür prädestiniert, real nachgebaut zu werden; ihre Leistung und Benutzerfreundlichkeit würden keinen gebräuchlichen Standards entsprechen. Trotzdem ist es sehr viel anschaulicher und nachvollziehbarer, wenn man ein mögliches physisches Abbild betrachtet:
Abbildung 2
- Seite 6 -
Deutlich erkennbar ist das Turingband. Der Doppelpfeil deutet an, dass das Band sowohl nach links als auch nach rechts verschoben werden kann. Der Lese-/Schreibkopf sitzt über dem Band und empfängt/übermittelt die Informationen aus der Blackbox. Diese kann entweder gestartet oder zurückgesetzt werden. Ein Eingriff in eine laufende Berechnung ist also nicht möglich. Softwareseitige Simulationen sind in Kapitel 6 aufgelistet.
2.3. Mathematische Definition Um der Tatsache gerecht zu werden, ein mathematisches Denkmodell darzustellen, muss die Turingmaschine auch mathematisch definiert sein. Zunächst sollten einige grundsätzliche Begrifflichkeiten geklärt werden:
- Der Buchstabe M steht stellvertretend für die Turingmaschine - M hat einen fest definierten Startzustand - S ist das Bandalphabet - x ist die Zeichenkette auf dem Band vor der Berechnung und kann als Einga-
be angesehen werden - y ist die Zeichenkette auf dem Band nach der Berechung und kann als Ausga-
be angesehen werden - Der Lese-/Schreibkopf ist vor der Berechung über das linke äußere Ende von x
zu bewegen - S* stellt die Menge aller Zeichenketten über S dar
Das Bandalphabet Σ kann dabei aus jeder erdenklichen Zusammenstellung von Zeichen bestehen. M muss nicht bei jeder möglichen Zeichenkette x auch anhalten, daher berechnet x korrekterweise nur eine Teilfunktion. Da für eine Turingmaschine ihr mechanischer Aufbau kaum eine Bedeutung spielt, ist sie im wesentlichen dasselbe wie Ihr Programm. Damit steht M also nicht nur für die Turingmaschine, sondern auch für das Turingprogramm. Dieses ist formal eine Menge von Quintupeln der Form
(q, s, q’, s’, d)
Mit folgenden Bedeutungen:
- q ist der aktuelle Zustand - s das vom Lesekopf gelesene Zeichen - q’ der auf den Berechnungsschritt folgende neue einzunehmende Zustand - s’ das an die Stelle von s zu schreibende Zeichen - d die Bewegungsrichtung des Lese-/Schreibkopfes, in die das Band nach dem
Berechnungsschritt zu bewegen ist
Wobei sowohl q und q’, als auch s und s’ nicht unterschiedlich sein müssen. Die Inhalte setzen sich so zusammen:
- Seite 7 -
- die Zustände kommen aus einer endlichen Menge von Zuständen Q, die
zusammen M ergeben - s bzw. s’, also die Zeichen, kommen aus dem Bandalphabet S - d kann nur ein Element aus D = {links, rechts, halt}sein
Diese Definition macht zwei besondere Zustände q ∈ Q nötig: Einen Anfangszustand q0, der immer der erste Zustand zu Beginn einer Berechnung ist, in dem sich M befindet. Der zweite benötigte Zustand ist ein Haltezustand: Falls d = „halt“ erreicht wird, muss M in einen Haltezustand übergehen:
yxf qq → >− ': Dieses spezielle „ q’ “ darf dabei natürlich nie der Anfangszustand q0 sein, da in diesem Fall keine Berechnung erfolgen würde. Die zu dem Zeitpunkt des Erreichens eines Haltezustandes auf dem Band befindliche Zeichenkette wird demnach als Ausgabe y von M angesehen.
3. Beispielanwendungen Um die Funktionsweise einer Tuningmaschine besser verstehen zu können, empfiehlt es sich, einige simple Beispiele näher zu betrachten. Bevor dies geschehen kann, muss aber noch die Notation noch definiert werden. 3.1. Schreibweisen für Turingprogramme Aus der mathematischen Definition in Kapitel 2 ging hervor, dass ein Turingprogramm einer einbändigen Turingmaschine aus einer Menge von Quintupeln der Form
(q, s, q’, s’, d)
besteht. Um bei längeren Programmen den Programminhalt übersichtlich verstehen zu können, soll nun folgende Form für diese Ausdrucksweise (fortan als Registerschreibweise bezeichnet) verwendet werden:
q s s’ d q’ Abbildung 3
Und konkret an einem Beispiel:
1. 1 1 R 1 + 1 R 2
Abbildung 4
Die linke „1“ ist also der aktuelle Zustand, dann wird unterschieden: die obere Zeile tritt in Kraft, wenn eine „1“ auf dem Band gelesen wurde; die untere Zeile, wenn ein „+“ erfasst wurde.
- Seite 8 -
In beiden Fällen soll wieder eine „1“ auf das Band geschrieben und der Lese- bzw. Schreibkopf nach rechts bewegt werden. In der ersten Zeile soll der Zustand 1 beibehalten werden, in der zweiten Zeile soll ein Übergang in den Zustand 2 erfolgen. Für d gibt es in dieser Notationsform drei mögliche Zeichen:
- R steht für eine Bewegung nach rechts - L steht für eine Bewegung nach links - S steht für Stop, also das Anhalten des Vorgangs als Symbol der abgeschlosse - nen Berechnung (Haltezustand)
Der Startzustand in dieser Schreibform ist per Definition immer der Zustand mit der Zahl „1“ Bei einem längeren Bandalphabet entstehen häufig Situationen, bei denen, korrekte Bandbeschriftung zu Beginn vorausgesetzt, viele Zeichen für bestimmte Zustände gar nicht vorkommen können. Als Beispiel eignet sich hier etwa ein Multiplikationsprogramm (siehe 3.4.). Falls das Zeichen, welches das Ende der Zeichenkette und das Startfeld für das Notieren des Ergebnisses repräsentieren soll, schon vor dem Trennzeichen zwischen den beiden zu multiplizierenden unären Zahlen eingelesen wird, kann die Bandbeschriftung nicht korrekt sein. In diesem Fall müsste das Programm derart gestaltet sein, dass es automatisch in den Haltezustand übergeht, ohne aber die Berechung abgeschlossen zu haben. Dies soll verhindern, dass die Turingmaschine in einer Schleife niemals in einen Haltezustand übergeht. Um sich die unnötige Schreibarbeit zu sparen, können diese Zustände, die eine vorzeitige Stopanweisung für den Fall einer inkorrekten Eingabe enthalten, auch einfach weggelassen werden. Die Summe aller einzelnen Register wird auch Übergangsdiagramm genannt.
Vor allem bei längeren Programmen kann es trotz dieser Simplifizierungen passieren, dass die eigentliche Funktion bzw. der Zweck der Berechnung nicht mehr klar ersichtlich sind. Um diesem Problem entgegen zu wirken, existiert auch eine Definition für eine visuelle Darstellung (natürlich sind die Symbole und Formen frei definierbar; um die Arbeit mit dem PC-Programm „Visual Turing“ zu erleichtern, soll hier aber dessen Symbolik verwendet werden. Mehr zu Visual Turing siehe Kapitel 6). Diese Darstellung unterscheidet sich teilweise wesentlich von der Registerschreibweise und lässt sich auch schwerer auf die mathematische Definition anwenden, bietet dafür aber einen besseren Überblick.
- Seite 9 -
Bewege den Lese-/Schreibkopf nach links
Bewege den Lese-/Schreibkopf nach rechts
Schreibe ein „#“ auf das Band
Schreibe ein „e“ auf das Band, analog für jedes andere Zeichen des Bandalphabets
Zeichen für eine Haltezustand (= Breakpoint)
Der Pfeil definiert diesen Befehl als den Startbefehl
Abbildung 5 (Anweisungssymbole)
- Seite 10 -
Bewege den Lese-/Schreibkopf so lange nach links, wie du b einliest (Schleife)
Wenn du ein b einliest, bewege den Kopf nach links
Ohne an eine Bedingung gekoppelt zu sein, soll das Pro- gramm den Lese-/Schreibkopf nach links bewegen
Eine Kombination der beiden Bedingungen: solange ein „b“ gelesen wird, soll der Lese-/Schreibkopf nach links bewegt werden. Wird ein „a“ erfasst, soll der Kopf nach rechts bewegt werden. Abbildung 6 ( Bedingungssymbole)
- Seite 11 - Das Programm „Visual Turing“ bietet darüber hinaus noch eine Reihe weiterer Optionen, auf die aber erst in Kapitel 6 näher eingegangen werden soll, da sie für die folgenden Beispiele keine Relevanz haben. Eine simple Anwendung, die einen einfachen Einstieg bietet, ist die Addition zweier unärer Zahlen: 3.2. Addition zweier unärer Zahlen Werden Zahlen in der unären Darstellungsform notiert, so gilt: Eine beliebige Zahl a ( a ) wird durch a aufeinanderfolgende „1“-en dargestellt, z.B.:
0N∈
111 entspricht der „3“ im Dezimalsystem 11111 entspricht der „5“ (5 Einsen). Der genaue Wortlaut der Aufgabenstellung lautet: Zwei durch ein „+“ (bzw. „#“ für „Visual Turing“, da hier „+“ nicht als Symbol des Bandalphabets verwendet werden kann) getrennte beliebig große unäre Zahlen sollen addiert werden, so dass das Ergebnis am Ende als unäre Zahl auf dem Turingband steht. Der Lese-/Schreibkopf soll/muss dazu vor der Berechnung über dem äußersten linken Ende der Zeichenkette stehen.
Das externe Bandalphabet muss zur Erfüllung dieser Aufgabe nicht mehr als 2 Zeichen beinhalten, einmal die „1“ und einen Platzhalter (z.B. „+“ ). Somit ergibt sich E = {1;+} Da in diesem Beispiel das Bandalphabet nur zwei Zeichen umfasst, existieren auch nur zwei mögliche Eingangszeichen und folglich auch nur zwei zu schreibende mögliche neue Zeichen. Für die Addition zweier unärer Zahlen werden 5 Register benötigt.
1. 1 1 R 1 + 1 R 2 2. 1 1 R 2 + + L 3 3. 1 + L 4 + + S 3 4. 1 1 L 4 + + R 5 5. 1 1 S 5 + + S 5
Zustandstabelle/Übergangsdiagramm:
Abbildung
- Seite 12 -
Per Definition (3.1.) ist der Startzustand der Maschine „1.“ Damit die Anzahl der Schritte noch übersichtlich klein bleibt, sollen die beiden „kleinen“ Zahlen „2“ und „3“ addiert werden, das Turingband hat demnach diesen Inhalt:
L + + 1 1 + 1 1 1 + + + + + + + + + + + +
Abbildung 8
Wobei sich das Band natürlich sowohl nach links als auch nach rechts unendlich fortsetzen kann. Der Schreibkopf befindet sich, wie schon erwähnt, über der linken Eins. Die beiden linken Einser repräsentieren die Zahl „2“, die drei rechten Einsen die Zahl „3“. Zustand 1 besagt: Wenn eine „1“ auf dem Band gefunden wurde, schreibe eine „1“ und bewege den Kopf nach rechts, bleibe im Zustand 1. Dies geschieht zweimal, danach liegt ein Freizeichen auf dem Band vor, d.h.: es wurde ein „+“ gelesen, schreibe eine „1“, bewege den Kopf nach rechts, wechsle in den Zustand 2. Die obere Zeile von Zustand 2 ist der des ersten sehr ähnlich, nur, dass am Ende der zweite und nicht der erste Zustand beibehalten wird. Auf diesem Weg tastet sich die Turingmaschine bis an das Ende der zweiten Zahl. Sobald ein Freizeichen gefunden wurde, tritt die untere Befehlszeile in Kraft: Wenn ein „+“ gelesen wurde, schreibe ein „+“, bewege den Kopf nach links und wechsle in den Zustand 3. Der Lesekopf erkennt nun eine „1“, der 3. Zustand besagt: wenn du eine „1“ gelesen hast, schreibe ein „+“, bewege den Kopf nach links und gehe in den 4. Zustand über. Im 4. Zustand wird nun, solange eine „1“ eingelesen wird, diese auch wieder geschrieben und der Lesekopf bis ans linke Ende der Zeichenkette bewegt. Sobald dies erreicht ist, wird ein „+“ eingelesen. Dies bewirkt das Wenden des Kopfes nach rechts und den Übergang in den letzten, den 5. Zustand. Hier wird nun die äußerste linke „1“ der Zeichenkette gelesen und auch wieder auf das Band geschrieben, die Maschine hält an (S) und der Berechnungszyklus ist beendet. Für die Addition von „2“ und „3“ werden auf diesem Weg immerhin 15 Taktzyklen benötigt, und das, obwohl die Addition hier durch einen simplen Trick geschieht: Das Freizeichen in der Mitte wird entfernt und stattdessen die äußerste rechte „1“ durch ein „+“ ersetzt. Trotzdem wurden die beiden Zahlen korrekt addiert, man erhält am Ende diese Zeichenfolge auf dem Band:
L + + 1 1 1 1 1 + + + + + + + + + + + + +
Abbildung 9
5 mal das Zeichen „1“ entspricht tatsächlich der Zahl 5 ( 2 + 3 = 5 ) Die Aufgabenstellung, umgesetzt mit Hilfe von „Visual Turing“, sieht so aus:
- Seite 13 -
Der Programmcode:
Abbildung 10
Bedingt durch das verwendete Programm, ist das mögliche Bandalphabet nicht mehr frei wählbar. Hier entspricht die Raute ( # ) dem Freizeichen ( + ) und das kleine „a“ der „1“. Das Band sieht hier demnach so aus:
Abbildung 11
Im Gegensatz zum vorangegangenen Modell befindet sich hier der Kopf zu Beginn noch über einem Freizeichen links der Zeichenkette, wird aber durch eine Schleife gleich bis zum ersten „a“ auf dem Band bewegt. 3.3. Verdoppelung einer unären Zahl Ein etwas komplexeres Beispiel ist die Verdoppelung einer beliebig langen unären Zahl. Sowohl die Notation als auch das verwendete Alphabet bleiben dabei gleich, die möglichen Zustände unterscheiden sich natürlich hingegen. Die Definition der Aufgabenstellung lautet: verdopple eine zusammenhängende Zeichenkette, die eine unäre Zahl repräsentiert, so dass am Ende die verdoppelte unäre Zahl auf dem Band steht. Die Verdopplung kann auch als Multiplikation mit Zwei verstanden werden. Für die Verdoppelung werden 7 Zustände benötigt, der Lese- bzw. Schreibkopf setzt wieder am linken äußeren Ende der Zeichenkette an.
- Seite 14 -
Zustandstabelle/Übergangsdiagramm: 1. 1 + R 2
+ + R 7 2. 1 1 R 2 + + R 3 3. 1 1 R 3 + 1 R 4 4. 1 1 S 4 + 1 L 5 5. 1 1 L 5 + + L 6 6. 1 1 L 6 + + R 1 7. 1 1 S 7 + + S 7
Abbildung 12
Verwendet man diese Zustandstabellen, wird die Zahl der nötigen Takte bei größeren Zahlen recht schnell unüberschaubar groß. Daher wird hier nur das Beispiel mit der Zahl 2 „durchgespielt“, aber auch dieser Vorgang benötigt schon 22 Takte. Das Band sieht zu Beginn also so aus:
L + + 1 1 + + + + + + + + + + + + + + + +
Abbildung 13
Der Lesekopf befindet sich über der linken der beiden Einsen. Es wird der erste Zustand aufgerufen: Wenn eine Eins gelesen wurde, schreibe ein „+“, bewege den Kopf nach rechts und gehe in den Zustand 2 über. Hier wird erneut eine „1“ gelesen, im 2. Zustand auch wieder eine „1“ aufs Band geschrieben, der Kopf erneut nach rechts bewegt, der Zustand beibehalten. Jetzt findet der Lesekopf ein „+“ auf dem Band, es wird auch wieder ein „+“ auf das Band geschrieben, der Kopf bewegt sich abermals nach rechts und die Turingmaschine geht in den 3. Zustand über. Dieser veranlasst die Turingmaschine, da ein „+“ gelesen wurde, eine „1“ aufs Band zu schreiben, den Lesekopf nach rechts zu bewegen und in den 4. Zustand zu wechseln.
- Seite 15 -
Das Band sieht dabei so aus:
L + + 1 + 1 + + + + + + + + + + + + + + +
Abbildung 14
Hier wird nun ein „+“ erkannt, der 4. Zustand besagt: Wenn ein „+“ gelesen wurde, schreibe eine „1“, bewege den Kopf nach links und gehe in den 5. Zustand über. Nun erkennt die Maschine eine „1“, schreibt diese auch wieder auf das Band und bewegt den Kopf nach links, unter Beibehaltung des aktuellen 5. Zustands. Nun wird ein „+“ eingelesen, dieses wird auch wieder aufs Band geschrieben, der Kopf nach links bewegt, aber dafür der 6. Zustand geladen. Das Band schaut im Moment so aus:
L + + 1 + 1 1 + + + + + + + + + + + + + +
Abbildung 15
Zunächst bleibt die Turingmaschine in diesem Zustand, da eine „1“ auf dem Band gefunden und beibehalten wurde; der Lesekopf wird nach links bewegt. Jetzt wird ein „+“ gelesen, dieses wird erneut auf das Band geschrieben, der Kopf wird jedoch zurück nach rechts bewegt und die Maschine geht wieder in den 1. Zustand über. Von diesem Zeitpunkt an wiederholt sich der Vorgang für jede weitere „1“ der Ursprungszahl, in diesem Beispiel also noch ein weiteres Mal. Sobald die Maschine wieder den 6. Zustand erreicht hat, sieht das Band so aus:
L + + 1 1 1 1 + + + + + + + + + + + + + +
Abbildung 16
Die Maschine geht gemäß der Definition des 6. Zustands wieder in den ersten über. Im Gegensatz zu den vorangegangen Durchgängen findet die Maschine aber keine „1“ mehr auf dem Band vor, daher wird nun das „+“ wieder auf das Band geschrieben, die Maschine wechselt jedoch in den 7. Zustand. Dieser enthält nun den Befehl, stehen zu bleiben, die Berechnung ist beendet und der Lesekopf steht wieder über der äußersten linken „1“ der Zeichenkette. Bei diesem Beispiel wird also jede „1“ der Ursprungszahl eingelesen, durch ein Freizeichen ersetzt und am rechten Ende der gedachten Zeichenkette wieder zweimal auf das Band geschrieben. Auch diese Anwendung lässt sich visualisieren und erleichtert damit das Verständnis:
- Seite 16 -
Das Programm:
Abbildung 17
3.4. Multiplikationsprogramm Eine sogar real sinnvolle Anwendung würde ein Multiplikationsprogramm darstellen. Um die Anzahl der benötigten Register klein und auch die Übersichtlichkeit der Anwendung zu erhalten , wird für diese Anwendung das Bandalphabet ein wenig erweitert.
E = {+;a;b;x;e} Mit folgenden Bedeutungen: + bleibt weiterhin das Freizeichen a stellt ebenso weiterhin einen Teil einer unären Zahl dar b fungiert als Platzhalter und soll nach der Berechnung nicht mehr auf dem Band stehen x trennt die beiden zu multiplizierenden unären Zahlen e entspricht dem „=“ (e wie Ergebnis) Die genau Formulierung der Aufgabenstellung: Multipliziere 2 unäre Zahlen, die durch ein x getrennt auf dem Turingband (ohne Unterbrechungen der Zeichenkette) stehen. Schreibe das Ergebnis rechts der Zeichenkette hinter ein „e“ (welches das rechte Ende der Zeichenkette markiert) auf das Band und bewege den Lesekopf anschließend zurück zur Ursprungsposition links der Zeichenkette.
- Seite 17 -
Zunächst die Zustandstabellen/das Übergangsdiagramm:
1. + + R 1 a b R 2
2. + + S 2 a a R 2 e e S 2 x x R 3
3. e e S 3 a b R 4
4. a a R 4 e e R 5
5. + a L 6 a a R 5
6. a a L 6 e e L 7
7. a a L 7 b b R 8
8. a b R 4 e e L 9
9. b a L 9 x x L 10
10. a a L 10 b b R 11
11. a b R 2 b b R 11 x x L 12
12. + + S 12 b a L 12
Abbildung 18
Hier wurde zum erstenmal von der unter 3.1. erwähnten Simplifizierung Gebrauch gemacht und einige nur durch „nicht korrekte Eingabe“ mögliche Anweisungen weggelassen.
- Seite 18 -
Das Band vor der Berechnung (am Beispiel 2 x 3):
L + + a a x a a a e + + + + + + + + + + +
Abbildung 19
Der Lesekopf ist am linken äußeren Ende der Zeichenkette. Da der Lesekopf sofort ein "a" einliest, muss er nicht erst nach rechts bis zum Beginn der Zeichenkette bewegt werden. Die Turingmaschine schreib also an die Stelle des ersten „a“s ein „b“ und geht gleich in den 2. Zustand über. Die Möglichkeit, ein „+“ einzulesen, darf eigentlich nicht bestehen, da ansonsten die Zeichenkette nicht, wie in der Aufgabenstellung vereinbart, auf dem Band stünde, gleiches gilt für das „e“. Der Kopf wird nun solange nach rechts bewegt, wie das Zeichen „a“ eingelesen wird. Sobald die Turingmaschine auf das „x“ (als Multiplikationszeichen) stößt, wird dieses auf dem Band belassen, der Lese- bzw. Schreibkopf nach rechts bewegt und zum 3. Zustand gewechselt. Falls hier gleich ein „e“ eingelesen wird, hält die Turingmaschine natürlich an, da die Multiplikation mit „0“ (es existieren hinter dem „x“ keine zu einer unären Zahl gehörenden Zeichen mehr auf dem Band) kein Ergebnis liefert. Im Normalfall wird nun ein „a“ eingelesen, durch ein „b“ ersetzt, der Lese-/Schreibkopf nach rechts bewegt und die Maschine geht in den 4. Zustand über. Dieser besagt: solange ein „a“ eingelesen wird, schreibe ein „a“ auf das Band, bewege den Kopf nach rechts und bleibe in diesem Zustand. Sobald das „e“ gelesen wird, behalte es so auf dem Band, bewege den Kopf noch ein Feld nach rechts und gehe in den 5. Zustand über. Das Band hat nun folgende Beschriftung:
L + + b a x b a A e + + + + + + + + + + +
Abbildung 10
Im 5. Zustand soll nun für den Fall, dass ein „a“ gelesen wird, der Kopf solange nach rechts bewegt werden (und der Zustand nicht gewechselt werden), bis ein Freizeichen in Form eines „+“ gelesen wird. Dieses wird ersetzt durch ein „a“ und der Kopf ändert seine Richtung nach links. Der anzunehmende neue Zustand ist 6. Solange ein „a“ gelesen wird, bewegt sich der Kopf nach links; stößt die Maschine auf das „e“, muss der Kopf um noch ein weiteres Feld nach links bewegt werden und der 7. Zustand geladen werden. Falls ein „a“ gelesen wird, soll dieses auch wieder auf das Band geschrieben werden und der Kopf nach links bewegt werden. Stößt der Lesekopf hingegen auf ein „b“, soll der Kopf, ohne das „b“ durch ein anderes Zeichen zu ersetzen, sich nach rechts bewegen und die Maschine in den 8. Zustand übergehen. Dieser nimmt nun eine Unterscheidung vor: wird ein „e“ gelesen, bedeutet dies, dass auf dem Band rechts des Multiplikationszeichens und noch vor dem Zeichen „e“ nur noch das Zeichen „b“ steht, die Zahl also schon komplett abgearbeitet wurde. Ist dies nicht der Fall, findet die Turingmaschine ein „a“ vor, wird dieses durch ein „b“ ersetzt und die Maschine geht zurück in den 4. Zustand, der Ablauf wird analog vorangegangener Schilderung also für jedes „a“ der zweiten unären Zahl wiederholt.
- Seite 19 -
Sobald nur noch „b's" rechts des Multiplikationszeichens auf dem Band stehen, schaut es so aus:
L + + b a x b b b e a a a + + + + + + + +
Abbildung 21
Die durch „b“ substituierten „a“s müssen wieder zurückgewandelt werden, dafür ist der 9. Zustand zuständig. Solange ein „b“ gelesen wird, ist dieses durch „a“ zu ersetzen. Sobald das „x“ auftaucht, geht die Maschine in den 10. Zustand über, der Kopf wird weiterhin nach links bewegt. Dieser Zustand besagt: solange ein „a“ gelesen wird, schreibe ein „a“ auf das Band, bewege den Kopf nach links und bleibe in diesem Register. Sobald ein „b“ gelesen wird, schreibe das „b“ wieder auf das Band und wechsle in den 11. Zustand und bewege vorher den Kopf nach rechts. Das nun folgende Schema folgt dem Muster der zweiten unären Zahl in Bezug auf die Prüfung der Vollständigkeit der Substitution der „a“s durch „b's“. Wird sofort nach der Rechts-Bewegung nur noch das „x“-Zeichen gelesen, heißt das, es gibt keine „a“s mehr auf der linken Seite des Multiplikationszeichens und folglich wurde die ganze linke Zahl schon abgearbeitet. Ist dies nicht der Fall, wird das gelesene „a“ durch ein „b“ ersetzt und die Maschine geht zurück in den 2. Zustand. Dieser Prozess wird also für alle „a“s der ersten unären Zahl wiederholt. Sobald die erste Zahl komplett ersetzt wurde, sieht das Band so aus:
L + + b b x a a a e a a a a a a + + + + +
Abbildung 22
Nun muss diese Substitution nur noch rückgängig gemacht werden. Dies geschieht im 12. Zustand, in dem, solange ein „b“ gelesen wird, dieses durch ein „a“ ersetzt wird und der Kopf sich weiter nach links bewegt. Sobald ein Freizeichen ( + ) erscheint, geht die Maschine in einen Haltezustand über, die Berechnung ist abgeschlossen und alle Substitutionen sind rückgängig gemacht worden:
L + + a a x a a b e a a a a a a + + + + +
Abbildung 23
- Seite 20 -
Das Programm in visueller Darstellung:
Abbildung 24
Besonders auffallend sind die 3 Breakpoints; die oberen beiden dienen zur Vermeidung von Programmfehlern durch 0-Eingabe, der untere Breakpoint stellt den normalen Endpunkt der Berechnung dar.
Das Programm schreibt also für jedes „a“ der linken Zahl zunächst ein „b“ als Platzhalter, geht dann zur rechten Zahl, liest dort alle „a“s ein (ersetzt die dabei kurzzeitig durch „b“s), schreibt die ersetzten „a“s rechts des „e“s wieder auf das Band, verwandelt die substituierten „b“s der rechten Zahl wieder in „a“s und geht zurück zur linken Zahl. Der Vorgang wird für jedes „a“ der linken Seite wiederholt und am Ende werden die „b“s dieser Zahl auch wieder zurück in „a“s verwandelt. Der Lesekopf ist wieder links der Zeichenkette und das Ergebnis rechts vom „e“-Zeichen. Das Band am Anfang:
Abbildung 25
Das Band am Ende:
Abbildung 26
Man kann leicht erkennen, dass der Aufwand schon bedeutend größer ist als noch bei der einfachen Addition. Je komplexer die Aufgabenstellungen werden, desto umfangreicher werden auch die Programme.
- Seite 21 - Um die Grenzen solcher Programme ausfindig machen zu können, und deren Bedeutung für die Mathematik- und Computerwissenschaft zu verstehen, bedarf es genauerer Überlegungen. Mehr dazu im nächsten Kapitel, in welchem die Berechenbarkeitstheorie näher vorgestellt wird.
4. Theorie zur Turingmaschine 4.1. Mehrbändige Turingmaschinen Eine der interessantesten Eigenschaften von Turingmaschinen ist ihre hohe Flexibilität. So sind tiefgreifende Veränderungen möglich, ohne ihre Berechnungsfähigkeit nachhaltig zu beeinflussen. Eine Möglichkeit der Veränderung ist die Variierung der Anzahl der Turingbänder. Es existieren auch Modelle von Maschinen mit mehr als einem Band (und entsprechend auch mit mehr als einem Lese-/Schreibkopf). Der Vorteil solcher Maschinen lässt sich durch das Kapitel 3.4. gut demonstrieren. Während für die Multiplikation das Symbol „b“ als Platzhalter zur Kennzeichnung bereits eingelesener Teile der unären Zahl diente, könnte man mit einer zweibändigen Maschine das zweite Band als temporären Speicherort verwenden und dabei vermutlich auch einige Registerzustände einsparen. Die Darstellung einer mehrbändigen Turingmaschine weicht dabei natürlich von der Einbändigen ab. Während in Kapitel 3.1. noch Quintupeln der Form (q, s, q’, s’, d) verwendet wurden, muss eine mehrbändige Turingmaschine auch mehr Angaben erhalten. Dies geschieht in folgender Form:
(q, s1, s2..., sn, q’, s1’, s2’..., sn’, d1, d2...dn) Lediglich q und q’ bleiben von der Veränderung unberührt, alle anderen Werte müssen n-mal angegeben werden (wobei n die Anzahl der Bänder repräsentiert). Daher besteht eine Turingmaschine in der allgemein Form aus (2 + 3*n)-Tupeln. Die Bedeutung der einzelnen Symbole hat sich nicht verändert: q, der aktuelle Zustand besagt: wenn s1, s2..., sn auf den entsprechenden Bändern gelesen wurden, schreibe s1’, s2’..., sn’ auf die passenden Bänder, bewege deren Leseköpfe nach d1, d2...dn und gehe in den Zustand q’ über.
4.2. Größe des Bandalphabetes Neben der Bänderanzahl kann man auch die Größe des Bandalphabetes verändern. In Kapitel 3.4. hatte die Vergrößerung des Bandalphabetes nur kosmetischen Charakter und half, die Anzahl der benötigten Übergangszustände in einem erträglichen Rahmen zu halten. Es existieren bereits Beweise, dass eine Turingmaschine mit einem Alphabet von nur 2 Zeichen ebenfalls alles berechnen kann, was eine Maschine mit einem beliebig großen Alphabet berechnen könnte. Natürlich besteht dabei aber auch ein Zusammenhang zwischen der Größe der Übergangsdiagramme und der entsprechenden Alphabete. Sei Q eine Turingmaschine mit Σq = {x1, x2...xn} und n Zuständen und P eine Turingmaschine mit Σp >> Σq und m Zuständen, so kann für die gleiche Aufgabenstellung (entsprechend etwas komplexer) angenommen werden, dass m << n gilt .
- Seite 22 -
4.3. Berechenbarkeitstheorie Der eigentliche Grund für die Entwicklung der Turingmaschine war die Hoffnung, einen Apparat zu finden, der auf möglichst einfache Weise entscheiden konnte, ob ein beliebiger mathematischer Ausdruck berechenbar wäre oder nicht. Die Definition dieser Berechenbarkeit:
eine Funktion f: Nk N heißt turingberechenbar, falls es eine (deterministische) Turingmaschine M gib, so dass für alle n1, .......,nk, m ∈ N gilt: f(n1, .......,nk) = m genau dann, wenn: z0bin(n1)#bin(n2)#...#bin(nk) ... zebin(m) ... wobei ze ∈ E (Nachweis/Definition entnommen aus Schöning, Uwe: Theoretische Informatik kurzgefasst, Ulm, Verlag Spektrum (akademischer Verlag), 1995 Seite 89,90,91) bin(n) ist dabei die Binärdarstellung der Zahl n ∈ N ohne führende Null. Äquivalent dazu kann n auch in unärer Form dargestellt werden. Ebenfalls deckt diese Definition alle Wörter ab, da sich jeder Buchstabe problemlos in eine Ganzzahl konvertieren lässt (z.B. durch die ASCII-Kodierung, die jeden Buchstaben per Binärsystem darstellen kann) und auch eine eindeutige Rückwandlung möglich ist. Es gilt dadurch folgende Definition (mit all ihren Folgen): „Alles was berechenbar ist, ist durch eine Turingmaschine berechenbar!“
Und auch der Kehrsatz wurde akzeptiert:
„Alles was nicht durch eine Turingmaschine berechnet werden kann, ist überhaupt nicht berechenbar!“
Der letzte Satz wird für das 5. Kapitel von Bedeutung sein.
4.4. Formale Bedeutung der Turingmaschine Dieses Kapitel soll nur ein kurzer Ausblick auf die weitere Bedeutung der Turingmaschine sein und wird sich auch nicht genauer mit Beweisen oder Beispielen beschäftigen. 4.4.1. Turingmaschine als Generator Eine Turingmaschine kann eine formale Sprache aufzählen. Dazu werden alle Bestandteile der Sprache nacheinander auf das Band geschrieben und durch ein spezielles Symbol getrennt. Daher sind Turingmaschinen auch Generatoren für formale Sprachen. Unendliche Sprachen werden auch unendliche lange auf das unendlich lange Turingband geschrieben. Trotzdem kann für ein bestimmtes Zeichen ein fester Zeitpunkt angegeben werden, an dem es auf dem Band geschrieben steht. 4.4.2. Turingmaschine als Akzeptor Eine Turingmaschine kann unterscheiden, ob ein auf das Band geschriebenes Wort zu einer formalen Sprache gehört. Die Unterscheidung erfolgt über die Auswertung des
- Seite 23 -
Verhaltens der Turingmaschine: nimmt diese einen Haltezustand ein, gilt das Wort als akzeptiert.
5. Das „Busy-Beaver-Problem“ Eine interessante Aufgabenstellung, die auch heute noch aktuell ist und dabei selbst modernste Rechenzentren auslastet, wenn nicht sogar überfordert, ist das sog. Busy-Beaver-Problem. Wie lautet diese Aufgabe, die mehr als 60 Jahre nach der Einführung der Turingmaschine den Mathematikern noch Kopfzerbrechen bereiten kann? Gegeben ist ein leeres Turingband (auf dem also nur das Zeichen „0“ steht), ein aus 2 Zeichen bestehendes Bandalphabet Σ = {0; 1} und eine Turingmaschine mit n = Anzahl der möglichen Zustände. Gesucht sind die Zustände, die bei einem vorgegeben n die größtmögliche Anzahl von „1“en auf das Band schreiben kann, bevor die Turingmaschine in einen Haltezustand übergeht. Diese Zahl (Σ(n)) muss existieren, da die Anzahl der Turingmaschinen auch endlich ist und somit Σ(n) nicht unendlich groß werden kann. Formuliert wurde die Aufgabe 1962 von Tibor Rado. Die eigentliche Schwierigkeit des Busy-Beaver besteht darin, dass die Busy-Beaver-Funktion schneller ansteigt als jede berechenbare Funktion. Beweis: Die Busy-Beaver-Maschine Bn besitzt n Zustände und gibt Σ(n) „1“en aus. Ihr gegenüber steht eine Turingmaschine, die aus wiederum aus drei einzelnen Turingmaschinen zusammen gesetzt sein soll. Ihre Ein- und Ausgabe erfolgt binär. Sie besteht im einzelnen aus folgenden Bestandteilen:
- Die mit „C“ bezeichnete Turingmaschine wandelt eine binäre in eine unäre
Zahl um. Dazu benötigt sie eine feste Anzahl r von Zuständen.
Die zentrale Turingmaschine:
- Die „B“ genannte Turingmaschine, welche die Busy-Beaver-Funktion berechnet. Liest B die Zahl n ein, gibt sie Σ(n) wieder aus. Dazu benötigt sie ebenfalls eine feste Anzahl von q Zuständen
Und schließlich die zweite „Hilfsmaschine“:
- Die mit dem Buchstaben „A“ bezeichnete Turingmaschine, welche n auf ein
leeres Band in Binärform schreiben kann. Sie benötigt nur log(n) Zustände.
Zusammen ergeben die drei Einzelmaschinen die Busy-Beaver-Maschine ABC. Nun kann man ABC mit Bn vergleichen: Unter der Bedingung n ∈ N und n > log(n) + q + r kann ABC ebenso viele „1“en auf das Turingband schreiben wie Bn, benötigt dazu aber offensichtlich weniger Zustande. Die Teilmaschinen A und C lassen sich leicht konstruieren und da es außer Frage steht, dass es sie wirklich gibt, kann B mit q Zuständen nicht existieren. Daher ist Σ(n) keine berechenbare Funktion.
- Seite 24 - Da die Aufgabenstellung mittlerweile ein regelrechtes „Wettrennen“ um die besten Übergangsdiagramme geworden ist, verwendet man allgemein eine gemeinsame Notationsform Diese weicht natürlich nicht von der Definition in Kapitel 2 ab, liest sich aber ein wenig anders als die Schreibweise für die Beispiele im 3. Kapitel, da hier das Bandalphabet nur auf 2 Zeichen beschränkt wurde. Als Beispiel für einen Busy-Beaver soll der 5er-Biber dienen:
A ist der Anfangszustand. Wird eine „0“ auf dem Band gelesen, schreibt die Turingmaschine eine „1“ auf das Band, bewegt den Kopf nach links und geht in den Zustand B über. Die Schreibweise ähneltähnelt der Notationsform aus dem Kapitel 3. Die folgenden Tabelle über den aktuellen Wissenstand der Berechnungen stammt vom Juni 2002:
n Σ(n) S(n) Quelle 1 1 1 Lin and Rado 2 4 6 Lin and Rado 3 6 21 Lin and Rado 4 13 107 Brady 5 >= 4098 >= 47,176,870 Marxen and Buntrock 6 > 1.29*10865 > 3*101730 Marxen and Buntrock
Abbildung 28
S(n) ist dabei die Anzahl der benötigten Schritte, bis Σ(n) „1“en auf dem Band stehen. Zwei Besonderheiten fallen an der Tabelle auf: Zum einen die enormen Sprünge bei n = 5 und n = 6 und zum anderen, dass für n ∈ {1; 2; 3; 4} nachweislich das Gleichheitszeichen verwendet werden kann (es ist bewiesen, dass für diese Anzahl von n Zuständen nicht ein größeres Σ(n) existieren kann), für n = 5 jedoch nur ein „>=“ – Zeichen angebracht ist und für n = 6 schließlich nur noch ein „>“-Zeichen Berechtigung hat. Natürlich fällt ein Nachweis bei derart großen Zahlen sehr schwer, obgleich vermutet wird, bis n = 6 sei Σ(n) noch nachweisbar. Dass es wenig Sinn macht, auf einem handelsüblichen Heim-PC derartige Berechnungen durchzuführen, wird sehr schnell am Beispiel von n = 6 klar: Nimmt man an, der verwendete PC würde mit einer Taktrate von 1,8 GHz betrieben und das Simulationsprogramm würde für die Aufrechterhaltung des Systems nur etwa 1% der Leistung benötigen, stünden ca. 1,782 * 1012 Berechungsschritte/Sekunde zur Verfügung. Wollte man damit die 3*101730 nötigen Schritte durchführen, benötigte man 1,74 * 101718 Sekunden (5,5 * 101711 Jahre). Ein unvorstellbar großer Wert! Selbst modernste Hochleistungsrechenzentren könnten die Dauer nur unwesentlich verkürzen.
- Seite 25 -
Daher werden diese Berechnungen auch nur über Abschätzungen und Ungleichungen näherungsweise berechnet. Σ(n) steigt also schneller an, als jede berechenbare Funktion f(n) anwachsen könnte ( Σ(n) ist nicht deterministisch berechenbar). So gilt für ein entsprechend großes n stets:
I. Σ(n) >= f(n) ( z.B. Σ(5) >= e5 ) Ein wesentlich bedeutenderes Ergebnis erhält man aber durch diese Überlegung: II. f(Σ(n)) < Σ(n+1) für unendlich viele Werte von n m
Für die f-Funktion kann man z.B. verwenden: f(m) = mm Dies funktioniert für jede feste Anzahl an Potenzierungen (in diesem Beispiel 2). Das ändert jedoch nichts an der Gleichung I. Damit erhält man diese Formel: Σ(n)
III. Σ(n+1) > Σ(n) Σ(n) für unendliche viele Werte von n
6. Turingsimulatoren
Eine Vielzahl an Programmen, geschrieben in den unterschiedlichsten Programmiersprachen, beschäftigen sich mit dem Thema „Turingmaschine“ und versuchen, ein möglichst komfortables Arbeiten mit diesem Gedankenmodell zur Verfügung zu stellen. Eine eher simple Anwendung ist die „Freeware-Turing-Maschine“. 6.1. „Freeware-Turing-Maschine“ Dieses Programm eignet sich nur bedingt für die Simulation von Programmabläufen, da zum einen das Bandalphabet auf 2 Zeichen beschränkt ist (und sich auch nicht ereitern lässt) und zum anderen die Anzahl der möglichen Register auf 100 limitiert ist. Dies mag zwar für simple Aufgabenstellungen genügen, kann jedoch zusammen mit dem extrem beschränkten Alphabet schnell zum Engpass werden. Hersteller & Informationen:
Copyright (c) 2002 fb-software, Osterode. Alle Rechte vorbehalten.
6.2. „Facharbeitsturingmaschine“ Um den Mängeln des oben genannten Programms entgegenzuwirken, entstand die sog. Facharbeitsturingmaschine. Das Programm ist in der Interpretersprache „Hypertext Preprocessor“ (= „PHP“; ab Version 4.x bis Version 4.2 und ab hier nur noch mit der Einstellung register_globals = „on“) geschrieben und ist unter allen Betriebssystemen lauffähig, für die es einen entsprechenden Interpreter gibt (was wohl mehrheitlich bei allen für Desktop oder Servereinsatz gebräuchlichen Systemen gegeben sein sollte).
- Seite 26 -
Eine funktionierende Demoversion ist unter http://schorschium.net/turing/ abrufbar. Die Anwendung erlaubt es dem Benutzer, beliebige Alphabete (aufgrund der ASCII-Definition aber nur Zeichen aus einem vorgegebenen Array) zu erstellen, Bänder damit zu beschriften und entsprechende Übergangsdiagramme zu programmieren. Das Kernstück der Anwendung, der Simulator an sich, schreibt die Bandausgabe Schritt für Schritt untereinander. Aufgrund der Unzulänglichkeit der Hypertextmarkuplanguage ist das Symbol für den Lesekopf nicht über dem Feld, sondern jeweils links davon, rot unterlegt. Das Programm umfasst dabei knapp 1000 Zeilen Code (der eigentliche Simulator kommt allerdings nur auf 89 Zeilen), und lief im Rahmen dieser Facharbeit für alle in Kapitel 3. genannten Beispiele ohne Probleme (z.B. die Addition unärer Zahlen):
Hersteller & Informationen: Copyright (c) 2002 Stefan Schorsch, Nürnberg. Alle Rechte vorbehalten.
Das GUI ist dabei noch sehr einfach gehalten und nur funktional.
Abbildung 11
6.3. „Visual-Turing“ Eine Besonderheit unter den Simulationsprogrammen stellt „Visual-Turing“ dar. Anders als bei den meisten Simulatoren arbeitet die Anwendung nicht mit Registertabellen, sondern erlaubt es dem Benutzer, seine Programme regelrecht zu zeichnen, angelehnt an die IDEs von namenhaften Herstellern wie Microsoft und deren Visual-Studios (z.B. für C++, Java, uvm). Eine kurze Einführung in die Symbolik befindet sich in Kapitel 3.1. Mit Hilfe der Arbeit von Christian Cheran können auch komplexe Anwendungen sehr schnell umgesetzt werden, Korrektur- und Wartungsarbeiten am Quellcode sind leicht durchzuführen. Darüber hinaus beherrscht das Programm noch eine Reihe weiterer Optionen, Einstellungsmöglichkeiten und Arbeitstechniken, die allerdings über den Rahmen der Facharbeit weit hinausgehen. Eine gute Dokumentation für diese Features ist ebenfalls enthalten. Hersteller & Informationen: Copyright (c) 1997 Christian Cheran Email: [email protected] Homepage: http://apolo.cs.pub.ro/~cheran/vturing/
- Seite 27 - Das Programm ist kostenlos erhältlich und darf bei kostenloser Weitergabe auch publiziert werden. Leider scheint die Homepage des Programmierers nicht mehr erreichbar zu sein.
Entnommen von Internetseite „Turing Maschine-Simulator“ Systems Architecture and Software Group Department of Information Technology University of Zurich http://www.ifi.unizh.ch/groups/richter/achatz/turing.jpg vom 10.4.1996, besucht am 30.12.2002
2. Modell einer Turingmaschine Entnommen aus Dewdney, A:K:: Der Turing Omnibus, The University of Western Ontario Kanada, Verlag Springer, 1995 Seite 222
3. Modell eines Übergangsdiagramms Erstellt mit „Microsoft Excel 2000“, 2002
4. Modell eines Übergangsdiagramms Erstellt mit „Microsoft Excel 2000“, 2002
5. Liste von Symbolen für die Programmierung in „Visual Turing“ Erstellt als Screenshot aus „Visual Turing“ (siehe 6.3.), 2002
6. Liste von Symbolen für die Programmierung in „Visual Turing“ Erstellt als Screenshot aus „Visual Turing“ (siehe 6.3.), 2002
7. Beispielprogramm 1 Erstellt mit „Microsoft Excel 2000“, 2002
8. Band zu Beispielprogramm 1 Erstellt mit „Microsoft Excel 2000“, 2002
9. Band zu Beispielprogramm 1 Erstellt mit „Microsoft Excel 2000“, 2002.
10. Beispielprogramm 1 in „Visual Turing“ Erstellt als Screenshot aus „Visual Turing“ (siehe 6.3.), 2002
11. Turingband zu Beispielprogramm 1 aus „Visual Turing“ Erstellt als Screenshot aus „Visual Turing“ (siehe 6.3.), 2002
12. Beispielprogramm 2 Erstellt mit „Microsoft Excel 2000“, 2002
13. Turingband zu Beispielprogramm 2 Erstellt mit „Microsoft Excel 2000“, 2002
14. Turingband zu Beispielprogramm 2 Erstellt mit „Microsoft Excel 2000“, 2002
15. Turingband zu Beispielprogramm 2 Erstellt mit „Microsoft Excel 2000“, 2002
16. Turingband zu Beispielprogramm 2 Erstellt mit „Microsoft Excel 2000“, 2002
17. Beispielprogramm 2 in „Visual Turing“ Erstellt als Screenshot aus „Visual Turing“ (siehe 6.3.), 2002
Hodges, Andrew „Alan Turing: a short biography“, Internetseiten http://www.truing.org.uk/bio/part1.html http://www.truing.org.uk/bio/part2.html http://www.truing.org.uk/bio/part3.html http://www.truing.org.uk/bio/part4.html http://www.truing.org.uk/bio/part5.html http://www.truing.org.uk/bio/part6.html http://www.truing.org.uk/bio/part7.html von 1995, aufgerufen am 30.12.2002
Kapitel 2: Dewdney, A:K:: Der Turing Omnibus, The University of Western Ontario Kanada, Verlag Springer, 1995
Dewdney, A:K:: Der Turing Omnibus, The University of Western Ontario Kanada, Verlag Springer, 1995, diverse Kapitel
Marxen, Heiner: „Attacking the Busy-Beaver 5“, Internetseite
http://www.drb.insel.de/~heiner/BB/mabo90.html http://www.drb.insel.de/~heiner/BB/index.html vom 24.6.2002, aufgerufen am 30.12.2002 Michael Bertol, Holger Petersen und Horst Prote „fleißige Biber“, Internetseite http://www.informatik.uni-stuttgart.de/ifi/ti/projects/beaver/bbb.html vom 12.8.1996, aufgerufen am 30.12.2002
7.3. Abschlusserklärung: „Ich erkläre hiermit, dass ich die vorliegende Facharbeit ohne fremde Hilfe angefertigt und nur die im Literaturverzeichnis angeführten Quellen und Hilfsmittel benutzt habe.“ Nürnberg, den 01.01.2003 ............................................................ Stefan Thomas Schorsch
