Termination

Satz: Jedes Programm aus terminiert (hält) für jede Eingabe.


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


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

Beispiel: Interpreter für primitiv rekursive Programme.



Johannes Waldmann 2011-01-18