Titel: Computability Theory
Sprache: Englisch
Autor/Autorin: Zimmermann, Karl-Heinz
Schlagwörter: computability theory;undecidability;theoretical computer science;recursion theory
Erscheinungsdatum: 2017
Zusammenfassung (englisch): 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.
URI: http://tubdok.tub.tuhh.de/handle/11420/1404
URN: urn:nbn:de:gbv:830-88216409
DOI: 10.15480/882.1401
Institut: Eingebettete Systeme E-13
Dokumenttyp: Buch (Monographie)
Enthalten in den Sammlungen:tub.dok

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
book.pdf990,29 kBAdobe PDFMiniaturbild

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.