Automatentheorie Buchkatalog

Quelle: Wikipedia. Seiten: 54. Kapitel: Turingmaschine, Endlicher Automat, Kellerautomat, Zellulärer Automat, Nichtdeterministische Turingmaschine, Deterministischer endlicher Automat, Zweikellerautomat, Nichtdeterministischer endlicher Automat, Potenzmengenkonstruktion, Turingmaschine Typ 2, Transduktor, Büchi-Automat, Virtueller endlicher Automat, Alternierende Turingmaschine, Greibach-Normalform, Reguläre Sprache, Langton-Schleife, Moore-Automat, Wator, Lineare Sprache, Transitionssystem, AtoCC, Wireworld, O-Automat, Rekursiv aufzählbare Sprache, Mealy-Automat, Deterministisch kontextfreie Sprache, Zustandsübergangsdiagramm, Registermaschine, Gewichteter Automat, Symbolic Model Verifier, Staiger-Wagner-Automat, Rekursive Sprache, Ameise, Boolescher Differentialkalkül, Muller-Automat, Berry-Sethi-Verfahren, Bewertungsfunktion, Zweiwege-DFA, Rabin-Automat, Bisimulation, Transitionsrelation, Hilfskellermaschine, Äquivalenzproblem, Streett-Automat, Konfluenz, Dyck-Sprache, Linear beschränkte Turingmaschine, O-regulär, SPIN, Übergangstabelle, Akzeptor, Eindeutiger endlicher Automat, Kurodas Problem, Zustandsraum, Akzeptieren, Potenzautomat, Medwedew-Automat, PROMELA. Auszug: Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Theoretischen Informatik. Das Modell wurde im Rahmen des von David Hilbert im Jahr 1920 formulierten Hilbertprogramms, speziell zur Lösung des so genannten Entscheidungsproblems, in der Schrift "On Computable Numbers, with an Application to the Entscheidungsproblem" vorgestellt. Alan Turing beabsichtigte, mit der Turingmaschine ein Modell des mathematisch arbeitenden Menschen zu schaffen und damit eine mathematische Definition des Begriffs "Algorithmus" zu formulieren. Das von David Hilbert aufgestellte Entscheidungsproblem fragt, ob eine Formel der Prädikatenlogik allgemeingültig ist, also ob eine mathematische Aussage gültig ist oder nicht. Das von ihm vorgeschlagene Hilbertprogramm versuchte, dieses Problem automatisch zu lösen. Die Methode, die für eine prädikatenlogische Formel bestimmt, ob sie allgemeingültig ist, soll also von einer "Maschine" durchgeführt werden können. Vor der Erfindung des Computers bedeutete dies, dass ein Mensch nach festen Regeln - einem Algorithmus - eine Berechnung durchführt. Turing gelang es durch seine Turingmaschine, die Begriffe des Algorithmus und des automatischen Entscheidens mathematisch zu definieren. Diese Definition - eine Funktion ist genau dann berechenbar, wenn sie durch eine Turingmaschine berechenbar ist - wird durch die Church-Turing-These untermauert. So kann man beweisen, dass eine Turingmaschine alle Funktionen berechnen kann, die von anderen theoretischen Maschinenmodellen (wie zum Beispiel dem Lambda-Kalkül) oder heutigen Computern berechnet werden können. Nach der Church-Turing-These folgt, dass es auch zukünftig keine Maschinenmodelle geben wird, die mehr Funktionen als eine Turingmaschine berechnen können. Das Besondere an einer Turingmaschine ist dabei ihre strukturelle Einfachheit. Sie benötigt nur drei Operation