Calculi nannten die Romer die Steinchen, mit denen sie auf dem Rechenbrett (lat. abacus) rechneten. Von diesem Wort ist das Wort ,,Kalktil" abgeleitet. Ein Beispiel fiir Kalktile sind die Logikkalktile. Das sind Regelsysteme zur formalen Umformung von Sprachpartikeln mit dem Ziel, logische Beweise zu formalisieren und auf kombinatorische Umformungen zuriickzufiihren. Allgemein sind Kalktile Regelsysteme zur rein formalen Umformung von Zeichenreihen. Diese brauchen nicht nur lineare Worte iiber einem Alphabet zu sein, es kann sich auch urn Muster in der Ebene oder im Raum handeln, die nach Regeln umge formt werden. FaBt man Spielregeln fiir Brettspiele (Legespiele) als Kalkiile auf, ist man der urspriinglichen Wortbedeutung wieder sehr nahe gekommen. Unter (Rechen)Maschinen stellt man sich Apparate zur automatischen Verarbeitung von Informationen vor. Dabei soli der Dbergang von einem Zustand in einen neuen nach festen Regeln (Programmen) verlaufen. In diesem Sinne stellen theoretische Modelle von Rechenmaschinen spezielle Kalkiile dar. Dieses Buch soli einen Einblick in ein Gebiet der mathematischen Grundlagenforschung geben, das sich mit dem kombinatorischen Hintergrund der Mathematik beschaftigt. Es sollen verschiedene Ansatze aufgezeigt werden, den intuitiven Begriff "Rechnen" mathe matisch zu prazisieren. Die Worte ,,Maschine" und "Kalkiil" (Regelsystem) bezeichnen dabei zwei Akzente, unter denen die intuitiven Vorstellungen prazisiert werden sollen. Bei der Beschaftigung mit Kalktilen und Maschinen geht es deshalb nicht urn die Behandlung verschiedener Gebiete, sondem urn die Untersuchung verwandter Theorien unter ver schiedenen Aspekten.

Inhalt

1. Einleitung.- 2. Konstruieren mit Baukästen.- 3. Handrechenmaschinen.- 4. Abstraktion von der Handrechenmaschine zu einer idealen Registermaschine (RM).- 5. RM-Berechenbarkeit.- 6. Unterprogramme für Registermaschinen.- 7. Verzweigung von Programmen.- 8. Primitiv-rekursive Funktionen.- 9. Primitiv-rekursive Prädikate.- 10. Die RM-Berechenbarkeit der primitiv-rekursiven Funktionen.- 11. Die Rekursivität der RM-berechenbaren Funktionen.- 12. Universelle Funktionen.- 13. Die Unentscheidbarkeit des Stop-Problems für RM.- 14. Rekursiv-aufzählbare Prädikate.- 15. Kompliziertheitsmaße für Funktionen.- 16. Charakterisierung der primitiv-rekursiven Funktionen.- 17. Kleine universelle Registermaschinen.- 18. Worterzeugende Kalküle.- 19. Induktive Definitionen und Beweise.- 20. Wortverarbeitende Kalküle.- 21. Wortalgorithmen.- 22. Unentscheidbare Wortprobleme.- 23. Legespiele.- 24. Netzwerke von Automaten.- Lösung der Übungsaufgaben.- Literatur.- Namen- und Sachverzeichnis.