Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.1012
Fulltext available Open Access
Title: Computability theory
Language: English
Authors: Zimmermann, Karl-Heinz 
Keywords: computability theory;undecidability;theoretical computer science;recursion theory
Issue Date: 2011
Abstract (english): 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 solvable by an algorithm, a rigorous formalism is necessary that allows mathematical proofs. The need for such a formalism became apparent in the works 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 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 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 and computer scientists. Many mathematical problems are known to be undecidable such as the word problem for groups and semigroups, the halting problem, and Hilbert’s tenth problem.
URI: http://tubdok.tub.tuhh.de/handle/11420/1014
DOI: 10.15480/882.1012
Institute: Rechnertechnologie E-13 
Type: Buch (Monographie)
License: http://doku.b.tu-harburg.de/doku/lic_ohne_pod.php
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
fullbook.pdf4,32 MBAdobe PDFThumbnail
View/Open
Show full item record

Page view(s)

572
Last Week
7
Last month
7
checked on Sep 21, 2020

Download(s)

717
checked on Sep 21, 2020

Google ScholarTM

Check

Note about this record

Export

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