Grundlagen
Automaten
Ein Automat ist eine gedachte Maschine, welche nach bestimmten, genau festgelegten Regeln arbeitet. Dabei dient ein Automat in erster Linie der Analyse und dem Beweis von verschiedensten Problemen.Der Automat besitzt dabei einen festen inneren Zustand. Bekommt er nun von außen eine Eingabe, so ergibt sich aus dem inneren Zustand und dem eingegebenen Zustand, ein neuer innerer Zustand. Anschließend kann der nächste Zyklus nach dem selben Schema durchlaufen werden. In der Regel sind diese Automatenalgorithmen folglich so konzipiert, das sich eine bestimmte Operation immer wieder wiederholt. Man unterscheidet grundlegend zwischen zwei Arten von Automaten.
Dies sind zum einen die deterministischen Automaten und zum anderen die nichtdeterministischen. Bei deterministischen Automaten ist es eindeutig definiert, welcher Zustand auf einen bestimmten inneren Zustand in Verbindung mit der Eingabe folgt. Bei nichtdeterministischen Automaten ist dies nicht sicher festgelegt, da bei ihnen der Zufall eine Rolle spielt. Deterministische Vorgänge liefern folglich unter gleichen Startbedingung, nach der gleichen Anzahl von Durchläufen stets das gleiche Ergebnis. Bei nichtdeterministischen Automaten ist das Ergebnis auch nach mehreren Durchläufen mit den gleiche Ausgangsparametern stets ungewiss.
Eine weitere Unterscheidung von Automaten besteht in ihrer Endlichkeit. Wie dieser Fakt bereits vermuten lässt, gibt es zum einen Endliche Automaten und zum anderen unendliche Automaten. Ein endlicher Automat liefert daraus folgend, aus bestimmten getätigten Aktionen/Eingaben, einen, durch seinen internen Algorithmus festgelegten Rückgabewert, seine Berechnung hat also nach einer gewissen Zeit ein festes Ergebnis und wird somit beendet. Dagegen besitzen unendliche Automaten diesen Abbruchpunkt nicht. Ihr Programmablauf kann unendlich wiederholt werden und es kommt nie zu einem Schlussergebnis sondern stets nur zur Berechnung eines neuen Zustandes.
Bei beiden nachfolgenden Simulationen handelt es sich nun um zelluläre Automaten. Zelluläre Automaten sind auf einer Fläche oder einem Raum von Zellen angesiedelt, wobei jede Zelle eine festgelegte Zahl von Nachbarzellen besitzt. Der Zustand der einzelnen Zellen zu einem bestimmten Durchlaufzyklus hängt nun von dem vorangegangenen Zustand der Nachbarzellen und dem internen Programm des Automaten, wie oben bereits angeführt, ab.
Turingengines
Turingmaschinen1 hängen eng mit der Automatentheorie zusammen. So handelt es sich bei ihnen um Automaten, welche lediglich die grundlegenden Funktionen Schreiben, Lesen und Schreibposition verschieben beherrschen. Nach ihrer Theorie sind sie auf einem (für die nötigen Berechnungen) unendlich langem Speicherband angesiedelt. Dabei beginnen sie mit einem Startwert auf dem Band und bewegen sich je nach Programmablauf entweder ein Feld zur einen Seite oder ein Feld zur anderen Seite weiter. Der Wert des Bandes an dieser Position wird nun erneut gelesen und der neue, aus dem inneren Zustand und dem Eingabewert ermittelte Wert auf das band geschrieben, wobei die Turingmaschine anschließend wieder ihre Schreibpostion verschiebt. Prinzipiell ist es so möglich, sämtliche Berechenbaren Probleme nach einer endlichen Zeit zu lösen.1 Von Alan Turing (1912 – 1954); britischer Mathematiker