Dieses Buch entstand aus Vorlesungen, die ich in den lahren 1970 bis 1973 an den Universitiiten Saarbriicken, Erlangen-Niirnberg und Frankfurt gehalten habe. Das Ziel des Buches ist es, die Grundlagen der Berechenbarkeit und des Rechen aufWandes auf der Basis abstrakter Maschinenmodelle aufzubauen, wobei beim Be griff Maschine stets eine sequentielle Arbeitsweise vorausgesetzt wird. Die Theorie der rekursiven Funktionen wird mittels Begriffsbildungen der Informatik wie Pro gramm, Maschine und Simulation entwickelt; dieser Aufbau wird jedoch hinreichend breit angelegt und nicht nur an ein spezielles Maschinenmodell wie z. B. die Turing maschine gekniipft. Die systematische Entwicklung der Begriffe Simulation und GOdelisierung gestattet es, die Aquivalenzbeweise ftir die Klassen der turingberechen baren, registerberechenbaren und rekursiven Funktionen detailliert und, wie ich glaube, in iibersichtlicher Form darzustellen. Bei der Stoffauswahl habe ich nur solche Gebiete beriicksichtigt, die heute in ihren Grundziigen bereits voll entwickelt sind und in systematischer Form dargestellt werden konnen. Aus diesem Grund habe ich auf die fUr die Informatik besonders interessanten Fragen des Berechnungsaufwandes bei konkreten Problemen verzichtet. Dieses Gebiet, das ebenso wie die Theorie der Berechnungen iiber endliche Bereiche in einer stiirmischen Entwicklung begriffen ist, habe ich zukiinftigen Darstellungen iiberlassen.

Inhalt

0. Grundbegriffe und Bezeichnungen.- 1. Der Begriff des Algorithmus.- 2. Maschinen, Programme und berechenbare Funktionen.- 3. Rekursive Funktionen.- 4. Rekursive Aufzählungen.- 5. Das Rekursionstheorem und Anwendungen.- 6. Unentscheidbare Prädikate.- 7. Subrekursive Funktionenklassen.- 8. Rechenzeit und effiziente Berechnungsmodelle.- 9. Maschinenunabhängige Komplexitätstheorie.- 10. Ausblick auf aktuelle Fragen der Forschung.