Computability and Decidability : An Introduction for Students of Computer Science

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.