Computability Theory

Abstract

This book is a development of class notes for a two-hour lecture including a two-hour lab held for second-year Bachelor students of Computer Science at the Hamburg University of Technology during the last few years. The course aims to present the basic results of computability theory, including well-known mathematical models of computability such as the Turing machine, the unlimited register machine (URM), and GOTO and LOOP programs, the principal classes of computational functions like the classes of primitive recursive, recursive, and partial recursive functions, the famous Ackermann function and the Ackermann class, the main theoretical concepts of computability such as Gödel numbering, universal functions, parametrization, Kleene’s normal form, Kleene’s recursion theorem, the theorems of Rice, undecidable and semidecidable (or recursively enumerable) sets, Hilbert’s tenth problem, and last but not least several important undecidable word problems including those for semi-Thue systems and semigroups. An added chapter provides a brief presentation of the central open question in complexity theory which is one of the millenium price problems in mathematics asking roughly whether each problem whose solution can be verified in polynomial time can also be solved in polynomial time. This chapter includes the well-known result of Stephen Cook and Leonid Lewin that the satisfiabilty problem is NP-complete and also its proof from scratch. The first appendix provides the reader with the necessary mathematical background on semigroups and monoids, notably free monoids and the presentation of monoids. The second appendix describes briefly the command-line program glu which has been developed for the interpretation of GOTO, LOOP and URM programs. This is a useful toolkit for making first steps to learn the programming of abstract computer models.