ABOUT BOOK

Computability Theory deals with one of the most fundamental questions in computer science: What is computing and what are the limits of what a computer can compute? Or, formulated differently: ‰"What kind of problems can be algorithmically solved?‰" During the course this question will be studied. Firstly, the notion of algorithm or computing will be made precise by using the mathematical model of a Turing machine. Secondly, it will be shown that basic issues in computer science, like "Given a program P does it halt for any input x?" or "Given two program P and Q, are they equivalent?" cannot be solved by any Turing machine. This shows that there exist problems that are impossible to solve with a computer, the so-called "undecidable problems".