Computability and Decidability An Introduction for Students of Computer Science

The present Lecture Notes evolved from a course given at the Technische Hogeschool Eindhoven and later at the Technische Hogeschool Twente. They are intended for computer science students; more specifically, their goal is to introduce the notions of computability and decidability, and to prepare for the study of automata theory, formal language theory and the theory of computing. Except for a general mathematical background no preliminary knowledge is presupposed, but some experience in programming may be helpful. While classical treatises on computability and decidability are oriented towards the foundation of mathematics or mathematical logic, the present notes try to relate the subject to computer science. Therefore, the expose is based on the use of strings rather than on that of natural numbers; the notations are similar to those in use in automata theory; in addition, according to a common usage in formal language theory, most of the proofs of computability are reduced to the semi-formal description of a procedure the constructivity of which is apparent to anybody having some programming experience. Notwithstanding these facts the subject is treated with mathematical rigor; a great number of informal comments are inserted in order to allow a good intuitive understanding. I am indebted to all those who drew my attention to some errors and ambiguities in a preliminary version of these Notes. I want also to thank Miss L.A. Krukerink for her diligence in typing the manuscript.

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.