Rekursive Funktionen und ihre Komplexität

Inhaltsverzeichnis

• 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.