Bewertung:
Derzeit gibt es keine Leserbewertungen. Die Bewertung basiert auf 2 Stimmen.
A Mathematical Primer on Computability
Das Buch bietet eine in sich geschlossene Einführung in die Berechenbarkeitstheorie für fortgeschrittene Studenten der Mathematik und Informatik im Grund- oder Hauptstudium. Das technische Material wird durch zahlreiche Beispiele, Probleme mit vollständig ausgearbeiteten Lösungen sowie eine Reihe von Übungsvorschlägen illustriert.
Teil I befasst sich mit den grundlegenden Begriffen und Ergebnissen der Berechenbarkeit, beginnend mit den Grundbegriffen Computermodell (eine abstrakte Programmiersprache auf hoher Ebene), berechenbare Funktion, entscheidbare und auflistbare Menge, geeignete universelle Funktion, Entscheidungsproblem und Reduktionstechnik zur Übertragung von Eigenschaften der Entscheidbarkeit und Auflistbarkeit. Die wesentlichen Ergebnisse, nämlich Rice's Theorem, Rice-Shapiro's Theorem, Rice-Shapiro-McNaughton-Myhill's Theorem sowie Rogers' Theorem und das Rekursionstheorem werden vorgestellt und illustriert. Viele-zu-eins-Reduzierbarkeit und viele-zu-eins-Grade werden untersucht. Eine kurze Einführung in das Rechnen mit Orakeln ist ebenfalls enthalten. Es werden sowohl berechenbare als auch nicht berechenbare Operatoren sowie monotone und finite Operatoren eingeführt. Die Beziehung zwischen ihnen wird diskutiert, insbesondere über den Satz von Myhill-Shepherdson. Kleene's Least Fixed Point Theorem wird ebenfalls vorgestellt. Schließlich endet Teil I mit einer kurzen Erläuterung des Turing-Rechenmodells, der Turing-Reduzierbarkeit und der Turing-Grade.
Teil II des Buches konzentriert sich auf Anwendungen der Berechenbarkeit in verschiedenen Bereichen, nämlich in der Logik (Unentscheidbarkeit der Arithmetik, Erfüllbarkeit in der Aussagenlogik, Entscheidbarkeit in der Modallogik), der euklidischen Geometrie, Graphen und der Kolmogorov-Komplexität. Dennoch sind keine Vorkenntnisse in diesen Bereichen erforderlich. Die wesentlichen Details zum Verständnis der Anwendungen werden vermittelt.
| ISBN: | 9781848902961 |
| Autor: | |
| Verlag: | |
| Sprache: | Englisch |
| Einband: | Taschenbuch |
Derzeit verfügbar, auf Lager.
