Einführung in die Informatik

Die hier beschriebenen mathematischen Maschinen sind mehr oder weniger abstrakte Modelle von elektronischen Rechnern. “Mathematisch” ist als Gegensatz zu “physikalisch” zu verstehen. Es handelt sich also nicht um die Realisierung einer physikalischen Maschine, sondern um eine mathematische Konstruktion. Zwar verwenden wir dabei physikalische Begriffe (“Speicher”, “Adresse”, “Befehl”, “Schaltwerk”,...) und geben auch eine physikalische Interpretation für die Arbeitsweise unserer Maschine (“Befehl wird in das Befehlsregister β geladen”, “Maschine stoppt”,...), dadurch soll jedoch nur der intuitive Hintergrund der Definitionen angedeutet werden. Desweiteren sehen wir von physikalischen Problemen wie Ausführungszeiten von Operationen etc. ab. Um beweisbare Aussagen innerhalb einer Theorie der Rechenmaschinen formulieren zu können, bedarf es solcher mathematischer Modelle.

Im ersten Teil des Buches haben wir von einfachen Programmieraufgaben ausgehend eine einfache Programmiersprache entwickelt, die es erlaubt, Algorithmen zur Lösung dieser Aufgaben zu programmieren. Ohne uns dann eine ernsthafte Rechenschaft darüber abzuverlangen, ob diese Programmiersprache zur Formulierung aller Algorithmen taugt, sind wir in Kapitel 3 des Buches dazu übergegangen, zu dieser Sprache eine Maschine zu konstruieren, die die Programme dieser Sprache ausführen kann.