Computability Theory

Cooper, Barry

Buchcover
Was können Computer berechnen? Wo gibt es Grenzen, Dinge die nicht mehr berechenbar sind? Was soll "Berechenbarkeit" überhaupt sein? Wieviel "Information" ist in einer Menge enthalten?

Dies sind nur einige der Fragestellungen, die als Leitgedanken und Motivation für Fragestellungen der Berechenbarkeits- oder Rekursionstheorie, einem Teilgebiet der Theoretischen Informatik, dienen. In dem vorliegenden Lehrbuch gibt der Autor einen umfassenden Überblick über diesen vielfältigen Bereich.
Im ersten Teil des Buches stellt er dabei Grundbegriffe der Theorie zusammen, inklusive einer recht ausführlichen Einleitung in die mathematische Logik, mit der die Berechenbarkeitstheorie etwa durch den Gödelschen Unvollständigkeitssatz eng verknüpft ist. Dieser Teil umfasst etwas mehr als das, was man in einer Einführungsvorlesung zur Theoretischen Informatik normalerweise über Berechenbarkeit lernt.
Der zweite Teil widmet sich der Einführung in Berechnungen mit Hilfe von Orakelmengen, der arithmetischen Hierarchie und stellt die sogenannte Aufzählbarkeitsreduktion vor.
Im dritten Teil greift der Autor verschiedene weiterführende Themenbereiche heraus, in die er jeweils einen Einblick zu geben versucht, etwa die rekursionstheoretische Version der Forcing-Methode und Anwendungen des mengentheoretischen Axioms der Determiniertheit.
Der Inhalt der 400 Seiten im Einzelnen ist:

Part I: Computability and Unsolvable Problems
1. Hilbert and the Origins of Computability Theory
2. Models of Computability and the Church-Turing Thesis
3. Language, Proof and Computable Functions
4. Coding, Self-Reference and the Universal Turing Machine
5. Enumerability and Computability
6. The Search for Natural Examples of Incomputable Sets
7. Comparing Computability and the Ubiquity of Creative Sets
8. Gödel's Incompleteness Theorem
9. Decidable and Undecidable Theories
Part II: Incomputability and Information Content
10. Computing with Oracles
11. Nondeterminism, Enumerations and Polynomial Bounds
Part III: More Advances Topics
12. Post's Problem: Immunity and Priority
13. Forcing and Category
14. Applications of Determinacy
15. The Computability of Theories
16. Computability and Structure

In der Auswahl und Behandlung der Themen ist Coopers Buch dabei bislang wohl einzigartig. Andere Bücher aus diesem Themenfeld sind üblicherweise entweder speziell an Einsteiger gerichtet und decken lediglich die Grundlagen der Berechenbarkeitstheorie ab, oder befassen sich mit einem enger umgrenzten Spezialthema. Cooper vereint beide Herangehensweisen, indem er sowohl auf die Grundlagen eingeht als auch fortgeschrittene Themen nicht abschließend, aber hinreichend ausführlich behandelt, um einen Einblick in die Fragestellungen und Techniken zu geben, um die es jeweils geht. Dabei versucht er meist, auch die Beweisideen klarzumachen, bevor er die formalen Details ausführt, was das Buch sehr gut lesbar macht.
Ausgezeichnet gefallen hat mir auch die Integration der Vielzahl von Übungsaufgaben in den Text. Diese stehen über die Kapitel verteilt jeweils direkt an der Stelle, an der sie sich inhaltlich einfügen und ermöglichen dadurch eine "aktivere" Lektüre.

Fazit: Das beste Buch im Bereich der Berechenbarkeitstheorie, das ich kenne, ist "Computability Theory" sowohl für Anfänger als auch für Fortgeschrittene, die einen Überblick bekommen wollen, geeignet.


Hinzugefügt am: 2009-04-07
Kritiker: Bilbo
Bewertung

Zugehöriger Link: Katalog amazon.de
Gelesen: 2537




Durchschnittsbewertung: 1 Bewertungen

Suchbegriffe : Berechenbarkeitstheorie :: Theoretische Informatik :: Rekursionstheorie :

Kommentar schreiben   Ein besseres Review schreiben

Weitere Kommentare:

Neuer Kommentar zu:
Computability Theory


Benutzername: Anonymous [ Mitglied werden ]


Bewertung: 1=schlechteste, 10=beste Bewertung

Kommentar:

Bitte eine Wertung, einen Kommentar oder beides abgeben.

Autoren: A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z    
Themengruppen:
Titelsuche:  
[Schreibe eine Buchbesprechung]
[Ein Buch, das hier besprochen sein sollte]
[Fragen? -> Forum Bücher & Links]

[Zum Index der Buchbesprechungen]

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]