BuK/IIm11/Studenten/simawiel/ue10

Wiki-Quelltext dieser Seite.

== Entwickeln Sie eine Beweisidee zu folgendem Satz ==

Jede primitiv-rekursive Funktion ist LOOP-berechenbar und
umgekehrt.

LOOP-Programme sind gekennzeichnet durch folgende Konstrukte:
* Wertzuweisungen (Bindung an Variablen)
* Konstanten
* Iterationen / Zyklen (LOOP <Wert> DO <Sequenz> END)
* Programmaufrufe

weiterhin ist von vornherein bekannt, wie viele Zyklen ein LOOP-Programm durchläuft.

Primitiv-rekursive Funktionen sind wie folgt definiert:
* Es gibt Basisfunktionen, die allesamt total und berechenbar sind.
** Nachfolgerfunktion
** Nullfunktion
** Projektionsfunktion
Mit diesen Basisfunktionen und den 2 folgenden Techniken können weitere Funktionen beschreiben werden:
* Primitive Rekursion
* Substitution

Nun können die Konstrukte aus der LOOP-Sprache wie folgt den Vorschriften der primitiv-rekursiven Funktionen zugeordnet werden.

* Variablen können der Zahl den Parametern in der Funktionsdefinition zugeordnet werden
* Konstanten können durch die Nullfunktion erreicht werden.
* Zyklen werden durch die primitive Rekursion erreicht.
* Programmaufrufe entsprechen Substitution

Umgekehrt kann zugeordnet werden:

* Die Nachfolgerfunktion kann durch die primitiv-rekursive Funktion add realisiert werden
* Die Projektionsfunktion bedeutet in LOOP-Programmen einen Programmaufruf mit n Argumenten.