[176858]
Title: Computability Theory.
Written by: Karl-Heinz Zimmermann
in: July (2016).
Volume: Number:
on pages:
Chapter:
Editor:
Publisher: Hamburg University of Technology:
Series: 20150722-computability-theory-zimmermann.pdf
Address:
Edition: 6.
ISBN: 10.15480/882.1309
how published: 16-100 Zimm16 TUBdok
Organization:
School:
Institution:
Type:
DOI:
URL:
ARXIVID:
PMID:

[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 B achelor students of Computer Science at the Hamburg University of Technology during the last four years. The course aims to pr esent the basic results of computability theory, including mathematical models of computability, primitive recursive and parti al recursive functions, Ackermann's function, G&ouml;del numbering, universal functions, smn theorem, Kleene's normal form, un decidable sets, theorems of Rice, and word problems. The manuscript has partly grown out of notes taken by the author during h is studies at the University of Erlangen-Nuremberg.<br /> In the second edition, 2012, minor changes were made. In particular, the section on G&ouml;del numbering has been rewritten and a glossary of terms has been added. In the third edition, 2013, the eight chapters on computability theory were complement ed by a short introduction to computational complexity theory. The 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 pro blem whose solution can be verified in polynomial time can also be solved in polynomial time. The chapter includes the well-kn own result of Stephen Cook and Leonid Lewin that the satisfiabilty problem is NP-complete and also its proof from scratch. In the fourth and fifth editions, some small amendments have been make.