| www.r-krell.de |
| Webangebot für Schule und Unterricht, Software, Fotovoltaik und mehr |
Willkommen/Übersicht > Informatik > Informatik mit Java, Seite t3)
Fortsetzung Teil t): Simulation einer
Turing-Maschine in/mit Java
Seite t3): Benötigte Eigenschaften und Fähigkeiten im
Hintergrund
Auf der ersten Projekt-Seite if-t-turi.htm wurden bereits allgemeiner Aufbau und Funktion einer Turing-Maschine sowie die Grundvorhaben des Projekts erläutert. Auf der zweiten Projektseite if-t-turi2.htm wurden verschiedene Verfahren zum Speichern und erneuten Öffnen eines Turingmaschinen-Modells untersucht und mit Quelltext vorgestellt. Jetzt geht es darum, welche grundsätzlichen Eigenschaften und Fähigkeiten eine programmierte Turingmaschine besitzen muss - und zwar weitesgehend unabhängig von der Benutzeroberfläche, die mit ihren eigenen spezifischen Methoden später auf einer folgenden Seite vorgestellt wird. Denn wie bei fast allen meinen Programmen sollen die eigentliche Funktion (die das Thema dieser Seite ist) und die Gestaltung der Oberfläche in getrennten Klassen realisiert werden. Grundlegenden Eigenschaften (Attribute bzw. globale Variablen oder Datenfelder) wurden z.T. schon auf der vorangehenden, zweiten Projektseite beschrieben - zumindest soweit sie auch gespeichert werden. Neben der Ergänzung einiger weiterer Attribute für den Betrieb liegt deshalb das besondere Augenmerk auf den Fähigkeiten (realisiert durch Prozeduren und Funktionen, d.h. durch Methoden), die für die Arbeit der Turingmaschine bzw. im Zusammenspiel mit der Oberfläche benötigt werden.
Projekt:
Entwicklung einer Turing-Maschinen-Simulation,
hier: benötigte
Eigenschaften und Fähigkeiten für die Arbeit im
Hintergrund
2. Fähigkeiten von
TM_BandEine vollständige Übersicht aller "Informatik mit Java"-Seiten gibt's auf der Informatik-Hauptseite. Viele der dort aufgeführten Seiten enthalten ausführlich beschriebene Java-Programme im Quelltext. Außerdem wird auf die Seiten SWE1 und SWE2 zum Software-Engineering hingewiesen.
zum Seitenanfang / zum Seitenende
Auf der vorigen Webseite if-t-turi2.htm dieses Projekts war bereits die zentrale Klasse der Turingmaschinen-Simulation vorgestellt worden. Die zum Speichern nötigen Datenfelder (Variablen bzw. Java-Attribute) waren dort im obersten Abschnitt b) genannt und begründet worden; die Java-Klasse erhielt dann im Abschnitt Cb3) mit Turing_zum_Speichern3 ihre letzte im Quelltext vorgestellte Fassung, wobei am Ende des dortigen Abschnitts Cb3) ("Natürlich kann Abhilfe geschaffen werden: ..") noch einige Anpassung empfohlen wurden. Die entsprechend verbesserte Version wird jetzt unter dem Namen TM_Maschine Grundlage für die weiteren Überlegungen; die früher als Turingmaschinen_Eintrag3X erwähnte Hilfsklasse heißt ab sofort schlicht TM_Eintrag. Die mit @ beginnenden Annotations geben an, dass und unter welcher Tag-Bezeichnung die jeweils nachfolgende Eigenschaft (=Datenfeld=Attribut) in eine XML-Datei übertragen wird.
zum Seitenanfang / zum Seitenende
Hier also der Anfang der Klasse TM_Maschine (der Text der Datei wurde auf 4 Kästen verteilt; die Attribute im zweiten, weiß unterlegten Kasten kommen neu hinzu. Im vierten Kasten folgen Konstruktoren, danach kämen weitere Methoden (Fähigkeiten).
| import javax.xml.bind.annotation.*; import java.util.*; import java.io.*; import javax.xml.*; import javax.xml.bind.*; @XmlRootElement(name="Turingmaschine") public class TM_Maschine // Hauptklasse der simulierten Turingmaschine, macht die Arbeit (nach Aufforderung durch die/aus der // Oberfläche) -- R.Krell 10/2019 für r-krell.de/if-t-turi3.htm { |
| String meldung = ""; // nimmt Warnungen und Fehlermeldungen auf String dateiname = ""; // merkt sich den zuletzt benutzten Dateinamen für leichtes erneutes Speichern String aktuellerZustand = null; // merkt sich den Namen des aktuellen Zustands der Machine int schrittNr = -1; // zählt mit, wie viele Schritte die Maschine schon gearbeitet hat int sichtbareBandlänge = 13; // weiß, wie groß das in der Oberfläche angezeigte Bandstück ist int bandPosLinks = -3; // merkt sich den Index der Bandstelle, die in der Oberfläche ganz links angezeigt wird int kopfPos = 0; // merkt sich den Index der Bandstelle, an der der Kopf steht TM_Band band = null; // Objekt für das verwendete Band (Achtung: unterscheidet sich von TM_GespeichertesBand) final int S_VORHER = 0; // Konstanten zur Beschreibung des Maschinen-Status... final int S_LAEUFT = 1; final int S_PAUSE = 2; final int S_FEHLER = 5; final int S_HAELT = 9; int status = S_VORHER; // merkt sich den aktuellen Status der Maschine |
| @XmlElement(name="Hinweis") String hinweis0 = "*** Gespeicherte Turingmaschine für das Programm \"TuringMa_J\", www.r-krell.de/if-t-turi.htm ***"; @XmlElement(name="Hinweis1") String hinweis1 = "** Das erste Zeichen im Bandalphabet ist das Leerzeichen **"; @XmlElement(name="Hinweis2") String hinweis2 = "** Der erste Zustand bei Zustaende ist der Startzustand; der letzte Zustand ist der Haltzustand **"; @XmlElement(name="Hinweis3") String hinweis3 = "** Die 3 Kopfbewegungssymbole stehen für die Kopfbewegungen LINKS (-1), STILL (0) und RECHTS (1) **"; @XmlElement(name="Hinweis4") String hinweis4 = "** Die EingabeOption gilt für die Bildschirm-Eingabereihenfolge innerhalb eines Eintrags **"; @XmlElementWrapper(name="Bandalphabet") @XmlElement(name="Zeichen") String[] bandalphabet; // enthält alle les- und schreibbaren Schriftzeichen; bandalphabet[0] = Leerzeichen @XmlElementWrapper(name="Zustaende") @XmlElement(name="Zustand") String[] zustand; // Namen aller Zustände; zustand[0] = Startzustand, zutand[maxIndex] = Endzustand @XmlElementWrapper(name="KopfbewegungsSymbole") @XmlElement(name="Symbol") String[] kopfbewegung; // genau drei Zeichen, z.B. 'L','S','R' oder '-','0','+' oder '<','=','>' @XmlElementWrapper(name="Maschinentafel") @XmlElement(name="Eintrag") ArrayList<TM_Eintrag> einträge; // lineare Liste der nicht-leeren Maschinentafel-Einträge (bel. Reihenfolge) // könnte, muss aber nicht als @XmlTransient gekennzeichnet werden: kommt nicht in XML! TM_Eintrag[][] maschinentafel; // 2-dim. geordnete Tabelle für bandalphabet.length x (zustand.length - 1) Einträge @XmlElement(name="EingabeOption") int reihenfolgenopt; // Option für Reihenfolge im Turing_Eintrag (möglich: eine der Konstanten aus Turing_Eintrag) @XmlElementWrapper(name="Kommentar") @XmlElement(name="Zeile") String[] kommentar; // mehrzeilige Beschreibung/Erläuterung zur Turing-Maschine @XmlElementWrapper(name="GespeicherteBaender") @XmlElement(name="Band") TM_GespeichertesBand[] bandbeschriftung; // Bandinschriften mit Position, Kopfposition und Anzahl der Schritte bis zur Inschrift |
| public TM_Maschine () { } // ("no-arg"-Standard-)Konstruktor wird sonst nicht benutzt, ist aber nötig für JAXB-Marshalling public TM_Maschine (String[] abc, String[] zustände, String[] richtungssymbole, ArrayList<TM_Eintrag> eintragsliste, int opt, String[] anmerkung, TM_GespeichertesBand[] bänder) // Turingmaschine wird aus den Angaben konstruiert, Maschinentafel passend gefüllt { bandalphabet = abc; zustand = zustände; kopfbewegung = richtungssymbole; einträge = eintragsliste; reihenfolgenopt = opt; kommentar = anmerkung; bandbeschriftung = bänder; fülleMaschinentafel(); } public TM_Maschine (String[] abc, String[] zustände, String[] richtungssymbole, TM_Eintrag[][] tabelle, int opt, String[] anmerkung, TM_GespeichertesBand[] bänder) // Turingmaschine wird aus den Angaben konstruiert, Liste einträge passend gefüllt { bandalphabet = abc; zustand = zustände; kopfbewegung = richtungssymbole; maschinentafel = tabelle; reihenfolgenopt = opt; kommentar = anmerkung; bandbeschriftung = bänder; fülleEinträge(); } ... (weitere Methoden werden weiter unten im Kapitel 3 auf dieser Seite vorgestellt!) |
Wie man sieht, gibt es für manche Inhalte bzw. Werte zwei verschiedene Datenstrukturen: Einmal werden Einträge in einer statischen, 2-dimensionalen Tabelle maschinentafel verwaltet (was für das rasche Auffinden des richtigen Eintrags während des Ablaufs der Simulation günstiger ist), zum anderen werden die gleichen Einträge in praktisch beliebiger Reihenfolge in der dynamischen, linearen ArrayList einträge gespeichert (was das Schreiben und besonders das Wiedereinlesen der Einträge in bzw. aus einer XML-Datei auf Festplatte, SSD oder USB-Stick erleichtert). Die in den Konstruktoren angegebenen Methoden fülleEinträge bzw. fülleMaschinentafel kopieren die Einträge auch in die jeweils andere Datenstruktur - nötig, wenn nur eine Struktur übergeben wird (die aufwändigere der beiden Methoden wird später im Kapitel 4 sogar mit komplettem Quelltext vorgestellt). Außerdem gibt es - wie weiter unten am Ende von Abschnitt 1c noch angesprochen wird - auch scheinbar zwei Bänder: GespeicherteBänder (1c) und ein 'normales' Band (1d).
zum Seitenanfang / zum Seitenende
Die erwähnten Einträge enthalten jetzt auch das alte
Zeichen und den alten Zustand und entsprechen nun dem
Java-Quelltext TM_Eintrag:
| import javax.xml.bind.annotation.*; @XmlRootElement(name="eintragX") // wird nicht von JAXB berücksichtigt beim Marshalling, stattdessen "Eintrag" aus Klasse TM_Maschine public class TM_Eintrag // Eintrag in Maschinentafel der Turingmaschine, macht die Arbeit. -- R. Krell 10/2019 für r-krell.de/if-t-turi3.htm { final static int ZCH_KOPF_ZST = 0; // Option für die Reihenfolge Ausgabezeichen - Kopfbewegung - Folgezustand final static int ZCH_ZST_KOPF = 1; // Option für die Reihenfolge Ausgabezeichen - Folgezustand - Kopfbewegung final static int ZST_ZCH_KOPF = 2; // Option für die Reihenfolge Folgezustand - Ausgabezeichen - Kopfbewegung final static int LINKS = -1; // interne Darstellung der Kopfbewegung, uabhängig von Anzeige als kopfbewegung[0] final static int STILL = 0; // interne Darstellung der Kopfbewegung, uabhängig von Anzeige als kopfbewegung[1] final static int RECHTS = +1; // interne Darstellung der Kopfbewegung, uabhängig von Anzeige als kopfbewegung[2] @XmlElement(name="AltesZeichen") String altesZeichen; // aktuell an der Kopfposition vom Band gelesenes Zeichen @XmlElement(name="AlterZustand") String alterZustand; // aktueller Zustand der Turingmaschine (vorm und beim Lesevorgang) @XmlElement(name="NeuesZeichen") String neuesZeichen; // Ausgabezeichen, das an der Kopfposition aufs Band geschrieben wird @XmlElement(name="Kopfbewegung") int kopfbewegung; // Bewegung des Kopfes (Werte sind nur LINKS, STILL oder RECHTS) @XmlElement(name="NeuerZustand") String neuerZustand; // Folgezustand, den die Turingmaschine für den nächsten Arbeitsschritt annimmt public TM_Eintrag () // ("no-arg"-Standard-)Konstruktor wird sonst nicht benutzt, ist aber nötig für JAXB-Marshalling { // hätte offenbar auch leer sein können, statt auffällig-sinnlos zu füllen altesZeichen = "???"; alterZustand = "**(ungültiger Eintrag)**"; neuesZeichen = "???"; kopfbewegung = 0; neuerZustand = "???"; } public TM_Eintrag (String altZchn, String altZst, String neuZchn, int bew, String neuZst) { altesZeichen = altZchn; alterZustand = altZst; neuesZeichen = neuZchn; kopfbewegung = bew; neuerZustand = neuZst; } } |
zum Seitenanfang / zum Seitenende
Außerdem wird wie auf der letzten Seite if-t-turi2.htm (allerdings statt dort als TM_Band jetzt unter dem Namen TM_GespeichertesBand) noch folgende Klasse benutzt:
| import javax.xml.bind.annotation.*; @XmlRootElement(name="Band") public class TM_GespeichertesBand // gespeichertes bzw. aktuelles Band der Turingmaschine -- R. Krell 10/2019 für r-krell.de/if-t-turi3.htm { @XmlElement(name="Schritte") int schrittzahl; // gibt an, nach wievielen Arbeitsschritten die Bandinschrift erreicht wurde @XmlElement(name="StartPosition") int indexBeschriftungsstart; // Position von bandinschrift[0] auf dem Band @XmlElement(name="KopfPosition") int indexKopf; // Position des Kopfes @XmlElement(name="Inschrift") String bandinschrift; // gespeicherte Bandinschrift @XmlElement(name="Anmerkung") String kommentar; // Anmerkung zur Bandinschrift bzw. zum erreichten Zwischenstand public TM_GespeichertesBand () { } // ("no-arg"-Standard-)Konstruktor wird sonst nicht benutzt, ist aber nötig für JAXB-Marshalling public TM_GespeichertesBand (int schritte, int start, int kopfposition, String inschrift, String anmerkung) { schrittzahl = schritte; indexBeschriftungsstart = start; indexKopf = kopfposition; bandinschrift = inschrift; kommentar = anmerkung; } } |
Achtung: Die vorstehende Klasse TM_GespeichertesBand ist für das Abspeichern bzw. Wiedereinlesen von Zwischenständen vorgesehen (sie hieß auf der letzten Seite if-t-turi2.htm noch TM_Band, während der gleiche Name künftig für die neue Klasse aus Abschnitt 1d gelten soll); einige Attribute wie schrittzahl können von schrittNr aus TM_Maschine in ein gespeichertes Band übernommen werden. Die Bandinschrift wird darin als einfache Zeichenkette verwaltet. Solche Strings können zwar nach rechts, aber schlecht nach links wachsen. Für den Betrieb der Turingmaschine ist daher eine dynamische Bandverwaltung besser, damit das Band bei Bedarf in beide Richtungen erweitert und der Kopf leicht hin und her bewegt werden kann. Deswegen gibt es noch die folgende neue Klasse:
zum Seitenanfang / zum Seitenende
Das Band wird hier als doppeltverkettete Liste aus Bandknoten realisiert, wobei jeder Knoten ein Feld des Bandes repräsentiert. Mehr über verkettete Listen findet sich z.B. auf meiner "Informatik-mit-Java"-Seite e) mit dem Thema Lineare abstrakte Datentypen. Die neue, am Ende des vorstehenden Abschnitts 1e schon begründete und für den Betrieb der Maschine sinnvolle(re) Banddefinition steht in der neuen zusätzlichen Klasse TM_Band, die wie folgt beginnt:
| public class TM_Band // aktuelles Band der Turingmaschine -- R.Krell 10/2019 für r-krell.de/if-t-turi3.htm { char leerzeichen; int sichtbareLänge = -1; TM_Bandknoten mitte = null; TM_Bandknoten liRand = null; TM_Bandknoten reRand = null; TM_Bandknoten liSichtbar = null; TM_Bandknoten kopf = null; public TM_Band (char leer, int länge) // erzeugt ein neues, leeres Band (mit Leerzeichen leer) und setzt sichtbareLänge auf länge { leerzeichen = leer; sichtbareLänge = länge; mitte = new TM_Bandknoten (leerzeichen, 0, null, null); liRand = mitte; reRand = mitte; kopf = mitte; } ... (und weitere, später beschriebene Methoden) |
wobei jeder der erwähnten Bandknoten folgendem Java-Bauplan genügt:
| public class TM_Bandknoten // TM_Band besteht aus doppelt-verketteter Liste von TM_Bandknoten -- R. Krell 10/2019 für r-krell.de/if-t-turi3.htm { char inhalt; // Zeichen (des Bandalphabets), das an dieser Stelle auf dem Band steht int index; // Index = laufende Nummer der aktuellen Bandstelle/des Feldes TM_Bandknoten links; // Zeiger auf die vorangehende Bandstelle bzw. den Bandknoten TM_Bandknoten rechts; // Zeiger auf die nachfolgende Bandstelle bzw. den Bandknoten public TM_Bandknoten (char inh, int ind, TM_Bandknoten li, TM_Bandknoten re) { // Konstruktor füllt Attribute mit übergebenen Werten inhalt = inh; index = ind; links = li; rechts = re; } } |
In dem beim Speichern bzw. zum Öffnen auf dem Datenträger abgelegten XML-Text taucht TM_Band nicht auf, wie man auch im Folgenden sieht. Schließlich wurde oben in der Klasse TM_Maschine das Objekt band nach dem Bauplan der Klasse TM_Band bei den weiß unterlegten Attributen aufgeführt, die keine Annotation für die XML-Datei haben. Nur das gespeicherte Band schafft es in die XML-Datei. Im Kapitel 2 folgen Methoden, die zwischen den beiden Banddarstellungen konvertieren.
zum Seitenanfang / zum Seitenende
Die XML-Datei gehört eigentlich weder zu den Eigenschaften noch zu den Fähigkeiten. Sie war Thema der letzten Seite: Eine XML-Datei kann die Turingmaschine zusammen mit schon teilweise bearbeiteten Bändern auf der Festplatte, einer SSD, einem USB-Stick, in der Cloud oder auf einem anderen Datenträger dauerhaft sichern. Die Daten im Hauptspeicher gehen ja beim Beenden/Schließen des Programms verloren und müssten sonst beim nächsten Start des Simulationsprogramms erneut eingegeben werden. Wie auf der vorigen Seite erklärt wurde, eignen sich XML-Dateien besonders zur Datenspeicherung, weil sie sehr zukunftssicher sind. Mithilfe der in Java enthaltenen JAXB-Bibliothek und den in vorstehenden Quelltexten schon eingefügten Annotations gelingt das Speichern sogar mit recht geringem Programmier-Aufwand. Mit speichere3 wurde schon eine geeignete Methode vorgestellt, die auf der vorigen Seite im Abschnitt Cb3) noch in der Extra-Klasse Turing_XML_Speichertest3 untergebracht war. Diese Methode kann aber unverändert (hier als speichere) in die Klasse TM_Maschine eingefügt werden (s.u., Kapitel 3). Die damit auf dem Datenträger abgelegte, aus der oben angegebenen Fassung von TM_Maschine erzeugte XML-Datei hat dann folgendes Aussehen (für die Beispielmaschine zur bitweisen Addition - siehe letzte Seite!), das hier eher als Ergänzung zur letzten Seite angegeben wird:
<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<Turingmaschine>
<Hinweis>*** Gespeicherte Turingmaschine für das Programm "TuringMa_J", www.r-krell.de/if-t-turi.htm ***</Hinweis>
<Hinweis1>** Das erste Zeichen im Bandalphabet ist das Leerzeichen **</Hinweis1>
<Hinweis2>** Der erste Zustand bei Zustaende ist der Startzustand; der letzte Zustand ist der Haltzustand **</Hinweis2>
<Hinweis3>** Die 3 Kopfbewegungssymbole stehen für die Kopfbewegung LINKS (-1), STILL (0) und RECHTS (1) **</Hinweis3>
<Hinweis4>** Die EingabeOption gilt für die Bildschirm-Eingabereihenfolge innerhalb eines Eintrags **</Hinweis4>
<Bandalphabet>
<Zeichen>_</Zeichen>
<Zeichen>0</Zeichen>
<Zeichen>1</Zeichen>
</Bandalphabet>
<Zustaende>
<Zustand>1</Zustand>
<Zustand>2</Zustand>
<Zustand>3</Zustand>
<Zustand>4</Zustand>
<Zustand>5</Zustand>
</Zustaende>
<KopfbewegungsSymbole>
<Symbol><</Symbol>
<Symbol>=</Symbol>
<Symbol>></Symbol>
</KopfbewegungsSymbole>
<Maschinentafel>
<Eintrag>
<AltesZeichen>0</AltesZeichen>
<AlterZustand>1</AlterZustand>
<NeuesZeichen>_</NeuesZeichen>
<Kopfbewegung>1</Kopfbewegung>
<NeuerZustand>2</NeuerZustand>
</Eintrag>
<Eintrag>
<AltesZeichen>1</AltesZeichen>
<AlterZustand>1</AlterZustand>
<NeuesZeichen>_</NeuesZeichen>
<Kopfbewegung>1</Kopfbewegung>
<NeuerZustand>3</NeuerZustand>
</Eintrag>
<Eintrag>
<AltesZeichen>_</AltesZeichen>
<AlterZustand>2</AlterZustand>
<NeuesZeichen>_</NeuesZeichen>
<Kopfbewegung>1</Kopfbewegung>
<NeuerZustand>2</NeuerZustand>
</Eintrag>
<Eintrag>
<AltesZeichen>0</AltesZeichen>
<AlterZustand>2</AlterZustand>
<NeuesZeichen>0</NeuesZeichen>
<Kopfbewegung>1</Kopfbewegung>
<NeuerZustand>5</NeuerZustand>
</Eintrag>
<Eintrag>
<AltesZeichen>1</AltesZeichen>
<AlterZustand>2</AlterZustand>
<NeuesZeichen>1</NeuesZeichen>
<Kopfbewegung>1</Kopfbewegung>
<NeuerZustand>5</NeuerZustand>
</Eintrag>
<Eintrag>
<AltesZeichen>_</AltesZeichen>
<AlterZustand>3</AlterZustand>
<NeuesZeichen>_</NeuesZeichen>
<Kopfbewegung>1</Kopfbewegung>
<NeuerZustand>3</NeuerZustand>
</Eintrag>
<Eintrag>
<AltesZeichen>0</AltesZeichen>
<AlterZustand>3</AlterZustand>
<NeuesZeichen>1</NeuesZeichen>
<Kopfbewegung>1</Kopfbewegung>
<NeuerZustand>5</NeuerZustand>
</Eintrag>
<Eintrag>
<AltesZeichen>1</AltesZeichen>
<AlterZustand>3</AlterZustand>
<NeuesZeichen>1</NeuesZeichen>
<Kopfbewegung>1</Kopfbewegung>
<NeuerZustand>4</NeuerZustand>
</Eintrag>
<Eintrag>
<AltesZeichen>_</AltesZeichen>
<AlterZustand>4</AlterZustand>
<NeuesZeichen>0</NeuesZeichen>
<Kopfbewegung>1</Kopfbewegung>
<NeuerZustand>5</NeuerZustand>
</Eintrag>
</Maschinentafel>
<EingabeOption>0</EingabeOption>
<Kommentar>
<Zeile>Diese Turingmaschine addiert zwei Bits.</Zeile>
<Zeile>Sie ist am Ende des Abschnitts b2) auf www.r-krell.de/if-t-turi.htm als zweite, kürzere Variante</Zeile>
<Zeile>beschrieben & wird hier als willkürlich ausgesuchtes Beispiel verwendet.</Zeile>
</Kommentar>
<GespeicherteBaender>
<Band>
<Schritte>0</Schritte>
<StartPosition>2</StartPosition>
<KopfPosition>2</KopfPosition>
<Inschrift>1_1</Inschrift>
<Anmerkung>Die Summe 1+1=10 soll die beiden Summanden ersetzen</Anmerkung>
</Band>
</GespeicherteBaender>
</Turingmaschine>
Abweichend von den Verbesserungsvorschlägen unten auf der letzten Seite if-t-turi2.htm wurde das Bandalphabet doch nicht als kompakter String, sondern als Reihung einzelner Zeichen gespeichert (damit man besser sehen kann, welche Zeichen für die alten und neuen Zeichen im Eintrag in Frage kommen); ähnliches gilt für die Kopfbewegungssymbole. Gegenüber früher wurden außerdem oben in TM_Maschine manche Tag-Bezeichner noch etwas ausführlicher formuliert und alle zum leichteren Lesen mit Großbuchstaben begonnen.
zum Seitenanfang / zum Seitenende
Wie oben auf dieser Seite am Ende des Abschnitts 1c und am Anfang von Abschnitt 1d schon gesagt, soll ein Objekt vom Typ TM_Band ermöglichen, dass bei Bedarf (spätestens wenn sich der Kopf dorthin bewegen will) das Band in beide Richtungen verlängert werden kann. Wie schon in 1d angegeben, eignet sich dazu eine doppelt verkettete Liste von Knoten. Natürlich bedarf es auch geeigneter Methoden. Dabei muss auch daran gedacht werden, dass später in der Oberfläche immer nur ein Teil des Bandes (der sichtbare Teil) dargestellt werden kann. Deshalb sind die einzelnen Felder nummeriert (damit - wenn z.B. der Kopf nach rechts aus dem bisher sichtbaren Teil heraus wandern würde - das Band nach links geschoben werden kann und der Kopf mit einem anderen Teil des Bandes sichtbar bleibt. An den Feldnummern [Indizes] sieht man, welcher Teil sichtbar ist). Der Konstruktor erzeugt zunächst ein Band mit nur einem einzigen Feld (repräsentiert durch den Bandknoten mitte) mit dem Index (=der Feldnummer) 0 und dem Leerzeichen als Inhalt. Bei Bedarf wird das Band verlängert (vgl. Quelltext im Kapitel 4, s.u.).
public TM_Band (char leer, int länge) // Konstruktor
erzeugt ein neues, leeres Band (mit Leerzeichen leer) und setzt sichtbareLänge auf länge
public void fülleBandMitInschrift (int abIndex, String inschrift) // schreibt inschrift aufs Band; Rest wird geleert
public char kopfLies () // liest und nennt Bandzeichen (altesZeichen) unter dem Kopf
public TM_Bandknoten nenneKopf () // nennt den Knoten des Bandes unter dem Kopf (und
damit das Bandzeichen und den
Index)
public void kopfSchreib (char zeichen) // schreibt mit dem / am Kopf das zeichen aufs Band
public void kopfBew (int um) // bewegt den Kopf um die angebene Felderzahl um auf dem Band
public int nenneIndexKopf () // nennt den im Bandknoten am Kopf gespeicherten Index (=Feldnummer)
public int nenneIndexLiRand () // nennt den im linkesten benutzten Bandknoten gespeicherten Index
public int nenneIndexReRand () // nennt den im rechtesten benutzten Bandknoten gespeicherten Index
public int nenneIndexLiSichtbar () // nennt den Index des Bandknotens, der in der Oberfläche gerade links sichtbar ist
public TM_Bandknoten[] zeigeBand (int abIndex) // kopiert die Knoten des gerade sichtbaren Teils des Bandes (für Oberfläche)
public String nenneInschrift() // nennt (fürs Speichern) alle Zeichen des benutzten Teils des Bandes in einem String
Nachdem ich vor Kurzem im Artikel 'Magic: The Gathering - Das komplexeste Spiel von allen' in der Zeitschrift "Spektrum der Wissenschaft", Heft 9/2019, S. 31-34, gelesen habe, dass man das Spiel Magic mittels einer Turingmaschine simulieren kann, deren Kopf sich allerdings nicht nur um -1, 0 oder +1 Feld(er) auf dem Band nach rechts bewegen kann, sondern um jede ganze Zahl von Feldern springen kann, habe ich mich entschlossen, oben bei kopfBew eine beliebige Ganzzahl um zuzulassen. Verlässt der Kopf dabei den bisher benutzten (und erzeugten) Teil des Bandes, müssen in der Methode kopfBew weitere Knoten mit fortlaufendem Index und dem Leerzeichen als Inhalt erzeugt und ans Band angefügt werden. Der vollständige Quelltext von kopfBew folgt im Kapitel 4.
Beim Speichern eines Zwischenstandes soll nur der beschriebene Teil des Bandes als Text gespeichert werden (dazu gibt es nenneInschrift, um die entsprechende Zeichenkette zu erhalten und nenneLiRand für die Startposition dieses Stücks); umgekehrt soll beim Öffnen eines zuvor gespeicherten Bandes mit fülleBandMitInschrift ein passende Band erzeugt werden können (wobei auch liRand und reRand entsprechend gesetzt werden müssen). Da beim Öffnen (Wiedereinlesen vom Datenträger) eines zuvor gespeicherten Bandes auch die Kopfposition gelesen wird, an die der Kopf gesetzt werden muss, wäre auch noch eine Methode public setzeKopfAufFeld (int kopfposition) denkbar. Allerdings erzielt der Aufruf von kopfBew(nenneIndexKopf() - kopfposition); den gleichen Effekt, sodass auf ein eigene Methode verzichtet wird.
zum Seitenanfang / zum Seitenende
Auf der letzten Seite wurde bereits über das Speichern und Öffnen gesprochen und entsprechende Methoden mit Quelltext vorgestellt. Diese Methoden wurden hier in die Klasse übernommen und erzeugen bzw. lesen eine XML-Datei der oben im Abschnitt 1e beispielhaft angegeben Form:
public void speichere () // schreibt aktuelle Maschine per JAXB-Befehlen als XML auf Datenträger
public void öffne () // übernimmt die vom Datenträger gelesene Turingmaschine als/ins aktuelles Objekt
// liest XML-Datei mit JAXB-Mitteln ein
Vor der Neueingabe einer Turingmaschine über die Tastatur müssen aktuelle Werte gelöscht werden. In öffne werden übernehme und einige weitere der nachfolgenden Methoden aufgerufen.
public void übernehme (TM_Maschine tm) // kopiere alle Datenfelder von tm ins aktuelle Objekt (this)
public void lösche () // setze alle Datenfelder/Attribute des aktuellen Turingmaschinen-Objekts (this) auf null
Wie bereits erwähnt, können die Maschinentafel-Einträge entweder in einer statischen 2-dimensionalen Tabelle oder in einer dynamischen linearen Liste stehen und bei Bedarf jeweils in die andere Form übernommen werden. Dafür sorgen nachfolgende Methoden, wobei vor dem Speichern mit fülleEinträge aus der Tabelle die Liste erzeugt und dann abgespeichert wird; nach dem Öffnen wird hingegen mit fülleMaschinentafel aus der von der XML-Datei eingelesenen Liste (wieder) die Tabelle erstellt. Während hier nur der Header und als Kommentar eine Textbeschreibung angegeben sind, folgt ein kompletter Java-Quelltext unten im Kapitel 4.
public void fülleMaschinentafel () // kopiert alle Einträge aus der Liste einträge in die Maschinentafel
public void fülleEinträge () // kopiert alle Einträge aus der Maschinentafel in die Liste einträge
Außerdem sollte beim Öffnen die eingelesene Turingmaschine kontrolliert werden: Durch technische Defekte oder durch bewusste Manipulation der XML-Datei mit einem Texteditor könnten z.B. Hinweise verändert, unerlaubte Zeichen in Einträgen oder auf einem gespeicherten Band stehen oder Zustände verloren gegangen sein. Allerdings ist es empfehlenswert, die Kontrolle nicht 'am Stück' in einer großen Methode zu programmieren, sondern aus kontrolle lieber mehrere einzelne Teil-Kontrollen aufzurufen. Die Teilmethoden können dann auch verwendet werden, um z.B. bei der Benutzereingabe über die Oberfläche zu prüfen, ob eingetippte Zeichen oder Zustände zulässig sind. Weil z.B. die Zeichen des Bandalphabets wegen der besser lesbaren Übertragung in die XML-Datei als Strings gespeichert werden, muss nachgeprüft werden können, ob die Zeichenketten wirklich je genau ein Zeichen enthalten. Außerdem müssen alle Zeichen des Bandalphabets verschieden sein. Ebenso müssen alle Zustände der Zustandsmenge verschieden sein. Beides kann durch die gleiche Methode geprüft werden. Und in Einträgen oder auf dem Band dürfen nur Zeichen auftauchen, die wirklich im Bandalphabet vorkommen. Meine folgenden boolean-Methoden geben je nach Ergebnis der Prüfung wahr oder falsch zurück. Die Methoden, deren Namen mit kontrolle... beginnen, geben entweder einen leeren Text (wenn alles in Ordnung war) oder eine verständliche Fehlerbeschreibung als String-Funktionswert zurück (vgl. auch Beispiel in Kapitel 4, s.u.):
public String kontrolle() // kontrolliert gesamte Turingmaschine auf Konsistenz und nennt ggf. Fehler
private String kontrolleBandalphabet() // kontrolliert bandalphabet und nennt ggf. Fehler
private String kontrolleZustände() // kontrolliert zustände und nennt ggf. Fehler
private String kontrolleKopfbewegungssymbole() // kontrolliert kopfbewegung und nennt ggf. Fehler
private boolean allesEinstellig (String[] reihe) // prüft, ob Strings in der reihe je genau 1 Zeichen enthalten
private boolean allesVerschieden (String[] reihe) // prüft, ob es in der reihe nicht verbotenerweise zwei gleiche Strings gibt
private boolean erlaubtesZeichen (String zch) // prüft, ob zch wirklich im bandalphabet vorkommt
private boolean erlaubterZustand (String zst, int x) // prüft, ob zst wirklich in zustände vorkommt
// dabei möglich: x=0 mit Haltezustand (für neuenZustand) oder bei x=-1 ohne Haltzustand (für altenZustand)
private boolean erlaubterEintrag (TM_Eintrag eintrag) // prüft, ob alle 5 Komponenten vom (Maschinentafel-)eintrag erlaubt sind
private boolean erlaubteMaschinentafel () // prüft, ob die Maschinentafel nur erlaubte Einträge enthält
private boolean erlaubteBandinschrift (String inschrift) // prüft, ob inschrift nur aus Zeichen des Bandalphabets besteht
Wenn es darum geht, Methoden für die eigentliche Arbeit der Turingmaschine zu entwickeln, so muss berücksichtigt werden, dass bei der Simulation die einzelnen (Teil-)Schritte in der Oberfläche veranschaulicht werden sollen. Es ist daher nicht sinnvoll, innerhalb einer einzigen Methode einen kompletten Arbeitsschritt der Maschine auszuführen, also das Zeichen vom Band zu lesen, das neue Zeichen zu schreiben, den Kopf zu bewegen und den neuen Zustand anzunehmen. Schließlich kann die aufrufende Oberfläche nicht in die Methode hineingucken und die Teilschritte sehen, sondern bekäme erst am Ende das Gesamtergebnis. Und die Methode soll ihrerseits ja keine Details der später austauschbaren Oberfläche kennen müssen (um selbst dort Teilschritte zu visualisieren). Statt dessen ist geplant, dass (1) die Oberfläche nachfragt, welches Zeichen der Kopf an seiner aktuellen Position vom Band liest. Dann kann die Oberfläche in ihrer Darstellung der Maschinentafel die passende Spalte der Tabelle farbig hervorheben. (2) Dann kann die Oberfläche den aktuellen Zustand erfragen und in der Maschinentafel-Anzeige die passende Zeile markieren. Am Schnittpunkt sieht man den jetzt benötigten Eintrag. (3) Die Oberfläche muss diesen Eintrag erfahren, um die neuen Werte kennen zu lernen und damit zu arbeiten: (4) Die Oberfläche veranlasst das Schreiben des neuen Buchstabens und zeigt die entsprechende Änderung in der Banddarstellung. (5) Die Oberfläche stößt die aus dem Eintrag erfahrene Kopfbewegung an und veranschaulicht mit einer geeigneten Animation die Verschiebung des Kopfes. (6) Die Oberfläche macht den neuen Zustand zum aktuellen und aktualisiert die Anzeigen des gegenwärtigen Zustandsnamens und der Schrittzahl und löscht alle Markierungen des letzten Arbeitsschrittes. Für jeden Teilschritt müssen passende Methoden zur Interaktion zwischen aufrufender Oberfläche und der hier entwickelten Maschine bereit gestellt werden, also etwa:
public int nenneSchrittzahl () // gibt an, wie viele (Arbeits-)Schritte die Turingmaschine schon ausgeführt hat
public int indexGelesenesZeichen () // nennt die Position des altenZeichens innerhalb der Reihung bandalphabets
public int indexAktZustand() // nennt die Position von aktuellerZustand innerhalb der Reihung zustände
public char nenneNeuesZeichen() // nennt das neu zu schreibende Zeichen als char
public void schreibeNeuesZeichen() // schreibt das neue Zeichen am/mit dem Kopf aufs Band
public int indexNeuerZustand() // nennt die Position vom neuen Zustand innerhalb der Reihung zustände
public String nenneNeuenZustand() // nennt den Namen des neuen (nächsten) Zustands
public int nenneKopfBewegungAlsZahl() // nennt die auszuführende Kopfbewegung als Zahl, z.B. -1
public String nenneKopfBewegungAlsWort() // nennt die auszuführende Kopfbewegung als Text, z.B. "'<'=-1"
public void bewegeKopf() // führt die eingetragene Kopfbewegung auf dem Band aus und erhöht die schrittNr um 1
Weil - wie oben bei den Teilschritten (1) und (2) schon notiert - Zeilen und Spalten in der angezeigten Maschinentafel markiert werden sollen, interessiert dafür eher die Zeilen- oder Spaltennummer (also der Index) als das Zeichen oder der Zustandsname selbst. Deswegen wurden indexGelesenesZeichen und indexAktZustand bereitgestellt, ebenso wie indexNeuerZustand. Der neue Zustand wird aber auch namentlich gebraucht.
Trotz aller Sorgfalt bei den Überlegungen, welche Methoden wohl benötigt werden, kann sich beim Programmieren der Oberfläche noch herausstellen, dass eine Methode vergessen wurde oder eine jetzt vorgesehene Methode gar nicht gebraucht wird. Entsprechend sind Veränderungen an dieser Übersicht nicht auszuschließen. Trotzdem werden die hier mit ihrem Header aufgeführten Methoden erstmal vollständig in Java programmiert und sollten möglichst auch getestet werden, bevor wir uns danach der Oberfläche zuwenden.
zum Seitenanfang / zum Seitenende
Der Aufbau vieler der oben genannten Methoden ist recht naheliegend und der Quelltext ist oft schnell erstellt oder erfordert in anderen Fällen zwar einigen Fleiß und Sorgfalt, aber keine wirklich schwierigen programmtechnischen Konstruktionen. Um nicht zu langweilen, sollen hier nur wenige Methoden ausführlicher vorgestellt werden. Da der Umgang mit einer doppelt-verketteten Liste aus Knoten vielleicht ungewohnt ist, soll eine Methode aus TM_Band ausgeführt werden [wobei ich für die Theorie nochmals auf meine zu Beginn des Abschnitts 1d angegebene Informatik-Seite e) verweise]. Nachfolgend wird erkennbar, wie bei Bedarf Knoten rechts oder links angefügt werden (und das Leerzeichen und die passende Nummerierung erhalten):
| public class TM_Band ... public void kopfBew (int um) // bewegt den Kopf um die angebene Felderzahl um auf dem Band { if (um > 0) { for (int i = 0; i < um; i++) { if (kopf.rechts == null) { kopf.rechts = new TM_Bandknoten (leerzeichen, kopf.index+1, kopf, null); } kopf = kopf.rechts; } } else if (um < 0) { for (int i = 0; i > um; i--) { if (kopf.links == null) { kopf.links = new TM_Bandknoten (leerzeichen, kopf.index-1, null, kopf); } kopf = kopf.links; } } } ... |
Die Zeiger liRand bzw. reRand (für den wirklich beschriebenen Teil es Bandes) werden dabei noch nicht verändert, weil neu angefügte Knoten ja nur das Leerzeichen enthalten. Erst wenn später ein anderes Zeichen als Inhalt in einen der jetzt erzeugten Knoten kommt, wird dann (in kopfSchreib) der Rand angepasst!
Aus der Turingmaschinen-Klasse TM_Maschine werden mehrere Methoden vorgestellt. Einmal soll gezeigt werden, wie die Fehlertexte einer Kontrollmethode aussehen können (und wie auch hier der Programmtext durch Aufruf weiterer Methoden übersichtlich gehalten wird):
| ... public class TM_Maschine ... private String kontrolleBandalphabet() // kontrolliert bandalphabet und nennt ggf. Fehler { String probleme = ""; if ((bandalphabet==null) || (bandalphabet.length<2)) { probleme = "!! Bandalphabet enthält weniger als 2 Zeichen !!\n"; } else if (!allesEinstellig(bandalphabet)) { probleme = "!! Bandalphabet enthält leere oder mehrstellige Zeichen !!\n"; } else if (!allesVerschieden(bandalphabet)) { probleme = "!! Bandalphabet enthält mehrfach gleiche Zeichen !!\n"; } return (probleme); } ... |
Zum anderen soll das Umfüllen der Einträge aus der ArrayList einträge in die dazu neu angelegte Maschinentafel vorgeführt werden. Es werden die richtigen Indizes x und y der 2-dimensionalen Tabelle in while-Schleifen gesucht. Sollte die Zuordnung nicht klappen, sollte besser noch die globale Variable meldung mit dem Fehlertext gefüllt werden (statt der jetzt auskommentierten Ausgabe des Fehlers nur auf die Konsole) oder sogar eine Exception geworfen werden:
| ... public void fülleMaschinentafel () // kopiert alle Einträge aus der Liste einträge in die Maschinentafel { int xmax = bandalphabet.length; int ymax = zustand.length-1; maschinentafel = new TM_Eintrag[xmax][ymax]; int x, y; for (y=0; y<ymax; y++) { for (x=0; x<xmax; x++) { maschinentafel[x][y] = null; } } Iterator itel = einträge.iterator(); TM_Eintrag e = new TM_Eintrag(); while (itel.hasNext()) { e = (TM_Eintrag) itel.next(); x = 0; while ((x < xmax) && !(e.altesZeichen.equals(bandalphabet[x]))) { x++; } // end of while y = 0; while ((y < ymax) && !(e.alterZustand.equals(zustand[y]))) { y++; } // end of while if ((x < xmax) && (y < ymax)) { maschinentafel[x][y] = e; } else { // System.out.println("** Problem: x="+x+", y="+y+": Eintrag passt nicht: "+e); } // end of if-else } } ... |
Zuletzt zeigen zwei weitere Methoden für die Turingmaschine die typischerweise doch nicht allzu anspruchsvolle Programmierung der Fähigkeiten:
| ... public void schreibeNeuesZeichen() // schreibt neu zu schreibendes Zeichen am Kopf aufs Band { char neu = maschinentafel[indexGelesenesZeichen()][indexAktZustand()].neuesZeichen.charAt(0); band.kopfSchreib(neu); } public int indexNeuerZustand() // nennt die Position vom neuen Zustand innerhalb der Reihung zustände { String neu = maschinentafel[indexGelesenesZeichen()][indexAktZustand()].neuerZustand; for (int i = 0; i < zustand.length; i++) { if (neu.equals(zustand[i])) { return (i); } } return (-1); } ... |
Man beachte, dass die lokalen Variablen neu in diesen beiden Methoden für Inhalte verschiedener Typen verwendet werden. Wird in der zweiten Methode der neue Zustand neu in der Reihung zustand aller Zustände gefunden, beendet das innere return (i) die Methode (und bricht damit die for-Schleife ab). Wird hingegen die for-Schleife wirklich bis zum Ende durchlaufen, wurde der neue Zustand nicht gefunden, hat also offenbar einen unzulässigen Namen bzw. ist ungültig. Das wird dann durch den negativen Rückgabewert -1 verdeutlicht.
zum Seitenanfang / zum Seitenende
zurück zur Startseite des
"Turingmaschinen-Projekts": allgemeine
Theorie der Turingmaschinen; Projektvorhaben
zurück zur vorigen Seite des "Turingmaschinen-Projekts":
Persistentes Speichern der
Turingmaschinen-Daten auf einem Datenträger und Öffnen
der Daten
weiter zur nächsten Seite des
"Turingmaschinen-Projekts":Realisation
der Benutzer-Oberfläche (GUI) der Simulation
zurück zum Anfang der Informatik-Hauptseite
direkt zur Übersicht aller
"Informatik-mit-Java"-Seiten auf der
Informatik-Hauptseite