BuK-Übung10
Aus ProgrammingWiki
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)
- 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:
Berechnen Sie F1 und F2 für selbstgewählte Argumente.
