Aufzhlbarkeit Entscheidbarkeit Berechenbarkeit: Einfhrung in die Theorie der r [Paperback]

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. Dal3ì