Computability and Decidability

1: Sets and Functions.- 1.1. The objects.- 1.2. Ordered sequences and sets.- 1.3. Further notations and definitions concerning sets.- 1.4. Functions.- 1.5. Particular objects.- 2: Sets and Functions of Strings.- 2.1. Definitions.- 2.2. String functions.- 2.3. Further notations and definitions.- 2.4. The interpretation of strings.- 2.5. Alphabetic order.- 2.6. Enumeration of strings and n-tuples of strings.- 2.7. Enumeration functions.- 2.8. Calculating the value of the enumeration functions.- 3: Computable Functions.- 3.1. Historical background.- 3.2. The basic idea of Turing.- 3.3. Physical model.- 3.4. Formal definition of a Turing machine.- 3.5. Examples of Turing machines.- 3.6. Computable functions.- 3.7. The thesis of Turing.- 3.8. Normal Turing machines.- 4: The Universal Turing Machine.- 4.1. The string description of a Turing machine.- 4.2. The universal Turing machine.- 4.3. Discussion.- 5: Some Functions Which are Not Computable.- 5.1. The halting problem.- 5.2. The blank tape halting problem.- 5.3. The uniform halting problem.- 5.4. The equivalence problem.- 5.5. General remark.- 6: Effectively Enumerable and Decidable Sets.- 6.1. Introduction.- 6.2. Definitions.- 6.3. Effectively enumerable sets and the domain of computable functions.- 6.4. Effectively enumerable sets and the range of total computable functions.- 6.5. A set which is not effectively enumerable.- 6.6. Decidable sets versus effectively enumerable sets.- 6.7. An effectively enumerable set which is not decidable.- 6.8. Some informal comments.- Appendix 1: Bibliographical Notes.- Appendix 2: List of the Most Important Notations.- Appendix 3: List of the Most Important Concepts.