Introduction to the Theory of Computation haben wir im Rahmen der letztsemestrigen Theoretischen Informatik Vorlesung als Grundlage verwendet, und zugegeben, ich habe es nicht komplett gelesen.

Von den Grundlagen wie Automatentheorie geht es die Chomsky-Hierarchie hoch bis zu den Turingmaschinen. Weiter zu verwandten Themen wie der Entscheidbarkeit (Church-Turing These, Hilberts Probleme, Halteproblem) und Reduzierbarkeit über zur Komplexitätstheorie. Das sind auch die Bereiche die ich gelesen habe, die fortgeschrittenen Themen habe ich dann weggelassen.

Das Buch ist wirklich sehr angehehm zu lesen, meistens war die Vorlesung (bei einem der drei Dozenten) sehr anspruchsvoll und man musste sich grosse Mühe geben, den Faden zwischen all den Definitionen, Beweisen und Sätzen nicht zu verlieren. Im Gegensatz dazu liest sich das Buch relativ ring. Auch ein Plus ist, dass es für einige Aufgaben auch Lösungen im Buch hat, das ist ja leider alles andere als selbstverständlich.

Fazit: Wem Computers Ltd. nicht gereicht hat und das Halteproblem verstanden hat, der sollte zu diesem nicht ganz billigen aber guten Buch greifen.