Inhalt

1. Einleitung.- 2. Konstruieren mit Baukästen.- 3. Handrechenmaschinen.- 4. Abstraktion von der Handrechenmaschine zu einer idealen Registermaschine (RM).- 5. RM-Berechenbarkeit.- 6. Unterprogramme für Registermaschinen.- 7. Verzweigung von Programmen.- 8. Primitiv-rekursive Funktionen.- 9. Primitiv-rekursive Prädikate.- 10. Die RM-Berechenbarkeit der primitiv-rekursiven Funktionen.- 11. Die Rekursivität der RM-berechenbaren Funktionen.- 12. Universelle Funktionen.- 13. Die Unentscheidbarkeit des Stop-Problems für RM.- 14. Rekursiv-aufzählbare Prädikate.- 15. Kompliziertheitsmaße für Funktionen.- 16. Charakterisierung der primitiv-rekursiven Funktionen.- 17. Kleine universelle Registermaschinen.- 18. Worterzeugende Kalküle.- 19. Induktive Definitionen und Beweise.- 20. Wortverarbeitende Kalküle.- 21. Wortalgorithmen.- 22. Unentscheidbare Wortprobleme.- 23. Legespiele.- 24. Netzwerke von Automaten.- Lösung der Übungsaufgaben.- Literatur.- Namen- und Sachverzeichnis.