Inhaltsverzeichnis

1  Die Turingmaschine und Ihre Bedeutung für die Informatik  1

1.1  Das Problem der algorithmischen Entscheidbarkeit.  1

1.1.1  Definition des Begriffs Algorithmus.  1

1.1.2  Der Algorithmus in der Informatik.  1

1.2  Turings Idee der Turingmaschine als Lösungsansatz.  2

1.3  Funktionsweise der universellen Turingmaschine.  3

1.3.1  Definition der Turingmaschine.  3

1.3.2  Schreibweisen der Konfigurationen  4

1.3.3  Die universelle Turingmaschine.  5

1.4  Die Turingmaschine als präziser Algorithmusbegriff  5

1.5  Interessante Turingmaschinen.  6

1.5.1  Einfache Mathematikmaschinen.  7

1.5.2  Sortieralgorithmen  8

1.5.3  Unterprogramme.  9

2  Objektorientierte Implementierungsansätze für eine Turingmaschine in Java  10

2.1  Vorüberlegungen.  10

2.2  Überlegungen zu benötigten Klassen  10

2.2.1  TuringMaschine.  11

2.2.2  TuringBand  11

2.2.3  Alphabet  11

2.2.4  Zustand.  11

2.2.5  Konfiguration.  11

2.3  Klassendiagramm.  11

2.4  Benutzerinteraktion und Anzeigefunktionalität  13

3  Technische Realisierung.  15

3.1  Umsetzung des Klassendiagramms  15

3.1.1  Turingmaschine  15

3.1.2  Benutzerinteraktion  15

3.2  Umsetzung der benötigten Funktionen.  16

3.2.1  TuringMaschine.  16

3.2.2  Subklassen von Turingmaschine  16

3.2.3  MainFrame.  18

3.2.4  TuringBandPanel.  18

3.3  Das fertige Programm.  19

3.3.1  Bedienung  19

3.3.2  Fazit  19

  Literaturverzeichnis  20

  Anlagenverzeichnis  21

  Ehrenwörtliche Erklärung.  25

ii

  Abbildungsverzeichnis  

  Abbildung 1 Klassendiagramm Kernfunktionalität  

  Abbildung 2 Kollaborationsdiagramm nextStep()  

  Abbildung 3 Sortiermaschine bei der Arbeit  

iii

1 Die Turingmaschine und Ihre Bedeutung für die

Informatik

1.1 Das Problem der algorithmischen Entscheidbarkeit.

1.1.1 Definition des Begriffs Algorithmus

Um das Problem der algorithmischen Entscheidbarkeit zu diskutieren, benötigt man

zuerst eine saubere Definition des Begriffs Algorithmus. Obwohl man in der

Mathematik schon seit langem Algorithmen verwendet, einer der ältesten bekannten ist

zum Beispiel das Sieb des Erasthotenes, hat man lange Zeit nicht genau darüber

nachgedacht, was ein Algorithmus eigentlich genau ist.

Versucht man eine intuitive Beschreibung des Algorithmusbegriffes zu geben so kommt

man zu folgendem Merkmalen:

• Ein Algorithmus besteht aus endlich vielen Anweisungen

• Zu jedem Zeitpunkt steht genau fest, welche Anweisung als nächstes

angewendet werden muss.

• Jede Anweisung ist mechanisch ausführbar.

Problembehaftet ist hierbei insbesondere die dritte Aussage, da es keine genaue

Definition von „mechanisch ausführbar“ gibt.

1.1.2 Der Algorithmus in der Informatik

Warum aber ist eine exakte Definition des Algorithmusbegriffes für die Informatik so

wichtig?

Diese Frage klärt sich, wenn man die Funktionsweise eines Computers analysiert:

Ein Computer ist eine Maschine, die ein Programm ausführt. Auch den Begriff

Programm können wir analog zum Begriff Algorithmus intuitiv wie folgt definieren:

• Ein Programm besteht aus endlich vielen (Maschinen-)Befehlen.

• Zu jedem Zeitpunkt steht genau fest, welcher Befehl als nächstes ausgeführt werden muss

1

• Jeder Befehl ist durch eine Maschine interpretierbar und ausführbar.

Ersetzt man in dieser Definition von Programm das Wort „Befehl“ durch das Wort

„Anweisung“ erhält man wieder die vorige intuitive Algorithmusdefinition. Ein

Programm ist also demnach ein Algorithmus.

Um also das Wesen der Informatik zu verstehen, muss man auch den Begriff des

Algorithmus vollständig durchdrungen haben.

Im Zusammenhang mit Algorithmen stellen sich schließlich zwei entscheidende Fragen:

1. Welche Probleme können durch einen Algorithmus entschieden werden. Gibt es

Probleme, die nicht durch einen Algorithmus entschieden werden können?

Dieses Problem wird als Frage der „algorithmischen Entscheidbarkeit“

bezeichnet.

2. Lässt sich ein Problem in effizienter Zeit durch einen Algorithmus lösen? Dieser

Bereich wird als „Komplexitätstheorie“ bezeichnet.

Wir werden uns im folgenden mit dem ersten Problem befassen, also mit der

algorithmischen Entscheidbarkeit.

1.2 Turings Idee der Turingmaschine als Lösungsansatz

Um die oben angesprochenen Probleme entscheiden zu können, ist es von elementarer

Bedeutung, einen exakten Algorithmusbegriff zu besitzen. Hier wurden im 20

Jahrhundert verschiedene Konzepte vorgeschlagen. Die bedeutendsten sind: 1

1. Die ?-K-Definierbarkeit von Church

2. Die µ-rekursiven Funktionen von Kleene

3. Die Turing-Maschine von Turing

4. Die normalen Algorithmen von Markov

5. Die Grammatiken von Chomsky

¹ vgl. Schlageter [2000] S. 72

2

Es hat sich hierbei gezeigt ,dass diese Konzepte äquivalent sind, also Probleme die in

einem Konzept entscheidbar sind, es auch in jedem anderen sind, und umgekehrt. Ist ein

Problem in einem Konzept nicht lösbar, so ist es dies auch in keinem der anderen

Konzepte.

In der theoretischen Informatik hat sich vor allem das Konzept der Turingmaschine

durchgesetzt. Dies resultiert daher, dass dieses Konzept eine anschauliche maschinelle

Interpretation erlaubt.

1.3 Funktionsweise der universellen Turingmaschine

1.3.1 Definition der Turingmaschine

Der englische Mathematiker A.M. Turing beschreibt sein Konzept einer „Computing

machine“ in etwa wie folgt: 2

Eine Turing-Maschine kann nur eine endliche Anzahl von Bedingungen, sogenannten

Zuständen speichern. Die Summe dieser Zustände wird als Turingprogramm

bezeichnet.

Die Maschine wird von einem Band durchlaufen, das in mehrere Felder unterteilt ist.

Jedes Feld kann mit einem Symbol aus einem definierten Alphabet beschriftet sein.

Die Maschine kann immer nur ein Feld lesen. Das mögliche Verhalten der

Turingmaschine ist zu jedem Zeitpunkt durch den entsprechenden Zustand und das

gelesene Zeichen determiniert. Das mögliche Verhalten wird Operation genannt, und

ist eines der folgenden:

• ein Symbol auf ein leeres Feld schreiben

• ein bedrucktes Feld löschen

• das Band, ein Feld nach rechts oder links bewegen

• stoppen

² vgl. Turing [1936] Kap. 1

3

Die Kombination aus Zustand, gelesenem Zeichen, definiertem Verhalten, sowie der

Festlegung eines Folgezustandes nennt man Konfiguration. Eine Turingmaschine wird

also definiert durch die Summe ihrer Konfigurationen. Der Vollständigkeit halber sollte

auch noch ein Alphabet angegeben werden, aus dem die Symbole auf dem Turingband

stammen. Das Alphabet wird im allgemeinen durch Aufzählung seiner Elemente

definiert:

} { a ,... = Σ n 1

Im Folgenden werden die Begriffe Turingmaschine, Programm und Algorithmus

synonym verwendet.

1.3.2 Schreibweisen der Konfigurationen

Für die Konfigurationen gibt es verschiedene Schreibweisen. Eine recht einfache ist

zum Beispiel die folgende: ³ :

k i a j v k l

Diese Konfiguration bedeutet, dass wenn im Zustand k i das Zeichen a j gelesen wird, die

Operation v ausgeführt wird, und danach zum Folgezustand k l übergegangen wird. Für

v sind hierbei folgende Operationen möglich:

• „r“ - ein Schritt nach rechts

• „l“ - ein Schritt nach links

• „s“ - Stopp

• „a i“ - das Zeichen a i drucken

Ohne die mögliche Funktionalität anzutasten kann man die Konfiguration auch in

folgender Schreibweise definieren:

k i a j a l v k m

Dies liest man dann folgendermaßen: Wenn im Zustand k i das Zeichen a j gelesen wird,

dann wird das Zeichen a l auf das Band geschrieben, danach die Operation v ausgeführt,

³ vgl. Schlageter [2000] S. 76

4

und schließlich zum Folgezustand k m übergegangen. Die Operationen sind hierbei

naturgemäß beschränkt auf r, l und s(Definition wie oben). Es wird also in jedem

Zustand ein Zeichen gedruckt.

Eine Einschränkung oder Erweiterung der Grundfunktionalität der Turingmaschine tritt

hierbei nicht auf. Die zweite Variante lässt sich wie folgt durch zwei Zeilen der ersten

Variante ausdrücken:

k i a j a l k i

k i a l v k m

Die zweite Schreibweise ist bei den meisten Maschinen vorteilhaft, da insgesamt

weniger Konfigurationszeilen benötigt werden. Soll in einem bestimmten Fall kein

neues Zeichen geschrieben werden, so ist dies natürlich auch problemlos formulierbar:

k i a j a j v k m

Die zweite Schreibweise führt also zu kompakteren, und auch leichter verständlichen

Turingmaschinen. Aus diesem Grund wird in den weiteren Betrachtungen stets die

zweite Schreibweise verwendet.

1.3.3 Die universelle Turingmaschine

Die universelle Turingmaschine, wie Sie von Turing in seinem Aufsatz definiert wird,

ist eine Maschine mit einem besonderen Programm:

Diese Turingmaschine kann quasi jede andere Turingmaschine ausführen. Die Maschine

bekommt dazu als „Input“ auf dem Turingband eine „Standard Description“ ⁴ ., kurz S.D.

Diese S.D. ermöglicht es, jede Turingmaschine als Folge von Zeichen auszudrücken.

Durch diese S.D. kann die universelle Turingmaschine quasi das Verhalten jeder

beliebigen Turingmaschine simulieren. Die genaue Funktionsweise wird hier aus

Platzgründen nicht näher erläutert.

1.4 Die Turingmaschine als präziser Algorithmusbegriff

„Because the Turing machines can carry out any computation that can be carried out by

any similar type of automata, and because these automata seems to capture the essential

⁴ Turing [1936] Kap. 5

5

features of real computing machines, we take the Turing machine to be a precise formal

equivalent of the intuitive notion of “algorithm”: nothing will be considered as an

algorithm if it cannot be rendered as a Turing machine” 5

Der Grundsatz, das jeder Algorithmus als Turing-Maschine darstellbar ist, ist als die

Churchsche These bekannt. ⁶ Man kann diese These auch etwas weniger formal wie

folgt ausdrücken:

„Alles was überhaupt berechenbar ist, ist schon mit der Turingmaschine berechenbar.“ 7

Die Mächtigkeit der Aussage wird ersichtlich wenn man Sie etwas umformuliert:

„Alles was mit der Turingmaschine nicht berechenbar ist, lässt sich überhaupt nicht

berechnen.“ 8

Leider lässt sich diese These nicht beweisen, da der Begriff berechenbar allenfalls

intuitiv verstanden werden kann. Trotzdem wird die These inzwischen allgemein

anerkannt:

„Every effectively calculable function that has been investigated in this respect has

turned out to be computable by a Turing machine.” 9

Alle Versuche, diese These zu widerlegen sind bis heute gescheitert.

1.5 Interessante Turingmaschinen

Nun können wir also voraussetzen, dass jeder Algorithmus in Form einer

Turingmaschine formulierbar ist. Dies bedeutet, dass man jedes Programm das in

irgendeiner Programmiersprache geschrieben ist, egal ob Assembler, Java, C++ oder

sonstige, in eine Turingmaschine umformen könnte. Niemand würde nun aber aus

diesem Grund sämtliche Programm, und sämtliche Rechnersystemimplementierungen

in Form von Turingmaschinen gestalten wollen. Die Turingmaschine dient nur als

⁵ Lewis, Papadimitriou [1981] S.223

⁶ Diese eigentliche These von Church ist allerdings eine andere, vermutlich wurde der Begriff in dieser Form zum erstenmal von Kleene geprägt. vgl. Copeland [2000]

⁷ Weuffen [1999]

⁸ Weuffen [1999]

⁹ Copeland [2000]

6

theoretisches Modell. Als reales System wäre Sie weder in der Programmierung

sonderlich komfortabel, noch besonders effizient in der Ausführung.

Wenn wir trotzdem hier einige Turingmaschinen betrachten, so geschieht dies primär

aus theoretischem Interesse, und um darzulegen, dass die Churchsche These richtig ist.

Es folgen nun drei Turingmaschine, deren Implementierung in Java später auch gezeigt

wird.

1.5.1 Einfache Mathematikmaschinen

Hierunter fallen insbesondere Maschinen, mit denen man die Grundrechenarten

simulieren kann. Es gibt hierbei verschiedene Möglichkeiten, die Operanden zu

notieren. Besonders einfach ist hierbei im Bereich der natürlichen Zahlen die unäre

Darstellung. Die unäre Darstellung erfolgt mittels eines unären Alphabets, das also nur

ein Zeichen enthält. Eine Zahl wird dabei über die Anzahl der Zeichen dargestellt, drei

Zeichen stehen also für die Zahl 3. Wir betrachten hier als einfaches Beispiel eine

Maschine, die zwei Zahlen, welche in unärer Darstellung, durch ein Blank getrennt auf

dem Turingband stehen addiert. 10

Die Maschine wird angesetzt auf das erste Zeichen des ersten Eingabewortes. Sie geht

nun so lange nach rechts, bis Sie ein Blank findet. Dieses ersetzt Sie durch das Symbol

(hier 1). Danach geht Sie weiter ans rechte Ende des zweiten Worts, und löscht hier das

letzte Symbol. Danach geht Sie an den Anfang des neuen Wortes. Das Alphabet ist

beschränkt auf zwei Zeichen:

} { 1 = Σ *,

Die Konfiguration dieser Maschine sieht im oben definierten Format wie folgt aus:

z1 * 1 r z2

z1 1 1 r z1

z2 * * l z3

z2 1 1 r z2

z3 * * s z3

z3 1 * l z4

¹⁰ vgl. Weuffen [1999]

7

z4 * * r z5

z4 1 1 l z4

z5 * * s z5

z5 1 1 s z5

1.5.2 Sortieralgorithmen

Als weiteres Beispiel zur Demonstration der Turingmaschine ist die Implementierung

von Sortieralgorithmen geeignet. Als Anwendungsbeispiel genügt uns hier ein sehr

einfacher Algorithmus. Dieser sortiert eine einfache Zeichenkette, die nur aus ‚A’ und

‚B’ besteht. Zuerst einmal benötigt man wieder eine brauchbare Strategie. Hier findet

man bei Weuffen: 11

„Bis kein A mehr vorhanden ist:

Suche ein A, lösche dieses, laufe an das Ende der Bandbeschriftung und füge es dort

ein.

Bis kein B mehr vorhanden ist:

Suche ein B, lösche dieses und schreibe es hinter die Zeichenkette aus A's.“ 12

Da bei den hierbei vorgenommenen Löschungen quasi „Löcher“ in der

Bandbeschriftung entstehen, kann die Maschine nicht „wissen“, ob Sie am Ende

respektive Anfang der Bandbeschriftung ist, oder ob noch andere Zeichen als Blank

folgen. Hier helfen wir ab mit dem Setzen von Markierungen, also zusätzlichen Zeichen

im Alphabet. Das hierbei entstehende Programm ist schon deutlich komplexer. Es

besteht aus 12 Zuständen. Da wir in unserem Alphabet 5 Zeichen benötigen (‚A’, ‚B’,

‚#’ für den Wortanfang, ‚%’ für das Wortende, sowie Blank) würden normalerweise 60

Konfigurationszeilen benötigt. Man kann hierbei jedoch einige Zeilen weglassen, da

bestimmte Konfigurationen aufgrund der Programmlogik nie erreicht würden. Die

komplette Definition dieser Maschine befindet sich im Anhang.

¹¹ vgl. Weuffen [1999]

¹² Weuffen [1990]

8

1.5.3 Unterprogramme

Als Unterprogramme sind Programme definiert, die für sich allein genommen noch

„keinen Sinn“ ergeben. Sie sind dazu gedacht, in anderen Turing-Programmen

„eingebaut“ zu werden, und modellieren häufig benötigte Funktionalitäten. Hierunter

fallen zum Beispiel Maschinen, die Wortanfänge, oder Wortenden suchen,

Kopiermaschinen, Verschiebemaschinen, und weitere. Wir betrachten hier eine einfache

Maschine die das rechte Wortende sucht, wie Sie bei Lewis und Papadimitriou 13

beschrieben wird:

Die Strategie dieser Maschine ist sehr einfach. Angesetzt auf ein beliebiges Zeichen

geht Sie solange nach rechts, bis Sie zu einem Blank kommt. Zur Vereinfachung der

Konfiguration beschränken wir uns wieder auf ein sehr simples Alphabet:

} { 1 = Σ *,

Auch die Konfiguration ist sehr simpel, und kommt mit einem Zustand aus:

z1 * * s z1

z1 1 1 r z1

¹³ vgl. Lewis, Papadimitriou [1981] S. 187

9

2 Objektorientierte Implementierungsansätze für eine

Turingmaschine in Java

2.1 Vorüberlegungen

Als erste Überlegung vor der Implementierung stellt sich die Frage, welche

Eigenschaften die fertige Anwendung haben soll. Diese Ziele habe ich hierbei wie folgt

definiert:

• flexibel einsetzbar.

die Implementierung sollte die Möglichkeit bieten, für möglichst verschiedene

denkbare Anwendungsfälle benutzbar zu sein. Insbesondere bedeutet dies, dass

möglichst viele verschiedene Turingmaschinen abgebildet werden können.

• verständlich

der Source-Code der Implementierung sollte gut lesbar und verstehbar sein.

Dadurch kann bereits die Programmierung als Hilfsmittel zum Verständnis des

Konzepts der Turingmaschine dienen.

• anschaulich

die Benutzeroberfläche sollte so gestaltet sein, dass der Benutzer jeden Schritt

der Turingmaschine nachvollziehen kann.

Einige dieser Aspekte erreichen wir durch das objektorientierte Paradigma relativ leicht.

Die flexible Einsetzbarkeit wird zum Beispiel durch Vererbung unterstützt. Die

Verständlichkeit wird unterstützt durch die Kapselung von Daten und Methoden in

Objekten.

Die Anschaulichkeit ist durch ein gelungenes und einfaches GUI-Design (Graphical

User Interface - Benutzeroberfläche) zu realisieren. Bei der Gestaltung des GUI wird

hierbei davon ausgegangen, das der Benutzer die Grundbegriffe und Ideen einer

Turingmaschine kennt. Ein ausgefeiltes Hilfesystem ist daher nicht nötig.

2.2 Überlegungen zu benötigten Klassen

Die Klassenhierarchie der Turingmaschine leitet sich direkt aus der Definition der

Turingmaschine selbst ab. Die einzelnen Klassen sind hier kurz mit Ihren wichtigsten

Eigenschaften und Methoden beschrieben.

10

2.2.1 TuringMaschine

Diese Klasse bildet die eigentliche Turingmaschine ab, und enthält eine Reihe von

möglichen Zuständen, einen aktuellen Zustand, das zuletzt gelesene Zeichen, und

natürlich ein Turingband. Außerdem besitzt sie eine Methode, die den nächsten Schritt

der Turingmaschine auslöst.

2.2.2 TuringBand

Diese Klasse stellt ein Turingband dar, also eine nicht begrenzte Liste von Zeichen.

Außerdem wird die Position des Schreib-/Lese-Kopfes auf dem Band dargestellt.

Darüber hinaus werden Methoden implementiert die Bewegungen des Schreib/Lese-Kopfes auf dem Band darstellen, sowie die Druckfunktionalität. Es steht außerdem eine

Methode zur Verfügung, die das Zeichen an der aktuellen Position des Schreib- darstellt.

2.2.3 Alphabet

Das Alphabet enthält eine Menge von Zeichen. Es sind Methoden vorhanden, um zu

überprüfen, ob ein bestimmtes Zeichen Teil des Alphabets ist. Außerdem kann zu jedem

Zeichen der Index zurückgegeben werden, bzw. zu einem bestimmten Index das

entsprechende Zeichen.

2.2.4 Zustand

Jeder Zustand enthält eine Reihe von Konfigurationen. Er enthält Methoden, um die

richtige Konfiguration bei einem bestimmten gelesenen Zeichen zu erhalten.

2.2.5 Konfiguration

Die Klasse Konfiguration bildet eine Konfigurationszeile ab, und enthält alle Elemente

dieser Zeile. Funktionen werden nur benötigt, um auf diese Daten zuzugreifen.

Diese fünf Klassen sind ausreichend, um die Funktionalität der Turingmaschine

abzubilden.

2.3 Klassendiagramm

Aus den hier beschrieben Klassen ergibt sich für die Kernfunktionalität das in

Abbildung 1 gezeigte Klassendiagramm.

11

Abbildung 1 Klassendiagramm Kernfunktionalität

Diese Klassen bilden nur die Kernfunktionalität ab. Es kommen später noch Klassen zur

Benutzeranzeige, sowie für die Nachrichtenübertragung hinzu.

Um das Zusammenspiel der hier gezeigten Klassen zu verdeutlichen dient das

nachfolgende Kollaborationsdiagramm. (Abb.2) Es verdeutlicht, was geschieht, wenn

die Methode nextStep() der Klasse TuringMaschine aufgerufen wird.

12

Abbildung 2 Kollaborationsdiagramm nextStep()

2.4 Benutzerinteraktion und Anzeigefunktionalität

Der GUI wird mittels Java-Swing implementiert. Der Benutzer hat hierbei nur 3

Interaktionsmöglichkeiten:

• Er kann ein Eingabewort eingeben.

• Er kann die Maschine starten.

• Er kann das Programm beenden.

Die erste Funktion wird über ein einfaches Texteingabefeld verwirklicht, die anderen

zwei sind über Buttons erreichbar.

Als Ausgabe wird nach jedem Schritt die aktuelle Beschriftung des Turingbandes

angezeigt, wobei das aktuelle Feld farblich markiert ist. Des weiteren soll die

Konfiguration der Turingmaschine angezeigt werden. Der Anwender benötigt zudem

eine Information darüber, ob die Turingmaschine noch läuft, oder ob Sie bereits

13

gestoppt hat. Der fertige GUI sieht dann wie in Abbildung 3 aus (Dargestellt ist die

Sortiermaschine, beim Bearbeiten einer Eingabesequenz.):

Abbildung 3 Sortiermaschine bei der Arbeit

Zur Darstellung der drei verschiedenen Turingmaschinen werden 3 unterschiedliche

Anwendungen benutzt. Diese unterscheiden sich zwar jeweils nur in einer Klasse, es ist

aber durch diese Aufteilung ein einfacheres GUI-Design möglich, da sonst noch eine

Möglichkeit zur Auswahl der Maschine implementiert werden müsste.

14

3 Technische Realisierung

3.1 Umsetzung des Klassendiagramms

Hier wird nur kurz auf die wichtigsten Merkmale der Implementierung eingegangen.

Der vollständige Source-Code sowie ein vollständiges Klassendiagramm befinden sich

im Anhang.

3.1.1 Turingmaschine

Das Klassendiagramm wird nahtlos in 5 Klassen umgesetzt. Dazu kommt noch für jede

Anwendung eine Subklasse von TuringMaschine. Die Klasse TuringMaschine wird

hierbei als abstract definiert - für die konkrete Implementierung einer Turingmaschine

muss also eine Subklasse gebildet werden. Für die drei hier benötigten Maschinen sind

dies die folgenden Subklassen:

• Addierer, dieser implementiert den unären Addierer

• Sortierer, dieser implementiert den Sortieralgorithmus über den Buchstaben A

und B

• RechtsSucher, implementiert die „große Rechtsmaschine“.

Zusätzlich gibt es noch eine Subklasse von Exception, die Klasse

Diese Exception wird von der Methode NotInAlphabetException.

setAktuellZeichen() der Klasse TuringBand geworfen, wenn versucht wird, ein

Zeichen auf das Band zu schreiben das nicht Bestandteil des zugehörigen Alphabets ist.

3.1.2 Benutzerinteraktion

Die Hauptklasse der Benutzerinteraktion bildet die Klasse MainFrame. Sie ist eine

Subklasse von JFrame, stellt also das Hauptfenster der Anwendung dar. Innerhalb

dieses Frame gibt es mehrere Elemente: Direkt in den Frame integriert werden die

Buttons, sowie das Textfeld zur Eingabe der Bandbeschriftung.

Des weiteren gibt es innerhalb von MainFrame noch zwei Panels: KonfigurationsPanel

und TuringBandPanel. Der KonfigurationsPanel dient zur Darstellung der

Konfiguration der aktuellen Turingmaschine, sowie des aktuellen „Betriebszustandes“.

Das TuringBandPanel stellt die aktuelle Beschriftung des Turingbandes dar, und

markiert hierbei das aktuell gelesene Feld.

15

3.2 Umsetzung der benötigten Funktionen

Hier werden nur die wichtigsten Funktionen besprochen:

3.2.1 TuringMaschine

In der Klasse TuringMaschine direkt ist eigentlich nur die Funktion nextStep()

interessant:

public boolean nextStep() throws NotInAlphabetException

{

gelesen = myTuringBand.getAktuellZeichen();

Konfiguration k = zustand.getKonfiguration(gelesen);

char write = k.getWriteSign();

myTuringBand.setAktuellZeichen(write);

if (k.getOperation() == k.LINKS)

myTuringBand.links();

if (k.getOperation() == k.RECHTS)

myTuringBand.rechts();

if (k.getOperation() == k.STOP)

return true;

zustand = k.getFolgeZustand();

return false;

}

Die Methode lässt sich vom Turingband das aktuelle Zeichen geben, und verlangt dann

von einem Objekt der Klasse Zustand die für dieses Zeichen, und den Zustand gültige

Konfiguration. Aus dieser Konfiguration wird das zu schreibende Zeichen genommen,

und auf das Turing-Band geschrieben. Danach wird die noch durchzuführende

Operation ausgeführt. Ist dieser Parameter auf Stop, so terminiert die Methode, und gibt

true zurück. Anderenfalls wird immer false zurückgegeben.

3.2.2 Subklassen von Turingmaschine

Die Subklassen von TuringMaschine überschreiben jeweils die Methode initialize() der

Superklasse. In dieser Methode wird ein Alphabet definiert, sowie die verschiedenen

Zustände und Konfigurationen definiert. Hier das ganze am Beispiel des Unär-

16

Zuerst wird die Größe des Zustandsarrays bestimmt, und zwar natürlich mit der Anzahl

möglicher Zustände(hier 5):

z = new Zustand[5];

Danach wird dieser Array mit Zustandsobjekten gefüllt, die erst mal nur eine Nummer

beinhalten:

for (int i = 0; i < z.length; i++)

z[i] = new Zustand(i + 1);

Jetzt können jedem Zustand seine entsprechende Konfigurationen zugeordnet werden.

Dies geschieht durch Aufruf der Methode

addKonfiguration(char readSign, char writeSign,

int operation, Zustand folgeZustand)

der Klasse Zustand. Hier wieder das Beispiel aus der Addierer Klasse:

z[0].addKonfiguration('*', '1', Konfiguration.RECHTS, z[1]);

z[0].addKonfiguration('1', '1', Konfiguration.RECHTS, z[0]);

z[1].addKonfiguration('*', '*', Konfiguration.LINKS, z[2]);

z[1].addKonfiguration('1', '1', Konfiguration.RECHTS, z[1]);

z[2].addKonfiguration('*', '*', Konfiguration.STOP, z[2]);

z[2].addKonfiguration('1', '*', Konfiguration.LINKS, z[3]);

z[3].addKonfiguration('*', '*', Konfiguration.RECHTS, z[4]);

z[3].addKonfiguration('1', '1', Konfiguration.LINKS, z[3]);

z[4].addKonfiguration('*', '*', Konfiguration.STOP, z[4]);

z[4].addKonfiguration('1', '1', Konfiguration.STOP, z[4]);

Schließlich muss noch ein zugehöriges Alphabet definiert werden, ein leeres Turing-Band erzeugt und mit diesem Alphabet verknüpft, sowie ein Startzustand definiert

werden. Dies geschieht durch folgende Aufrufe:

Alphabet alphabet = new Alphabet("*1");

myTuringBand = new TuringBand(alphabet);

zustand = z[0];

17

3.2.3 MainFrame

Drückt der Benutzer den Button „Maschine starten“, so wird die Methode

actionPerformed dieser Klasse aufgerufen. Hier wird ein Timer gestartet, der in einem

definierten zeitlichen Intervall actionPerformed()-Nachrichten an die registrierten

Empfänger sendet. Der registrierte Empfänger ist in diesem Fall das Objekt der Klasse

TuringBandPanel, dass für die Darstellung des Turingbands zuständig ist. Durch diese

Nachricht wird beim registrierten Empfänger dessen actionPerformed-Methode

ausgeführt.

3.2.4 TuringBandPanel

In der Klasse TuringBandPanel wird in der Methode actionPerformed jeweils der

nächste Schritt der Turingmaschine angestoßen. Danach wird die neue Beschriftung des

Turingbands ausgegeben.

public void actionPerformed(ActionEvent arg)

{

try

{

if (!myTuringMaschine.nextStep())

{

setText(myTuringMaschine.getTuringBand());

} else

//Maschine ist gestoppt.

} catch (NotInAlphabetException e)

{

//Fehlerbehandlung

}

}

Die Methode setText sorgt für die richtige Darstellung des Turingbandes. Dazu wird das

aktuell gelesene Feld farblich markiert, und in die Mitte der Darstellung geschrieben.

Links und rechts wird dann die weitere Beschriftung des Bandes angezeigt, und mit

Blanks aufgefüllt.

18

3.3 Das fertige Programm

3.3.1 Bedienung

Das Starten einer der drei Turingmaschine ist einfach: Vorausgesetzt wird hier das

Betriebssystem Microsoft Windows 95 oder höher, sowie ein korrekt installiertes Java

Runtime Environment, Version 1.3 oder höher. Zum Starten einer der Turingmaschinen

kann man einfach das entsprechende JAR-File doppelklicken:

• Addierer.jar für den Start des Unär-Addierers

• Sortierer.jar für den Start des Sortierprogramms

• Rechtssucher.jar für die „große Rechtsmaschine“

Danach muss nur noch in dem Textfeld eine entsprechende Eingabesequenz eingegeben

werden, und der Button „Maschine starten“ betätigt werden. Zum Testen können

beispielsweise folgende Eingabesequenzen benutzt werden:

• 1111*111 für den Unär-Addierer

• ABBABA für den Sortierer

• 111111111 für die „große Rechtsmaschine“

3.3.2 Fazit

Mit der Programmierung dieser Turingmaschine wurden die oben definierten Ziele im

wesentlichen erreicht. Natürlich wären im Einzelnen noch Verbesserungen,

insbesondere bei der Benutzerschnittstelle möglich. Das Programm hat allerdings mehr

Demonstrationscharakter, und muss daher auch nicht alle Merkmale einer komplexen

Anwendungssoftware erfüllen. Natürlich konnte hier nicht auf alle

Implementierungsdetails eingegangen werden. Für weitere Informationen hierzu wird

daher auf den angehängten Source-Code, bzw. auf die Javadoc-Dokumentation auf der

beigelegten CD verwiesen.

19

Literaturverzeichnis

Copeland, J: The Church-Turing Thesis, „Online im Internet”, http://www.alanturing.net/turing_archive/pages/Reference%20Articles/The%20Turing-Church%20Thesis.html Juni 2000, Abfrage am 17.02.2003

Horstmann, C.S.; Cornell, G.: Core Java 2 - Volume 1 Fundamentals ,10. Aufl. Sun Micorsystems Press, 1999

Horstmann, C.S.; Cornell, G.: Core Java 2 - Volume 2 Advanced Features ,4. Aufl. Sun Micorsystems Press, 2000

Lewis, H.R.; Papadimitriou, C.H.: Elements of the Theory of Computation, 3. Aufl., Prentice-Hall International London, 1981

Schlageter, W.; Rauhut, O.: Einführung in die theoretische Informatik, Heilbronn, 2000

Turing, A.M: On computable numbers, with an application to the Entscheidungsproblem, in: Proceedings of the London Mathematical Society, ser. 2. vol.42, 1936, S. 230-265.

Weuffen, G.: Die Turingmaschine „Biber am laufenden Band“, „Online im Internet“ http://www.matheprisma.de/Module/Turing/index.htm Dezember 1999, Abfrage am 17.02.2003

20

  Anlagenverzeichnis  

  Definition der Sortiermaschine.  22

  Klassendiagramm  24

  Source-Code.  1

  Addierer.java  1

  Alphabet.java  2

  Konfiguration.java.  4

  KonfigurationsPanel.java.  6

  MainFrame.java.  8

  NotInAlphabetException.java  10

  RechtsSucher.java  11

  Sortierer.java.  12

  TuringBand.java  14

  TuringBandPanel.java  17

  TuringMaschine.java.  20

  Zustand.java.  22

  Inhalt der beigefügten CD.  24

21

Definition der Sortiermaschine

Die Sortiermaschine mit folgendem Alphabet:

} { *, B A = % , # ,

wird durch die nachfolgenden Konfigurationen definiert:

z1 A A l z1

z1 B B l z1

z1 * # r z2

z2 A A r z2

z2 B B r z2

z2 * % l z3

z3 A A l z3

z3 B B l z3

z3 # # r z4

z3 * * l z3

z3 % % l z3

z4 A * r z5

z4 B B r z4

z4 * * r z4

z4 % % l z7

z5 A A r z5

z5 B B r z5

z5 * * r z5

z5 % % r z6

z6 A A r z6

z6 * A l z3

z7 % % l z7

z7 A A l z7

z7 B B l z7

z7 * * l z7

z7 # # r z8

z8 B * r z9

22

z8 * * r z8

z8 % * l z11

z9 B B r z9

z9 * * r z9

z9 % % r z10

z10 A

z10 B B r z10

z10 *

z11 * * l z11

z11 # * r z12

z12 * * r z12

z12 A

z12 B B s z12

23

Klassendiagramm

24

Source-Code

Addierer.java

package de.hm.turing;

/**

* Addiert zwei Zahlen in unärer Darstellung * Test-Klasse zur Funktionalitätsprüfung der Turing-Klassen * @author Robin Hermann * */

public class Addierer extends TuringMaschine {

public String getBezeichnung() { return "Addierer"; }

public void initialize() { z = new Zustand[5]; for (int i = 0; i < z.length; i++) z[i] = new Zustand(i + 1);

z[0].addKonfiguration('*', '1', Konfiguration.RECHTS, z[1]);

z[0].addKonfiguration('1', '1', Konfiguration.RECHTS, z[0]);

z[1].addKonfiguration('*', '*', Konfiguration.LINKS, z[2]); z[1].addKonfiguration('1', '1', Konfiguration.RECHTS, z[1]);

z[2].addKonfiguration('*', '*', Konfiguration.STOP, z[2]); z[2].addKonfiguration('1', '*', Konfiguration.LINKS, z[3]); z[3].addKonfiguration('*', '*', Konfiguration.RECHTS, z[4]);

z[3].addKonfiguration('1', '1', Konfiguration.LINKS, z[3]); z[4].addKonfiguration('*', '*', Konfiguration.STOP, z[4]); z[4].addKonfiguration('1', '1', Konfiguration.STOP, z[4]);

Alphabet alphabet = new Alphabet("*1"); myTuringBand = new TuringBand(alphabet); zustand = z[0]; }

public static void main(String[] arg) {

MainFrame f = new MainFrame(new Addierer()); f.show(); } }

1

Alphabet.java

package de.hm.turing;

/**

* Alphabet gehört zu einer Turingmaschine, respektive einem TuringBand.

* Es enthält alle Zeichen, die auf dem TuringBand enthalten sein dürfen. * @author Robin Hermann * */ public class Alphabet {

private char[] zeichen;

/**

* Erzeugt ein neues Alphabet, mit allen Zeichen die übergeben werden.

* Per Definitition steht dabei das Zeichen, das blank symbolisieren soll an * erster Stelle.

* @param alphabet Alle Zeichen, die übergeben werden sollen. * */

public Alphabet(String alphabet) {

zeichen = new char[alphabet.length()]; for (int i = 0; i < alphabet.length(); i++) { zeichen[i] = alphabet.charAt(i); } }

/**

* Erzeugt ein neues Alphabet, mit allen Zeichen die übergeben werden.

* Beim index 0 wird dabei das Zeichen das blank symbolisieren soll übergeben.

* @param alphabet Alle Zeichen, die im Alphabet enthalten sein sollen. */

public Alphabet(char[] alphabet) { zeichen = alphabet; }

/**

* Gibt das i-te Zeichen im Alphabet zurück. * @param index Index des gewünschten Zeichens * @return Das Zeichen */

public char getZeichen(int index) { return zeichen[index]; }

/**

* Liefert den Index zu einem bestimmten Zeichen. * @param a das Zeichen * @return int der Index des Zeichens. */

2

public int getIndex(char a) { for (int i = 0; i < zeichen.length; i++) {

if (zeichen[i] == a) return i; }

return -1; }

/**

* Überprüft, ob ein bestimmtes Zeichen Bestandteil des Alphabets ist.

* @param a Das Zeichen, dass überprüft werden soll. * @return boolean true, wenn das Zeichen im Alphabet ist. */

public boolean isInAlphabet(char a) { boolean temp = false; for (int i = 0; i < zeichen.length; i++) { if (zeichen[i] == a) temp = true;

} return temp; } }

3

Konfiguration.java

package de.hm.turing;

/**

* Diese Klasse bildet eine Konfigurationszeile ab. * @author Robin Hermann * */

public class Konfiguration {

// Operationskonstanten public static final int RECHTS = 1; public static final int LINKS = -1; public static final int STOP = 0;

private char readSign; //gelesenes Zeichen private char writeSign; //zu schreibendes Zeichen private int operation; //auszuführende Operation als int (s. Konstanten) private Zustand folgeZustand;

//Zustand nach Ausführung dieser Konfiguration

public Konfiguration( char readSign, char writeSign, int operation, Zustand folgeZustand) { this.readSign = readSign; this.writeSign = writeSign; this.folgeZustand = folgeZustand; this.operation = operation; }

/**

* Überprüft, ob diese Konfiguration ein bestimmtes Zeichen als * Eingangsbedingung hat. * @param a Zeichen, das verglichen werden soll * @return boolean true, wenn dieses Zeichen Eingangsbedingung für * diese Konfiguration ist. */

public boolean checkReadSign(char a) { if (this.readSign == a) return true; return false; }

/**

* Gibt das als Eingangsbedingung zu lesende Zeichen zurück. * @return char */ public char getReadSign() {

4

return readSign; }

/**

* Gibt die Operation zurück, die bei Ausführung dieser Konfiguration * ausgeführt werden soll

* @return int a value, whisch is one of the constants from this class */ public int getOperation() { return operation; }

/**

* Gibt das Zeichen zurück, dass an die aktuelle Stelle auf das * TuringBand geschrieben werden soll * @return char Das zu schreibende Zeichen */ public char getWriteSign() { return writeSign; }

/**

* Gibt den Folgezustand nach Ausführung dieser Konfiguration zurück.

* @return Zustand Ein Objekt mit diesem Zustand. */

public Zustand getFolgeZustand() { return folgeZustand; } }

5

KonfigurationsPanel.java

package de.hm.turing;

import javax.swing.JPanel; import javax.swing.JScrollPane; import javax.swing.JTextArea;

/**

* Diese Klasse bildet das Panel für die Konfiguration der Turingmaschine ab. * * @author Robin Hermann * */

public class KonfigurationsPanel extends JPanel {

private TuringMaschine myTuringMaschine; private JTextArea description; private final String run = "Turingmaschine läuft \n"; private final String stop = "Turingmaschine gestoppt\n";

/**

* Konstruktur für die Konfigurationsanzeige * @param m Die Turingmaschine, deren * Konfiguration dargestellt werden soll. */

public KonfigurationsPanel(TuringMaschine m) { super(); this.myTuringMaschine = m; description = new JTextArea(15, 30); description.setAutoscrolls(true); description.setTabSize(7); description.append("Turingmaschine steht\n"); description.setEditable(false); //Zustände durchlaufen:

for (int i = 0; i < myTuringMaschine.z.length; i++) {

myTuringMaschine.z[i].getKonfigurationen().length;

{

6

.getKonfigurationen()[j]

} }

add(new JScrollPane(description));//mit Scrollbalken.

}

/** * @see

java.awt.event.ActionListener#actionPerformed(ActionEvent) */ public void action() {

if (myTuringMaschine.isRunning()) description.replaceRange(run, 0, run.length());

else description.insert(stop, 0);

} }

7

MainFrame.java

package de.hm.turing;

import java.awt.Container; import java.awt.Dimension; import java.awt.Toolkit;

import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.event.WindowAdapter; import java.awt.event.WindowEvent;

import javax.swing.JButton; import javax.swing.JFrame; import javax.swing.JLabel; import javax.swing.JPanel; import javax.swing.JTextField; import javax.swing.Timer;

/**

* Hauptfensterklasse der TuringMaschine * @author Robin Hermann * */

public class MainFrame extends JFrame implements ActionListener { private JButton nextStep; private JButton quit; private TuringBandPanel tb; private TuringMaschine m; private JTextField sequenz; private KonfigurationsPanel k; public Timer t; public MainFrame(TuringMaschine m) {

super("Turingmaschine " + m.getBezeichnung()); this.m = m; m.initialize();

//innere Klasse zum Schließen des Fenster wenn das X gedrückt wird. addWindowListener(new WindowAdapter() {

public void windowClosing(WindowEvent w)

}); //Dieser Abschnitt dient zur zentralen Platzierung des Frame auf dem Desktop Toolkit tk = Toolkit.getDefaultToolkit(); Dimension d = tk.getScreenSize(); int screenHeight = d.height; int screenWidth = d.width; setSize(screenWidth / 2, screenHeight / 2); setLocation(screenWidth / 4, screenHeight / 4);

8

Container contentPane = getContentPane(); //Der "Basiscontainer" des Frames

//Zwei Buttons einfügen JPanel buttons = new JPanel(); nextStep = new JButton("Maschine starten"); nextStep.addActionListener(this);

quit = new JButton("Programm Ende"); quit.addActionListener(this);

buttons.add(nextStep); buttons.add(quit);

//input enthält Eingabeelemente JPanel input = new JPanel();

JLabel label1 = new JLabel("Eingabesequenz");

sequenz = new JTextField(20);

input.add(label1); input.add(sequenz);

//center enthält die zentralen Elemente Band und Konfiguration JPanel center = new JPanel(); k = new KonfigurationsPanel(m); tb = new TuringBandPanel(m, k, this); center.add(tb); center.add(k);

contentPane.add(buttons, "South"); contentPane.add(center, "Center"); contentPane.add(input, "North");

}

/** * @see

java.awt.event.ActionListener#actionPerformed(ActionEvent) */

public void actionPerformed(ActionEvent evt) {

if (evt.getSource() == nextStep) {

diesen anhalten

}

if (evt.getSource() == quit)

9

} }

NotInAlphabetException.java

package de.hm.turing;

/**

* Wird geworfen, wenn versucht wird, ein Zeichen einzufügen, * das nicht im Alphabet vorkommt. * @author Robin Hermann * */

public class NotInAlphabetException extends Exception {

/**

* Constructor for NotInAlphabetException. */

public NotInAlphabetException() { super(); }

/**

* Constructor for NotInAlphabetException. * @param arg0 */

public NotInAlphabetException(String arg0) { super(arg0); }

}

10

RechtsSucher.java

package de.hm.turing;

/**

* Implementiert die große Rechtssuchmaschine * @author Robin Hermann * */

public class RechtsSucher extends TuringMaschine {

public String getBezeichnung() {

return "Große Rechtsmaschine"; }

/**

* @see de.hm.turing.TuringMaschine#initialize() */ public void initialize() { z = new Zustand[1]; z[0] = new Zustand(1);

z[0].addKonfiguration('*', '*', Konfiguration.STOP, z[0]); z[0].addKonfiguration('1', '1', Konfiguration.RECHTS, z[0]);

Alphabet a = new Alphabet("*1"); myTuringBand = new TuringBand(a); zustand = z[0]; }

public static void main(String[] arg) {

MainFrame f = new MainFrame(new RechtsSucher()); f.show(); }

}

11

Sortierer.java

package de.hm.turing;

/**

* Diese Klasse implementiert einen Sortierer über zwei Buchstaben * 'A' und 'B' * @author Robin Hermann * */

public class Sortierer extends TuringMaschine {

public String getBezeichnung() { return "Sortierer"; }

public void initialize() {

z = new Zustand[12];

for (int i = 0; i < z.length; i++) z[i] = new Zustand(i + 1);

z[0].addKonfiguration('A', 'A', Konfiguration.LINKS, z[0]); z[0].addKonfiguration('B', 'B', Konfiguration.LINKS, z[0]); z[0].addKonfiguration('*', '#', Konfiguration.RECHTS, z[1]);

z[1].addKonfiguration('A', 'A', Konfiguration.RECHTS, z[1]);

z[1].addKonfiguration('B', 'B', Konfiguration.RECHTS, z[1]);

z[1].addKonfiguration('*', '%', Konfiguration.LINKS, z[2]);

z[2].addKonfiguration('A', 'A', Konfiguration.LINKS, z[2]); z[2].addKonfiguration('B', 'B', Konfiguration.LINKS, z[2]); z[2].addKonfiguration('#', '#', Konfiguration.RECHTS, z[3]);

z[2].addKonfiguration('*', '*', Konfiguration.LINKS, z[2]); z[2].addKonfiguration('%', '%', Konfiguration.LINKS, z[2]);

z[3].addKonfiguration('A', '*', Konfiguration.RECHTS, z[4]);

z[3].addKonfiguration('B', 'B', Konfiguration.RECHTS, z[3]);

z[3].addKonfiguration('*', '*', Konfiguration.RECHTS, z[3]);

z[3].addKonfiguration('%', '%', Konfiguration.LINKS, z[6]);

z[4].addKonfiguration('A', 'A', Konfiguration.RECHTS, z[4]);

z[4].addKonfiguration('B', 'B', Konfiguration.RECHTS, z[4]);

z[4].addKonfiguration('*', '*', Konfiguration.RECHTS, z[4]);

12

z[4].addKonfiguration('%', '%', Konfiguration.RECHTS, z[5]);

z[5].addKonfiguration('A', 'A', Konfiguration.RECHTS, z[5]);

z[5].addKonfiguration('*', 'A', Konfiguration.LINKS, z[2]);

z[6].addKonfiguration('%', '%', Konfiguration.LINKS, z[6]); z[6].addKonfiguration('A', 'A', Konfiguration.LINKS, z[6]); z[6].addKonfiguration('B', 'B', Konfiguration.LINKS, z[6]); z[6].addKonfiguration('*', '*', Konfiguration.LINKS, z[6]); z[6].addKonfiguration('#', '#', Konfiguration.RECHTS, z[7]);

z[7].addKonfiguration('B', '*', Konfiguration.RECHTS, z[8]);

z[7].addKonfiguration('*', '*', Konfiguration.RECHTS, z[7]);

z[7].addKonfiguration('%', '*', Konfiguration.LINKS, z[10]);

z[8].addKonfiguration('B', 'B', Konfiguration.RECHTS, z[8]);

z[8].addKonfiguration('*', '*', Konfiguration.RECHTS, z[8]);

z[8].addKonfiguration('%', '%', Konfiguration.RECHTS, z[9]);

z[9].addKonfiguration('A', 'A', Konfiguration.RECHTS, z[9]);

z[9].addKonfiguration('B', 'B', Konfiguration.RECHTS, z[9]);

z[9].addKonfiguration('*', 'B', Konfiguration.LINKS, z[6]);

z[10].addKonfiguration('*', '*', Konfiguration.LINKS, z[10]);

z[10].addKonfiguration('#', '*', Konfiguration.RECHTS, z[11]);

z[11].addKonfiguration('*', '*', Konfiguration.RECHTS, z[11]);

z[11].addKonfiguration('A', 'A', Konfiguration.STOP, z[11]);

z[11].addKonfiguration('B', 'B', Konfiguration.STOP, z[11]);

Alphabet a = new Alphabet("*AB#%"); myTuringBand = new TuringBand(a, "ABBABABA"); zustand = z[0]; }

public static void main(String[] arg) {

MainFrame f = new MainFrame(new Sortierer()); f.show(); } }

13

TuringBand.java

package de.hm.turing;

/**

* Diese Klasse repräsentiert ein nach beiden Seiten unbegrenztes Turingband

* Außerdem enthält es die aktuelle Position des Schreiblesekopfes. * @author Robin Hermann * */ public class TuringBand {

private int index = 0; //Der aktuelle Stand des Schreib/Lesekopfes

private int position = 0; //Das gelesene Feld private String band; private Alphabet myAlphabet;

public TuringBand(Alphabet alphabet) {

this.myAlphabet = alphabet; } /**

* @param myAlphabet Das Alphabet mit den Zeichen die das TuringBand beinhalten darf * @param band Das Band als Array von Zeichen */

public TuringBand(Alphabet myAlphabet, char[] band) {

this.myAlphabet = myAlphabet; String temp = ""; for (int i = 0; i < band.length; i++) { temp = temp + band[i];

} this.band = temp;

}

/**

* @param myAlphabet Das zugeordnete Alphabet * @param band Das Band als Array von Zeichen */

public TuringBand(Alphabet myAlphabet, String band) {

this.myAlphabet = myAlphabet; this.band = band;

}

/**

* Liefert das zu diesem Band gehörende Alphabet * @return Alphabet */

public Alphabet getAlphabet() {

14

return myAlphabet; }

public void setBeschriftung(String band) { this.band = band; }

/**

* Gibt das Zeichen an der aktuellen Position des Schreiblesekopfes zurück.

* @return Das Zeichen an der aktuellen Position des Schreiblesekopfes. */

public char getAktuellZeichen() {

return band.charAt(position); }

/**

* Schreibt das übergebene Zeichen an der aktuellen Position des Schreib/Lese-Kopfes * auf das Turing-Band.

* @param zeichen Das Zeichen das geschrieben werden soll. * @throws NotInAlphabetException wenn versucht wird, ein Zeichen einzufügen, dass nicht * im Alphabet vorhanden ist. */

public void setAktuellZeichen(char zeichen) throws NotInAlphabetException {

if (!myAlphabet.isInAlphabet(zeichen)) {

throw new NotInAlphabetException(); }

StringBuffer b = new StringBuffer(band); b.setCharAt(position, zeichen); band = b.toString();

}

/**

* Gibt die aktuelle Position des Schreib/Lesekopfes auf dem String der mit * getString() zurückgegeben wird. * @return int Die aktuelle Position des Schrib/Lesekopfes */

public int getAktuellPosition() { return position; }

/**

* Gibt den aktuellen Index der Position des Schreib-Lesekopfes. Der Index

* 0 steht hierbei bei dem ersten Zeichen des Eingabewortes. * @return int */

public int getAktuellIndex() {

15

return index; }

/**

* setzt die aktuelle Position des Schreib/Lesekopfes ein Feld nach rechts. */ public void rechts() { ++index; ++position; if (position == band.length()) {

band = band + myAlphabet.getZeichen(0); } }

/**

* Setzt die aktuelle Position des Schreib/Lesekopfes um ein Feld nach Links. */ public void links() {

--index; --position; if (position == -1) {

}

} /**

* Liefert die Beschriftung des TuringBandes im relevanten Bereich als String. */ public String getString() { return band; } }

16

TuringBandPanel.java

package de.hm.turing;

import java.awt.Color; import java.awt.Dimension; import java.awt.Font;

import java.awt.event.ActionEvent; import java.awt.event.ActionListener;

import javax.swing.JLabel; import javax.swing.JPanel;

/**

* Auf diesem Panel wird das Turing-Band während des * Programmlaufs dargestellt.

* Diese Klasse implementiert die Schnittstelle ActionListener, * da Sie ActionEvents vom Timer der bei Durck auf Maschine starten * anläuft erhalten kann. * */

public class TuringBandPanel extends JPanel implements ActionListener {

// 3 Label für die Ausgabe des Turingbandes private JLabel labell; //TuringBand links vom aktuellen Feld private JLabel labela; //Aktuelles Feld des Turingbandes private JLabel labelr; //TuringBand rechts vom aktuellen Feld private KonfigurationsPanel kp;

private String beschriftung; //Die Beschriftung des TuringBands private TuringMaschine myTuringMaschine; private Dimension d; private char blank; private MainFrame m;

public TuringBandPanel( TuringMaschine myTuringMaschine, KonfigurationsPanel kp, MainFrame m) { this.m = m;

this.myTuringMaschine = myTuringMaschine; this.kp = kp; labell = new JLabel(""); labela = new JLabel(""); labelr = new JLabel(""); labell.setForeground(Color.black); labela.setForeground(Color.red); labelr.setForeground(Color.black); Font f = new Font("Monospaced", Font.PLAIN, 12); labell.setFont(f); labela.setFont(f); labelr.setFont(f); add(labell); add(labela); add(labelr); blank =

myTuringMaschine.getTuringBand().getAlphabet().getZeichen(0); }

17

public void setTuringMaschine(TuringMaschine tm) {

this.myTuringMaschine = tm;

}

/** * Method setText.

* Diese Methode schreibt die aktuelle Beschriftung des TuringBandes

* auf das Panel. Dabei wird der aktuelle Stand des Turingbandes farblich markiert. * @param tb TuringBand * */

public void setText(TuringBand tb) {

labela.setText(tb.getString());

final int size = 60; // Die angezeigte Länge des Turingbandes

StringBuffer sb = new StringBuffer(tb.getString());

int pos = tb.getAktuellPosition(); char akt;

StringBuffer sbl = new StringBuffer(); StringBuffer sbr = new StringBuffer(); ;

//Der String wird in zwei StringBuffer aufgeteilt if (pos > 0) {

sbl = new StringBuffer(sb.substring(0, pos - 1)); }

if ((pos + 1) < sb.length()) {

sbr = new StringBuffer(sb.substring(pos + 1)); }

akt = sb.charAt(pos);

//Die StringBuffer werden auf eine einheitliche Länge gebracht

while (sbl.length() < size) { sbl.insert(0, blank); } if (sbl.length() > size) {

sbl = new StringBuffer(sbl.substring(sbl.length()size)); }

while (sbr.length() < size) { sbr.append(blank); }

if (sbr.length() > size)

18

{

sbr = new StringBuffer(sbr.substring(0, size)); }

//Das Turingband wird ausgegeben.

labell.setText(sbl.toString()); labela.setText(" " + akt + " "); labelr.setText(sbr.toString()); repaint();

}

/** * Method setText.

* Setzt einen freien Text auf das TuringBand * @param text Der zu setzende Text */

public void setText(String text) { beschriftung = text; labell.setText(beschriftung); repaint();

} /**

* Führt den nächsten Schritt der der TuringMaschine aus, und schreibt * das Ergebnis. * @see

java.awt.event.ActionListener#actionPerformed(ActionEvent) */

public void actionPerformed(ActionEvent arg) {

try {

myTuringMaschine.getTuringBand().getString());

} else { }

} catch (NotInAlphabetException e) {

//Hier sollte irgendetwas sinnvolles getan werden. } } }

19

TuringMaschine.java

package de.hm.turing;

/**

* Zentrale Klasse zur Ausführung der Turingmaschine
* Um eine Turingmaschine auszuführen muss eine Subklasse dieser Klasse * gebildet werden.

* Diese muss die Methode inititalize() * überschreiben, und hier die Zustände und Konfigurationen definieren. * @author Robin Hermann * */

public abstract class TuringMaschine {

protected TuringBand myTuringBand; Zustand[] z; //alle Zustände Zustand zustand; //Beschreibt den aktuellen Zustand private char gelesen; //Enthält das gelesene Zeichen private boolean running = false; ;

/**

* Gibt die Bezeichnung dieser Turingmaschine zurück * @return String */

public abstract String getBezeichnung();

/**

* Initialisiert die Turingmaschine. */

public abstract void initialize();

/**

* Führt den nächsten Schritt abhängig von Zustand und gelesenem Zeichen aus.

* Zeigt an ob die Maschine stoppt, oder ob weitere Schritte folgen.

* @return boolean true wenn Maschine stoppt */

public boolean nextStep() throws NotInAlphabetException { if (!running) running = true;

gelesen = myTuringBand.getAktuellZeichen(); Konfiguration k = zustand.getKonfiguration(gelesen); char write = k.getWriteSign(); myTuringBand.setAktuellZeichen(write); if (k.getOperation() == k.LINKS) myTuringBand.links(); if (k.getOperation() == k.RECHTS) myTuringBand.rechts(); if (k.getOperation() == k.STOP) {

20

}

zustand = k.getFolgeZustand(); return false; }

/**

* Liefert true zurück, wenn die Turingmaschine noch läuft * @return boolean */ public boolean isRunning() { return running; }

/**

* Liefert das Turingband, das von dieser Maschine bearbeitet wird. * @return TuringBand */

public TuringBand getTuringBand() { return myTuringBand; } }

21

Zustand.java

package de.hm.turing;

/**

* Zustand, in dem sich eine Turing-Maschine befinden kann. *
Jeder Zustand sollte für jedes lesbare Zeichen eine Konfiguration enthalten. * @author Robin Hermann * */ public class Zustand {

private int zustandsNummer; private Konfiguration[] myKonfiguration;

public Zustand(int zustandsnummer) { this.zustandsNummer = zustandsNummer; myKonfiguration = new Konfiguration[0]; }

public boolean equals(Zustand zustand) { if (this.zustandsNummer == zustand.zustandsNummer) return true; return false; }

/**

* Diese Methode fügt dem Zustand eine weitere Konfigurationszeile hinzu.
*

* @param readSign Das Zeichen das gelesen werden muss, um diese Konfig. auszuführen * @param writeSign Zu schreibendes Zeichen * @param operation Auszuführende Operation (Konstante aus Konfiguration) * @param folgeZustand Nächster Zustand * */

public void addKonfiguration( char readSign, char writeSign, int operation, Zustand folgeZustand) { Konfiguration k =

new Konfiguration(readSign, writeSign, operation, folgeZustand); Konfiguration[] temp = new Konfiguration[myKonfiguration.length + 1]; for (int i = 0; i < myKonfiguration.length; i++) { temp[i] = myKonfiguration[i];

}

temp[myKonfiguration.length] = k; myKonfiguration = temp;

}

22

/**

* Gibt die Nummer dieses Zustandes zurück. * @return int */ public int getNummer() { return zustandsNummer; }

/**

* Gibt die Konfiguration zu einem bestimmten gelesenen Zeichen zurück.

* @param readSign Das Zeichen das gelesen wurde * @return Konfiguration Die Konfiguration zu diesem Zeichen. */

public Konfiguration getKonfiguration(char readSign) { for (int i = 0; i < myKonfiguration.length; i++) {

if (myKonfiguration[i].checkReadSign(readSign))

} return null; }

/**

* Liefert alle Konfigurationen eines Zustandes zurück. * @return Konfiguration[] */

public Konfiguration[] getKonfigurationen() { return myKonfiguration; } }

23

Inhalt der beigefügten CD

Folgende Ordner finden sich auf der beigehefteten CD:

• html-quellen: Dieser Ordner enthält die zitierten Internetquellen.

• jar-files: In diesem Ordner sind die ausführbaren JAR-Files enthalten.

• java-doc: Die mittels javadoc generierte Beschreibung des Source-Codes.

• source: Der Sourcecode der Anwendung

• uml: Die UML-Diagramme zu dieser Anwendung.

Im Hauptverzeichnis ist außerdem die elektronische Version dieser Studienarbeit als

Winword2000-Dokument.

24

Ehrenwörtliche Erklärung

Ich versichere hiermit, dass ich diese Studien-/Diplomarbeit selbständig verfasst habe

und keine anderen als die angegebenen Quellen und Hilfsmittel benutzt habe.

................................ ....................................

Ort, Datum Unterschrift

25