BuK-Übung10

Aus ProgrammingWiki
< BuK < IIm11

Beweisidee (Max Wielsch)

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.

Begründung (Raik Bieniek)

Begründen Sie, weshalb Polynome mit natürlichen Koeffizienten primitiv rekursiv sind.

Beispiel p(n)=an²+bn+c.

Polynome bestehen nur aus Additionen, Multiplikationen und Potenzierungen. Diese sind bereits als primitiv rekursiv nachgewiesen.

Für das Beispiel:

p(n)=add(mult(a,pot(n,2)),add(mult(b,n),c))

Berechnung (Felix Nitsche, Stefan Lüttke)

Der rumänische Mathematiker Gabriel Sudan (14.04.1899 - 22.06.1977) - wie Ackermann ebenfalls ein Schüler von David Hilbert - hat 1927 eine total berechenbare jedoch nicht primitiv rekursive Funktion publiziert. Sie ist folgendermaßen definiert:

F_0(x,y)=x+y\\ F_{n+1}(x,0)=x,n\geq0\\ F_{n+1}(x,y+1)=F_n(F_{n+1}(x,y),F_{n+1}(x,y)+y+1),n\geq0

Berechnen Sie F1 und F2 für selbstgewählte Argumente.