Elementare Berechenbarkeitstheorie
Buch in deiner Nähe kaufen
Beschreibung
Das Buch führt in leicht verständlicher und dennoch präziser Form in die Grundlagen der Berechenbarkeitstheorie ein. Es richtet sich insbesondere an Informatikstudenten, ist aber für alle geeignet, die an den Grundlagen und Grenzen der algorithmischen Berechenbarkeit interessiert sind. Vom Leser wird nur eine gewisse Vertrautheit mit formaler Argumentation erwartet.
Der Darstellung liegt das Modell der Registermaschine zugrunde, das dem Umgang mit realen Computern und Programmiersprachen entlehnt ist und daher der Denkweise der Informatik besonders entgegenkommt. Daneben werden auch die klassischen Berechenbarkeitsmodelle Turingmaschine und µ-rekursive Funktionen betrachtet und die Gleichwertigkeit der Ansätze untereinander gezeigt.
Im Anschluß an die systematische Entwicklung des Begriffs der berechenbaren Funktion (und parallel dazu einer geeigneten Programmiersprache) werden nicht-berechenbare Funktionen und unentscheidbare Probleme nachgewiesen, wie etwa das grundlegende Halteproblem für Computerprogramme.
Als weiterführender Themenbereich wird die Unentscheidbarkeit der Prädikatenlogik behandelt sowie einiger Probleme aus dem Gebiet der formalen Sprachen, die im Compilerbau eine wichtige Rolle spielen.
Die Beschäftigung mit den Grundprinzipien und Grenzen der Berechenbarkeit ist für die Informatik von zentraler Bedeutung. Um dieses Verständnis zu vermitteln, werden in diesem Buch Ansätze vorgestellt, die dem Umgang mit realen Computern und Programmiersprachen entlehnt sind. Es werden vor allem Registermaschinen und eine einfach while-basierte Programmiersprache verwendet.
Diese kompakte, an den entscheidenden Punkten aber ausführliche Einführung setzt nur elementare mathematische Kenntnisse voraus. Erfahrungen mit einer konventionellen Programmiersprache wie Pascal oder Modula erleichtern das Verständnis, sind aber nicht unbedingt erforderlich.
Autor*in
Einar Smith
Themen in »Elementare Berechenbarkeitstheorie«
Algorithmen Algorithmus Berechenbarkeit Berechenbarkeitstheorie Entscheidbarkeit Kontextfreie Sprache Modula Programmiersprache Prädikatenlogik Registermaschine Rekursion Unentscheidbarkeit Unlösbarkeit rekursive Funktion algorithm analysis and problem complexity