Kara – Programmieren mit endlichen Automaten
Kara für Profis!
Es ist erstaunlich, welche Aufgaben mit endlichen Automaten gelöst werden können. Eine kleine Auswahl von solchen Aufgaben finden Sie hier.
|
Kara besucht jedes Labyrinth vollständig! Ein Beitrag vonHorst Müller, Institut für Informatik, Universität Erlangen. |
||
Kann Kara einen beliebigen zusammenhängenden Raum vollständig besuchen und jedes Feld mit einem Kleeblatt belegen? Kara kann sich keine "Landkarte" der Welt aufbauen, um sich so zu merken, wo er schon war oder wo es Bäume hat.
Obwohl Kara nur seine unmittelbare Umgebung wahrnimmt, kann er diese Aufgabe lösen. Horst Müller bewies 1977 in "A One-Symbol Printing Automaton Escaping from every labyrinth", Computing, Band 19, pages 95-110, 1977, dass ein endlicher Automat beliebige Labyrinthe vollständig besuchen kann. Eine verbesserte Version findet sich in Horst Müller, "Improvements on Printing Mice in Labyrinths", Computing, Band 47, pages 235-246, 1992. Das Unterfangen ist allerdings aufwendig: der von Horst Müller definierte endliche Automat für diese Aufgabe umfasst 7968 Zustände. Kara darf im Vergleich zu "normalen" endlichen Automaten pro Zustandsübergang mehr Befehle ausführen, so dass ein Kara-Automat mit weniger Zuständen auskommen würde. Horst Müller schätzt die benötigte Anzahl Zustände trotzdem noch auf mehrere Hundert...
Weitere Informationen von Horst Müller:
|
|
Kara, die Ameise |
||
Aus der Mathematik sind Beispiele von einfachen Iterationen bekannt, die komplexes Verhalten aufweisen.
Das wohl berühmteste Beispiel ist das Apfelmännchen.
Es gibt auch einfache endliche Automaten, die ein sehr komplexes Verhalten aufweisen. Ein Beispiel sind Christopher Langton's Ameisen (Spektrum der Wissenschaften, August 1995).
Die Langton-Ameise kann mit Kara einfach simuliert werden. Steht Kara auf einem Feld ohne Kleeblatt, so legt er ein Kleeblatt und geht auf das Feld rechts; steht Kara auf einem Feld mit Kleeblatt, so nimmt er es auf und geht auf das Feld links. Die Abbildung links zeigt das entsprechende Kara-Programm.
Quellen:
|
|
Kara, der fleissige Biber |
||
|
Was ist mit einer Turing-Maschine berechenbar bzw. entscheidbar und was nicht?
Das Standard-Beispiel eines nicht entscheidbaren Problems ist das Halte-Problem:
eine Turing-Maschine soll entscheiden, ob eine andere Turing-Maschine
je anhält oder nicht.
Von Tibor Rado (1962) stammt ein Beispiel einer einfachen nicht-berechenbaren Funktion. Für eine gegebene Anzahl n betrachtet man Turing-Maschinen mit n Zuständen (Stopzustand wird dabei nicht gezählt), die beginnend auf einem leeren Band irgendwann anhalten. Die Funktion S(n) soll die maximale Anzahl Markierungen (nicht notwendigerweise zusammenhängend) bestimmen, die eine Turing-Maschine mit n Zuständen auf dem Band hinterlassen kann, bevor sie anhält. Solche Turing-Maschinen werden "fleissige Biber" genannt. Die Funktion ist zwar wohldefiniert, aber schon für kleine n (ab 5, 6, ...) ist der Wert von S(n) nicht bekannt. Der fleissige Biber mit 4 Zuständen hinterlässt 13 Markierungen auf dem Band. Heiner Marxen zeigte, dass der fleissige Biber mit 5 Zuständen mindestens 4098 Markierungen auf dem Band und der fleissige Biber mit 6 Zuständen mindestens 1.29*10865 Markierungen hinterlässt. In Dewdney's "Der Turing Omnibus" wird ein Resultat von M. W. Green von 1964 zitiert, das eindrücklich zeigt, was "unberechenbar" bei diesem Beispiel heisst: Für jede berechenbare Funktion f gilt für alle Werte von n: f(S(n)) < S(n+1). Das heisst, S(n) wächst schneller als jede berechenbare Funktion!
Quellen:
|
