Textdokument
Aufzählbarkeitsklassen von Turingmaschinen und endlichen Automaten
Lade...
Volltext URI
Dokumententyp
Zusatzinformation
Datum
2004
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik
Zusammenfassung
Der Beitrag enthält eine Zusammenfassung der Dissertation n Structural Similarities of Finite Automata and Turing Machine Enumerability Classes. Die Dissertation [Ta03] eröffnet mit folgenden Worten: My Thesis: The enumerability and verboseness classes of finite automata on the one hand and of Turing machines on the other hand share numerous structural properties. They do not share these properties with intermediate resource-bounded computational models. Especially the finite automata versions of these classes have applications in areas unrelated to enumerability. Two methods that are used for the proofs of the structural similarities - elementary definitions of regular relations and branch diagonalisation - will be applicable to other proofs in automata, complexity, and recursion theory. Auf den folgenden 150 Seiten wird dann versucht, mittels etwa sechzig Sätzen, Korollaren und Lemmata diese These zu belegen und den Leser oder die Leserin von ihrer Richtigkeit zu überzeugen - nicht mehr und nicht weniger. Es wird sogar frech behauptet, man könne sich die weitere Lektüre der Arbeit sparen, sobald man von der {\tt>\hskip-.5e>}Thesis{\tt<\hskip-.5e<} überzeugt ist. Mein Hauptanliegen im vorliegenden Beitrag ist zu erläutern, was die obige These eigentlich genau besagt. Mathematische Exaktheit steht dabei weniger im Vordergrund als eine möglichst allgemein verständliche Darstellung der Ideen. Dazu werden zunächst die Konzepte wie Aufzählbarkeit oder Verboseness-Klassen genauer erklärt, dann die zentralen Resultate beschrieben, eine neue Beweismethode kurz angedeutet und zum Schluss Anwendungen skizziert. Die Konzepte 1.1 Turingmaschinen, endliche Automaten und Polynomialzeitmaschinen Schon der Titel der Dissertation verrät, dass es in ihr um Gemeinsamkeiten der beiden ältesten Maschinenmodelle der Informatik geht: Turingmaschinen und endliche Automaten. Grob gesprochen ist das Turingmaschinenmodell das mächtigste {\tt>\hskip-.5e>}sinnvolle{\tt<\hskip-.5e<} Maschinenmodell, das es gibt. {\tt>\hskip-.5e>}Mächtig{\tt<\hskip-.5e<} bedeutet hier, dass Turingmaschinen alles berechnen können, was sich überhaupt berechnen lässt. Da unklar ist, was die richtige Definition von {\tt>\hskip-.5e>}was sich überhaupt berechnen lässt{\tt<\hskip-.5e<} ist, ist es kein mathematischer Satz, dass Turingmaschinen allmächtig sind, sondern lediglich eine These, die aber der klangvollen Namen {\tt>\hskip-.5e>}Church'sche These{\tt<\hskip-.5e<} trägt. Praktisch kann man sich eine Turingmaschine als einen Rechner vorstellen, der über beliebig viel Speicher verfügt und der beliebig lange rechnen darf. Am anderen Ende des Spektrums der Maschinenmodelle finden sich die endlichen Automaten. Diese verarbeiten ihre Eingabe, indem sie sie einmal von links nach rechts lesen und am Ende sofort eine Ausgabe produzieren. Endliche Automaten benötigen keinerlei Speicher und ihre Rechenzeit ist proportional zur Eingabelänge. Vom praktischen Standpunkt aus sind Turingmaschinen viel zu mächtig, da sie Probleme spielend lösen können, die nachweislich nicht in vertretbarer Zeit (wie beispielsweise der zu erwartenden Lebensdauer des Universums) zu lösen sind. Endliche Automaten sind nicht mächtig genug, da sie manche Probleme nachweislich nicht lösen können, die ein Taschenrechner mit links löst. In der Komplexitätstheorie werden deshalb Modelle wie Polynomialzeitmaschinen betrachtet, die {\tt>\hskip-.5e>}in der Mitte liegen{\tt<\hskip-.5e<} und die die Fähigkeiten realer Computer realistischer modellieren.