Ebook: Elementare Berechenbarkeitstheorie

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.

---

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.

---

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.
Content:
Front Matter....Pages I-X
Einleitung....Pages 1-7
Registermaschinen....Pages 9-16
Berechenbare Funktionen....Pages 17-30
Zeichenketten und G?delnummern....Pages 31-37
Universelle Programme....Pages 39-51
Beschr?nkte und unbeschr?nkte Schleifen....Pages 53-66
Das Halteproblem und der Satz von Rice....Pages 67-76
Rekursive Funktionen....Pages 77-95
Turing-Maschinen....Pages 97-111
Berechenbarkeit, Entscheidbarkeit, Aufz?hlbarkeit....Pages 113-129
Das Postsche Korrespondenzproblem....Pages 131-139
Unentscheidbarkeit der Pr?dikatenlogik....Pages 141-147
Unentscheidbare Probleme in den formalen Sprachen....Pages 149-159
Back Matter....Pages 161-166

---

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.
Content:
Front Matter....Pages I-X
Einleitung....Pages 1-7
Registermaschinen....Pages 9-16
Berechenbare Funktionen....Pages 17-30
Zeichenketten und G?delnummern....Pages 31-37
Universelle Programme....Pages 39-51
Beschr?nkte und unbeschr?nkte Schleifen....Pages 53-66
Das Halteproblem und der Satz von Rice....Pages 67-76
Rekursive Funktionen....Pages 77-95
Turing-Maschinen....Pages 97-111
Berechenbarkeit, Entscheidbarkeit, Aufz?hlbarkeit....Pages 113-129
Das Postsche Korrespondenzproblem....Pages 131-139
Unentscheidbarkeit der Pr?dikatenlogik....Pages 141-147
Unentscheidbare Probleme in den formalen Sprachen....Pages 149-159
Back Matter....Pages 161-166
....