Thema dieses Buches sind zwei schon Voh Leibniz als zusammengehörend
erkannte Begriffe, deren mathematische Entwicklung von Frege bis Turing
das theoretische Fundament der Computerwissenschaft gelegt hat: der Be-
griff formaler Sprache als Träger präzisen Ausdrucks von Bedeutungen,
Sach- verhalten, Problemen und der des Algorithmus oder Kalküls, d. h.
formal ope- rierender Verfahren zur Lösung präzis beschriebener Fragen
und Probleme. Das Buch gibt eine einheitliche Einführung in die moderne
Theorie dieser Begriffe, wie sie sich zuerst in der mathematischen Logik
und der Berechen- barkeitstheorie und weiter in der Automatentheorie,
der Theorie formaler Sprachen und der Komplexitätstheorie entwickelt
hat. Neben der Berücksich- tigung eines schon klassisch gewordenen
Grundkanons dieser Gebiete ist die Stoffauswahl mit der Absicht
getroffen worden, durchgängig Erneuerungen traditioneller
Fragestellungen, Ergebnisse und Methoden den Vorrang zu ge- ben, die
sich aus Bedürfnissen oder Erkenntnissen der Informatik und hier
besonders der Komplexitätstheorie heraus entwickelt haben. Die
Zielsetzung dieses Buches ist eine doppelte: Lehrbuch zu sein. für
Anfängervorlesungen zu den genannten Gebieten, wie sie in fast allen
Curri- cula der Informatik, der Logik und der Mathematik heute
auftreten, aber darüberhinaus auch Monographie, indem in systematischer
Absicht in jedem der angesprochenen Gebiete weiterführende Ergebnisse
neuerer Forschungen (großenteils erstmalig in lehrbuchartiger Form)
vorgeführt werden und über- all versucht wird, Analogien und
Zusammenhänge zwischen verschiedenen Be- griffen und Konstruktionen
explizit herauszuarbeiten.
