Einar Smith, der Autor des zu besprechenden Buches, hat 1989 seine Dissertation zum Thema ,,Zur Bedeutung der Concurrency-Theorie für den Aufbau hochverteilter Systeme`` hier am Fachbereich Informatik geschrieben. Ein alter Bekannter also, dessen neu erschienenes Buch aber nicht nur deshalb die Neugier weckt.
Der Autor wählt nämlich für die Einführung in die Theorie der Berechenbarkeit einen etwas unüblichen Weg, indem er nicht zuerst Turingmaschinen definiert, sondern als Hauptmodell die sogenannten Registermaschinen vorschlägt. Diese ähneln in ihrem Aufbau am ehesten Zählerautomaten, werden aber durch geschickte Notation auf die Ebene von RAMs gehoben und kommen so realen - wenn auch sehr primitiven - Computern nahe.
Da Vorwissen über die Programmierung realer Rechner wohl bei fast allen Lesern vorauszusetzen ist, gelingt so die Einführung kürzer und intuitiver. Insbesondere werden die eingesetzten Algorithmen leichter verständlich, denn sie lassen sich ohne große Probleme in jede prozedurale Sprache übersetzen. Nicht zuletzt wird auch die Praxisrelevanz des Themas deutlicher, auch wenn es überwiegend dem Leser überlassen bleibt, hier Bezüge herzustellen.
Obwohl die Einführung den historisch gewachsenen Weg verläßt, so sind doch fast alle Standardthemen präsent und auch formal exakt ausgeführt: Turing-Maschinen, universelle Programme, Probleme der Kodierung, rekursive Funktionen (ja, mit Ackermann-Funktion), das Halteproblem und dessen Unentscheidbarkeit, der Satz von Rice, die Churchsche These, das Postsche Korrespondenzproblem, die Prädikatenlogik und auch die Theorie formaler Sprachen. Daß das 10. Hilbertsche Problem nicht erwähnt wird, ist bei der angestrebten Kürze verständlich. Ich vermisse allerdings doch die Busy-Beaver-Funktion und ganz besonders eine Erwähnung des -Kalküls.
Hier fehlt zumindest ein Verweis auf die Literatur (etwa Hindley/Seldin: ,,Introduction to Combinators and -Calculus``), um dem Interessierten ein vertiefendes Studium zu ermöglichen. Ohnehin ist die Bibliographie für ein Einführungswerk etwas zu kurz geraten. Sie enthält fast ausschließlich andere Überblickswerke, allerdings auch solche aktuellen Datums, so daß der Leser dort weitere Literaturhinweise finden wird. Die Kürze der Bibliographie ist charakteristisch für das ganze Buch: Es ist kompakt und zwar so kompakt, daß es trotz seines handlichen Format lange dauert, es komplett durchzuarbeiten.
Dies gilt insbesondere, wenn man die Beweise mitliest, denn
diese gehen weit über das hinaus, was beispielsweise
in einer Kerngebietsprüfung zur theoretischen Informatik
verlangt wird, und ermöglichen dem Leser auf diese Weise
ein vertieftes Verständnis. In Verbindung mit der
Redundanzfreiheit des Buches fordert solche Präzision
jedoch ihren Tribut. Glücklicherweise nicht in Mark und
Pfennig, wie der günstige Preis des Buches belegt.
Olaf Kummer
EINAR SMITH
Elementare Berechenbarkeitstheorie
Springer, 166 Seiten, DM 28,-
ISBN 3-540-60667-X