Die Theoretische Informatik - die mathematische Untersuchung von Modellen der Berechenbarkeit - ist ein Gebiet, das seine Wurzeln zum gro~eren Teil in mathematischen Grundlagenuntersuchungen der 30er Jahre hat (CHURCH, GtiDEL, KLEENE, POST und TURING) und das von der nach wie vor anhaltenden technischen Entwicklung in starkem Ma~e beeinflu~t wird. Wie kein anderes Gebiet hat es die Aufgabe, grundlegende Kennt­ nisse bereitzustellen, die es auf einem sicheren wissenschaftli­ chen Fundament ermoglichen, Heterogenitat und Diffusitat vieler Probleme und Erscheinungen in Grenzen zu halten und eine schnel­ le Anpassung an neue Entwicklungen vorzunehmen. Genau diese fun­ damentale Kraft der Theoretischen Informatik wird an vielen Stellen unterschatzt, und deshalb erscheint sie haufig als ein Gebiet, das man hal t gepriift wird), absolvieren mu~ (weil es aber zur praktischen Arbeit und zur beruflichen Praxis scheinbar kaum Beziehungen hat. Diesem Vorurteil entgegenzutreten und die Liicke zwischen mathematischen Grundlagen und praktischer Infor­ matik ein wenig zu schlie~en, ist ein Anliegen dieses Buches.