Elementare Berechenbarkeitstheorie

Die Beschäftigung mit den Grundprinzipien und Grenzen der Berechenbarkeit ist für die Informatik von zentraler Bedeutung. Um dieses Verständnis zu vermitteln, werden in diesem Buch Ansätze vorgestellt, die dem Umgang mit realen Computern und Programmiersprachen entlehnt sind. Es werden vor allem Registermaschinen und eine einfach while-basierte Programmiersprache verwendet. Diese kompakte, an den entscheidenden Punkten aber ausführliche Einführung setzt nur elementare mathematische Kenntnisse voraus. Erfahrungen mit einer konventionellen Programmiersprache wie Pascal oder Modula erleichtern das Verständnis, sind aber nicht unbedingt erforderlich.

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.