Elementare Berechenbarkeitstheorie
Springer Berlin (Verlag)
978-3-540-60667-3 (ISBN)
Daneben werden auch die klassischen Berechenbarkeitsmodelle betrachtet und die Gleichwertigkeit der Ansätze untereinander gezeigt. Darüber hinaus werden nicht-berechenbare Funktionen und unentscheidbare Probleme nachgewiesen. Als weiterführendes Thema wird die Unentscheidbarkeit der Prädikatenlogik und einiger Probleme aus dem Bereich der formalen Sprachen behandelt.
1 Einleitung.- Übersicht.- Mathematische Grundlagen.- 2 Registermaschinen.- 3 Berechenbare Funktionen.- 3.1 Programm-Makros.- 3.2 Weitere berechenbare Funktionen.- 4 Zeichenketten und Gödelnummern.- 5 Universelle Programme.- 5.1 Das Aufzählungstheorem.- 5.2 Rekursion.- 5.3 Indirekte Adressierung.- 6 Beschränkte und unbeschränkte Schleifen.- 6.1 For-berechenbare Funktionen.- 6.2 Nicht-for-berechenbare Funktionen.- 6.3 Die Kleenesche Normalform.- 7 Das Halteproblem und der Satz von Rice.- 7.1 Einführung: Das Halteproblem in Modula.- 7.2 Das Halteproblem der Registermaschine.- 7.3 Der Satz von Rice.- 8 Rekursive Funktionen.- 8.1 Primitiv-rekursive Funktionen.- 8.2 µ-rekursive Funktionen.- 9 Turhig-Maschinen.- 9.1 Grundlegende Definitionen.- 9.2 Äquivalenz von Tiring- und Registermaschinen.- 9.3 Allgemeine Tiring-Maschinen.- 10 Berechenbarkeit, Entscheidbarkeit, Aufzählbarkeit.- 10.1 Berechenbarkeit und die Churchsche These.- 10.2 Entscheidbarkeit.- 10.3 Semi-Entscheidbarkeit und Aufzählbarkeit.- 11 Das Postsche Korrespondenzproblem.- 12 Unentscheidbarkeit der Prädikatenlogik.- 13 Unentscheidbare Probleme in den formalen Sprachen.- 13.1 Kontextfreie Sprachen.- 13.2 Allgemeine Regelgrammatiken.- Literatur.
| Erscheint lt. Verlag | 30.4.1996 |
|---|---|
| Reihe/Serie | Springer-Lehrbuch |
| Zusatzinfo | X, 166 S. |
| Verlagsort | Berlin |
| Sprache | deutsch |
| Maße | 127 x 190 mm |
| Gewicht | 188 g |
| Themenwelt | Mathematik / Informatik ► Informatik |
| Mathematik / Informatik ► Mathematik ► Allgemeines / Lexika | |
| Schlagworte | Algorithm analysis and problem complexity • Algorithmen • Algorithmus • Berechenbarkeit • Berechenbarkeitstheorie • combinatorics • Entscheidbarkeit • formale Sprachen • Informatiker • Kontextfreie Sprache • Mathematische Logik • Modula • Prädikatenlogik • Programmiersprache • Registermaschine • Rekursion • Rekursive Funktion • Unentscheidbarkeit • Unlösbarkeit |
| ISBN-10 | 3-540-60667-X / 354060667X |
| ISBN-13 | 978-3-540-60667-3 / 9783540606673 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
