8. Turingmaschinen

Wir haben in den vorherigen Kapitel mit primitiver Rekursion und $\lambda$-Kalkül zwei Modelle kennengelernt, die den Begriff der Berechnung formalisieren. Das $\lambda$-Kalkül ist im Prinzip eine reduktion funktionaler Programmiersprachen auf das absolut essentielle. In diesem Kapitel lernen wir ein weiteres Modell für Berechnung kennen, das im Allgemeinen als Standardmodell gilt: die Turingmaschine. Anders als primitive Rekursion und $\lambda$-Kalkül sind Turingmaschinen auch eng mit dem Begriff des Laufzeitkomplexität und Speicherplatzkomplexität verbunden und bilden somit das Fundament der Komplexitätstheorie, die sich insbesondere mit dem Resourcenverbrauch bei Rechenprozessen beschäftigt.