> Details

Zimmermann, Karl-Heinz [Author] ; Technische Universität Hamburg-Harburg Institut für Rechnertechnologie, Technische Universität Hamburg-Harburg

Computability theory - [3. ed., Elektronische Ressource]

Reference
management

Bookmarks

Remove from
bookmarks

Share this on Whatsapp

Close

Bookmarks



You can manage bookmarks using lists, please log in to your user account for this.
  • Media type: E-Book
  • Title: Computability theory
  • Contributor: Zimmermann, Karl-Heinz [Author]
  • Corporation: Technische Universität Hamburg-Harburg, Institut für Rechnertechnologie ; Technische Universität Hamburg-Harburg
  • imprint: Hamburg: Univ. of Technology, 2013
  • Issue: 3. ed., [Elektronische Ressource]
  • Extent: Online-Ressource (PDF-Datei: 128 S., 758 KB); graph. Darst
  • Language: English
  • Identifier:
  • Keywords: Berechenbarkeit > Theoretische Informatik > Algebraische Rekursionstheorie > Rekursionstheorie > Unentscheidbarkeit > Berechnungstheorie > Komplexitätstheorie
  • Origination:
  • Footnote: Systemvoraussetzungen: Internet-Zugriff, Adobe Acrobat Reader
  • Description: Das Buch gibt eine kurze Einführung in die Theorie der Berechenbarkeit.

    Why do we need a formalization of the notion of algorithm or effective computation? In order to show that a specific problem is algorithmically solvable, it is sufficient to provide an algorithm that solves it in a sufficiently precise manner. However, in order to prove that a problem is in principle not solvableby an algorithm, a rigorous formalism is necessary that allows mathematical proofs. The need for such a formalism became apparent in the studies of David Hilbert (1900) on the foundations of mathematics and Kurt Gödel (1931) on the incompleteness of elementary arithmetic. The first investigations in the field were conducted by the logicians Alonzo Church, Stephen Kleene, Emil Post, and Alan Turing in the early 1930s. They have provided the foundation of computability theory as a branch of theoretical computer science. The fundamental results established Turing computability as the correct formalization of the informal idea of effective calculation. The results have led to Church’s thesis stating that ”everything computable is computable by a Turing machine”. The theory of computability has grown rapidly from its beginning.Its questions and methods are penetrating many other mathematical disciplines. Today, computability theory provides an important theoretical background for logicians, pure mathematicians, and computer scientists. Many mathematical problems are known to be undecidable such as the word problem for groups, the halting problem, and Hilbert’s tenth problem. 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 two 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. I would like to thank again my teachers Martin Becker and Volker Strehl for giving inspiring lectures in this field. In the second edition, 2012, minor changes were made. In particular, the section on Gö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 complemented 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 problem whose solution can be verified in polynomial time can also be solved in polynomial time. The chapter includes the well-known result of Stephen Cook and Leonid Lewin that the satisfiabilty problem is NP-complete and also its proof rom scratch. Finally, I would like to express my thanks to Ralf Möller for valuable comments. I am also grateful to Mahwish Saleemi for conducting the labs and Wolfgang Brandt for valuable technical support. Moreover, I would like to thank my students for their attention, their stimulating questions, and their dedicated work
  • Access State: Open Access