Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.1401
Fulltext available Open Access
Title: Computability Theory
Language: English
Authors: Zimmermann, Karl-Heinz 
Keywords: computability theory;undecidability;theoretical computer science;recursion theory
Issue Date: 2017
Abstract (english): 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
DOI: 10.15480/882.1401
Institute: Eingebettete Systeme E-13 
Type: Buch (Monographie)
License: In Copyright In Copyright
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
book.pdf990,29 kBAdobe PDFThumbnail
View/Open
Show full item record

Page view(s)

417
Last Week
0
Last month
13
checked on Sep 25, 2020

Download(s)

458
checked on Sep 25, 2020

Google ScholarTM

Check

Note about this record

Export

Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.