Erstes Kapitel. Einführende Betrachtungen über Algorithmen.- § 1. Der Begriff des Algorithmus.- § 2. Die grundlegenden Begriffe der Theorie des Konstruktiven.- § 3. Turingmaschinen als Präzisierung des Begriffs eines Algorithmus.- § 4. Historische Bemerkungen.- Zweites Kapitel. Turingmaschinen.- § 5. Definition der Turingmaschinen.- § 6. Präzisierung konstruktiver Begriffe mittels Turingmaschinen. Beispiele.- § 7. Zusammensetzung von Turingmaschinen.- § 8. Spezielle Turingmaschinen.- § 9. Beispiele für Turing-Berechenbarkeit und Turing-Entscheidbarkeit.- Drittes Kapitel. ?-rekursive Funktionen.- § 10. Primitiv-rekursive Funktionen.- § 11. Primitiv-rekursive Prädikate.- § 12. Der ?-Operator.- § 13. Beispiel einer berechenbaren Funktion, die nicht primitiv-rekursiv ist.- § 14. ?-rekursive Funktionen und Prädikate.- Viertes Kapitel. Die Äquivalenz von Turing-Berechenbarkeit und ?-Rekursivität.- § 15. Übersicht. Normierte Turing-Berechenbarkeit.- § 16. Die Turing-Berechenbarkeit der ?-rekursiven Funktionen.- § 17. Gödelisierung von Turingmaschinen.- § 18. Die ?-Rekursivität der Turing-berechenbaren Funktionen. Die Kleenesche Normalform.- Fünftes Kapitel. Rekursive Funktionen.- § 19. Definition der rekursiven Funktionen.- § 20. Die Rekursivität der ?-rekursiven Funktionen.- § 21. Die ?-Rekursivität der rekursiven Funktionen.- Sechstes Kapitel. Unentscheidbare Prädikate.- § 22. Einfache unentscheidbare Prädikate.- § 23. Die Unlösbarkeit des Wortproblems für Semi-Thue-Systeme und Thue- Systeme.- § 24. Die Prädikatenlogik.- § 25. Die Unentscheidbarkeit der Prädikatenlogik.- § 26. Die Unvollständigkeit der Prädikatenlogik der zweiten Stufe.- § 27. Die Unentscheidbarkeit und die Unvollständigkeit der Arithmetik.- Siebentes Kapitel. Verschiedenes.- § 28. Aufzählbare Prädikate.- § 29. Arithmetische Prädikate.- § 30. Universelle Turingmaschinen.- § 31. ?-K-Definierbarkeit.- § 32. Die Minimallogik von Fitch.- § 33. Weitere Präzisierungen des Begriffs des Algorithmus.- § 34. Rekursive Analysis.- Namen- und Sachverzeichnis.

In der Mathematik ist es immer als eine besonders interessante und wichtige Aufgabe angesehen worden, Algorithmen zur Lösung von Pro­ blemen zu entwickeln. Dabei ist ein Algorithmus im Normalfall nur auf einen eng umschriebenen Problemkreis anwendbar, wie etwa der Euklidi­ sche Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier Zahlen oder das bekannte Verfahren, mit dessen Hilfe die Qua­ dratwurzeln aus natürlichen Zahlen in Dezimaldarstellung gewonnen werden können. So wichtig derartige spezielle Algorithmen auch sein mögen - so wäre es dennoch wünschenswert, über Algorithmen mit großer Tragweite zu verfügen. Um solche Algorithmen, die sich mög­ lichst vielfältig anwenden lassen, hat man sich jahrhundertelang ohne rechten Erfolg bemüht. Erst in der zweiten Hälfte des letzten Jahr­ hunderts wurde ein bemerkenswerter Fortschritt erzielt, als es gelang, mit der Prädikatenlogik einen wichtigen Teil der logischen Schluß­ prozesse in die Gestalt eines Kalküls zu bringen. (Dabei spielte die Boolesche Algebra eine wesentliche Pionierrolle. ) Man hätte nun viel­ leicht vermuten können, daß alle mathematischen Probleme algorith­ misch lösbar seien. Doch mahnten wohlbekannte noch ungelöste Pro­ bleme (etwa das Wortproblem der Gruppentheorie, oder das zehnte Hilbertsche Problem, das die Frage nach der Lösbarkeit von diophanti­ schen Gleichungen betrifft) zur Vorsicht. Immerhin war nun der Anstoß gegeben, die Frage nach dem Wesen des Algorithmus aufzuwerfen. Diese Frage hatte schon Leibniz gestellt, aber nicht zu lösen vermocht.