Hans HermesAufzählbarkeit Entscheidbarkeit Berechenbarkeit
Einführung in die Theorie der rekursiven Funktionen
Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.
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 Unvoll ständigkeit der Arithmetik.- SiebentesKapitel. Verschiedenes.- 28. Aufzählbare Prädikate.- 29. Arithmetische Prädikate.- 30. Universelle Turingmaschinen.- 31. ?-K-Definierbarkeit.- 32. Die Minimallogik von Fitch.- 33. Aufzählbare Mengen über beliebigen Alphabeten. Chomsky-Sprachen.- 34. Das Korrespondenzproblem von Post.- 35. Weitere Präzisierungen des Begriffs des Algorithmus.- 36. Rekursive Analysis.- Namen- und Sachverzeichnis.
