Institute of Embedded Systems

[BibTex]

Note: khzimmermann, AEG

Abstract: This book is a development of class notes for a two-hour lecture including a one-hour lab held for second-year Bachelor students of Computer Science at the Hamburg University of Technology during the last four years. The course aims to present the basic results of computability theory, including mathematical models of computability, 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 has partly grown out of notes taken by the author during his studies at the University of Erlangen-Nuremberg. The second edition contains minor changes. In particular, the section on Gödel numbering has been rewritten and a glossary of terms has been added.