Computability Theory

Karl-Heinz Zimmermann
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...