Hermes Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit

Einführung in die Theorie der Rekursiven Funktionen
Erscheinungsjahr 2013
ISBN: 978-3-662-01462-2
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, Band 109, eBook

Reihe: Grundlehren der mathematischen Wissenschaften

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.

Zielgruppe

Research

Autoren/Hrsg.

Hermes, Hans

Inhaltsverzeichnis

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.