ue10

Aus ProgrammingWiki
< BuK < IIm11 < Studenten < simawiel

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)</sequenz></wert>
  • 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.