TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publications
  4. Computability Theory
 
Options

Computability Theory

Citation Link: https://doi.org/10.15480/882.1401
Publikationstyp
Book
Date Issued
2017
Sprache
English
Author(s)
Zimmermann, Karl-Heinz  
Institut
Eingebettete Systeme E-13  
TORE-DOI
10.15480/882.1401
TORE-URI
http://tubdok.tub.tuhh.de/handle/11420/1404
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.
Subjects
computability theory
undecidability
theoretical computer science
recursion theory
DDC Class
620: Ingenieurwissenschaften
Lizenz
http://rightsstatements.org/vocab/InC/1.0/
Loading...
Thumbnail Image
Name

book.pdf

Size

990.29 KB

Format

Adobe PDF

TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback