
\begin{slide}{Termination}
Satz: Jedes Programm aus
\begin{itemize}\itemsep 0pt
\item Zuweisungen
\item Verzweigungen
\item Zählschleifen 
\end{itemize}
terminiert (hält) für jede Eingabe.

\bigskip
Äquivalenter Begriff (für Bäume anstatt Zahlen):
strukturelle Induktion (fold, Visitor, primitive
Rekursion)

\bigskip
Satz: es gibt berechenbare Funktionen,
die nicht primitiv rekursiv sind.

Beispiel: Interpreter für primitiv rekursive Programme.

\end{slide}

