\( \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\pfrac}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\keys}{\textnormal{keys}} \newcommand{\E}{\mathbb{E}} \newcommand{\array}{\textnormal{array}} \newcommand{\first}{\textnormal{first}} \newcommand{\First}{\textnormal{FIRST}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\blackdepth}{\textnormal{blackdepth}} \newcommand{\blackheight}{\textnormal{blackheight}} \newcommand{\step}[1]{\stackrel{#1}{\rightarrow}} \newcommand{\rstep}[1]{\stackrel{#1}{\rightarrowtail}} \newcommand{\Step}[1]{\stackrel{#1}{\Longrightarrow}} \newcommand{\qstart}{q_{\rm start}} \newcommand{\qend}{q_{\rm end}} % \newcommand{\dk}[1]{\boldsymbol{#1}} % stands for DK-Grammar (Donald Knuth, LR-parser) % \newcommand{\dk}[1]{\ \boxed{#1}\ } % stands for DK-Grammar (Donald Knuth, LR-parser) \newcommand{\dk}[1]{\hat{#1}} % stands for DK-Grammar (Donald Knuth, LR-parser) % \newcommand{\dkt}[1]{\colorbox{lightgreen}{#1}} % stands for DK-terminal (Donald Knuth, LR-parser) \newcommand{\dkt}[1]{#1} % stands for DK-terminal (Donald Knuth, LR-parser) \)

7. Turing-Maschinen

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.