Enumerability · Decidability Computability - Hans Hermes

. .

Sommaire:
1. Introductory Reflections on Algorithms.- ? 1. The Concept of Algorithm.- ? 2. The Fundamental Concepts of the Theory of Constructivity.- ? 3. The Concept of Turing Machine as an Exact Mathematical Substitute for the Concept of Algorithm.- ? 4. Historical Remarks.- 2. Turing Machines.- ? 5. Definition of Turing Machines.- ? 6. Precise Definition of Constructive Concepts by means of Turing Machines.- ? 7. Combination of Turing Machines.- ? 8. Special Turing Machines.- ? 9. Examples of Turing-Computability and Turing-Decidability.- 3. ?-Recursive Functions.- ? 10. Primitive Recursive Functions.- ? 11. Primitive Recursive Predicates.- ? 12. The ?-Operator.- ? 13. Example of a Computable Function which is not Primitive Recursive.- ? 14. ?-Recursive Functions and Predicates.- 4. The Equivalence of Turing-Computability and ?-Recursiveness.- ? 15. Survey. Standard Turing-Computability.- ? 16. The Turing-Computability of ?-Recursive Functions.- ? 17. G?del Numbering of Turing Machines.- ? 18. The ?-Recursiveness of Turing-Computable Functions. Kleene's Normal Form.- 5. Recursive Functions.- ? 19. Definition of Recursive Functions.- ? 20. The Recursiveness of ?-Recursive Functions.- ? 21. The ?-Recursiveness of Recursive Functions.- 6. Undecidable Predicates.- ? 22. Simple Undecidable Predicates.- ? 23. The Unsolvability of the Word Problem for Semi-Thue Systems and Thue Systems.- ? 24. The Predicate Calculus.- ? 25. The Undecidability of the Predicate Calculus.- ? 26. The Incompleteness of the Predicate Calculus of the Second Order.- ? 27. The Undecidability and Incompleteness of Arithmetic.- 7. Miscellaneous.- ? 28. Enumerable Predicates.- ? 29. Arithmetical Predicates.- ? 30. Universal Turing Machines.- ? 31. ?-K-Definability.- ?32. The Minimal Logic of Fitch.- ? 33. Further Precise Mathematical Replacements of the Concept of Algorithm.- ? 34. Recursive Analysis.- Author and Subject Index.