Book on Computability Theory

License
In terms of citation, please refer to
URN: urn:nbn:de:gbv:830-tubdok-11072
URL: http://doku.b.tu-harburg.de/volltexte/2011/1107/


Preface

Why do we need a formalization of the notion of algorithm or effective computation? In order to show that a specific problem is algorithmically solvable, it is sufficient to provide an algorithm that solves it in a sufficiently precise manner. However, in order to prove that a problem is in principle not solvable by an algorithm, a rigorous formalism is necessary that allows mathematical proofs. The need for such a formalism became apparent in the works of David Hilbert (1900) on the foundations of mathematics and Kurt Gödel (1931) on the incompleteness of elementary arithmetic.

The first investigations in the field were conducted by the logicians Alonzo Church, Stephen Kleene, Emil Post, and Alan Turing in the early 1930s. They provided the foundation of computability theory as a branch of theoretical computer science. The fundamental results established Turing computability as the correct formalization of the informal idea of effective calculation. The results led to Church’s thesis stating that ”everything computable is computable by a Turing machine”. The theory of computability has grown rapidly from its beginning. Its questions and methods are penetrating many other mathematical disciplines. Today, computability theory provides an important theoretical background for logicians and computer scientists. Many mathematical problems are known to be undecidable such as the word problem for groups, the halting problem, and Hilbert’s tenth problem.

This book is a development of class notes for a two-hour lecture including a one-hour lab held for Bachelor students of Computer Science at the Hamburg University of Technology in the summer term 2011. The aim of the course was to present the basic results of computability theory, including mathematical models of computability (Turing machine, unlimited register machine, and LOOP and GOTO programs), primitive recursive and partial recursive functions, Ackermann’s function, Gödel numbering, universal functions, smn theorem, Kleene’s normal form, undecidable sets, theorems of Rice, and word problems. The manuscript partly follows the notes taken by the author during his studies at the University of Erlangen-Nuremberg. I would like thank again my teachers Martin Becker† and Volker Strehl for giving inspiring lectures in this field.

First of all, I would like to express my thanks to my colleague Ralf Möller for valuable comments. I am also grateful to my PhD student Mahwish Saleemi for conducting the lab and to our technical engineer Wolfgang Brandt for valuable technical support. Finally, I thank my students for their attention, their stimulating questions, and their dedicated work.