Primitiv rekursive Funktionen und $\mu$-rekursive Funktionen:

specific part [[theo2_VergleichModelleBerechenbarkeit]] broad part of [[112.00_anchor_overview]]

Als Motivation wollen wir folgend betrachten: Mit primitiv rekursiven Funktionen und weiter $\mu$-rekursiven Funktionen betrachten wir ein ganz anderes Berechnungsmodell, denn es fundiert primär auf der Mathematik und entsprang auch in dieser Sparte. Etwa vor 100 Jahren ward dieses System entwickelt - also so 1920er, wo es noch keine Informatiker*innen. Weiterhin gab es zu diesem Zeitpunkt auch noch keine Turingmaschinen!

Primitiv rekursive Funktionen:

Idee :

WIr betrachten folgend Funktionen, die eine feste Anzahl $k$ an natürlichen Zahlen als Eingabe erhalten und eine natürliche Zahl als Ausgabe erzeugen können. wir würde also die Abbildungsvorschrift aussehen? #card Wir schreiben also: $f:{\mathbb{N}}^k⟶\mathbb{N}$ Eine Funktion mit $k$ Eingaben nennt man dann auch eine $k$-stellige Funktion.

Definition:

Die Menge der primitiv rekursiven Funktionen wir induktiv definiert wie folgt: Dabei haben wir im Induktionsanfang drei definierte Funktionen: konstante,nachfolgerfunktion und Projektionsfunktion, was machen diese? #card Induktionsanfang:

1. DIe konstante, $0-$stellige Funktion $0$ ist pirmitiv rekursiv.
2. Die Nachfolgerfunktion $s$ für successor ist folgend definiert: $\mathbb{N}⟶\mathbb{N},s(k)=k+1$ und ist sie primitiv rekursiv
3. Die Projektionsfunktion der folgenden Form: $f_i:{\mathbb{N}}^k⟶\mathbb{N},(x_1,x_2,\dots ,x_k)⟼x_i$, welche ebenfalls primitiv rekursiv ist.

Induktionsschritt: 4. Die Komposition von primitiv rekursiven Funktionen ist ebenfalls primitiv rekursiv, denn: Seien $f:{\mathbb{N}}^k⟶\mathbb{N},g_1,\dots ,g_k:{\mathbb{N}}^m⟶\mathbb{N}$ und diese ist primitiv rekursiv. Weiter ist es dann auc $h(x_1,\dots ,x_m):=f(g_1(x_1,\dots ,x_m),\dots g_k(x_{1,}\dots ,x_m))$

5. Primitive Rekursion: Seien jetzt $g:{\mathbb{N}}^k⟶\mathbb{N},h:{\mathbb{N}}^{k+1}⟶\mathbb{N}$ ist primitiv rekursiv. Dann ist aber auch die folgende Funktion $f:{\mathbb{N}}^{k+1}⟶\mathbb{N}$ primitiv rekursiv. Betrachten wir dafür: $f(0,x_1,\dots ,x_K)=g(x_1,\dots ,x_k)$ -> wir haben die 0 geskipped! Dann auch: $f(s(n),x_1,\dots ,x_k)=h(f(n,x_1,\dots ,x_k),x_1,\dots ,x_k)$

Beispiel : Addition :

Betrachten wir die Addition wie folgt: $add:{\mathbb{N}}^2⟶\mathbb{N}$ ist eine primitiv rekursive Funktion. Warum? wie können wir sie beschreiben? #card schreiben wir sie wie folgt: $add(0,x)=x$ und weiterhin dann $add(s(n),x)=s(add(n,X))$ wobei wir mit $s$ den Nachfolger bezeichnen wollen.

Intuition ist dann also eine mathematische Schreibweise, wie folgt: $(n+1)+x=(n+x)+1$ -> denn so ist die mathematische Definition der Addition wenn man die natürlichen Zahlen mit Hilfe der Peano-Axiome definiert.

Primitiv rekursive Funktion $⟺$ for:

Das wollen wir ferner zeigen und setzen als Intuition zuerst: welche Schritte werden wir gehen? wir müssen eine Initialisierung und später eine Konvertierung bzw Rekursion aufbauen #card $f(0,x_1,\dots ,x_k)=g(x_1,\dots ,x_k)$ -> Initialisierung : betrachte, dass hier die Eingaben den gleichen Betrag weiterbehalten werden, also die Argumente werden eins zu eins übernommen. weiter dann: $f(n+1,x_1,\dots ,x_k)=h(f(n,x_1,\dots x_k),x_1\dots ,x_k)$ –> wobei hier f jetzt das Ergebnis nach $n+1$ Schleifenschritten darstellt. Weiterhin haben wir nach der Anpassung jetzt $h$ definiert, was der Berechnung der Schleife basierend auf dem Ergebnis des vorigen Schleifendurchlaufs.

Satz : #card

Die Menge er primitiv rekursiven Funktionen stimmt genau mit der Menge der for-berechenbaren Funktionen überein.

Beweis:

Um dies zu zeigen, müssen wir auch beide Seiten betrachten, also die beidseitige Rekursion zeigen!

Also folgt zuerst die Richtung:

for berechenbar $⟶$ primitiv rekursiv berechenbar.

Dies wird wieder mit einer strukturellen Induktion beweisbar sein. Also jede Variable des for-Programms wird durch eine Variable der Funktion beschrieben.

Induktionsanfang: Wir können einfache Befehle in for-Programmen durch eine primitiv rekursive Funktion beschreiben: Also in etwa folgend: $x_i=x_j+x_k;x_i=x_j-x_k;x_i=c$ Intuitiv ist dann klar, denn wir haben es bereits gesehen/ wahrgenommen, dass die Addition primitiv rekursiv ist. Das Gleiche gilt für die Subtraktion und eine konstante Funktion –> das haben wir zuvor bereits gezeigt, bzw. kann man eine Subtraktion als Addition darstellen!

Induktionsschritt: Hintereinanderausführung: betrachten wir das for-programm: bedenke es wird als $[P_1;P_2]$ beschrieben. Unsere Induktionsannahme wäre jetzt: wir können die Programm $P_1,P_2$ durch zwei Funktionen $g_1,g_2$ beschreiben. Können wir das, dann können wir auch die Hintereinandeausführung dieser als Funktion schreiben: $g_2(g_1)$ wir können sie dann wieder als primitiv rekursiv beschreiben.

Induktionsschritt 2 : for-Schleifen: Betrachten wir jetzt eine For-schleife; for $x_1$ do $P$ end: Unter Anwendung der Induktionsvoraussetzung können wir P durch eine Funktion $g_p$ beschreiben. Unter dieser Voraussetzung können wir jetzt also die for-Schleife folgend beschreiben: $f(0,x_1,\dots ,x_k)=\dots$ -> erstmal nur die Initialisierung der Variablen der for-Schleife. Weiter $f(n+1,x_1,\dots x_k)=g_p(f(n,x_1,\dots ,x_n))$ wobei wir mit $g_p$ die Berechnung in der for-Schleife beschreiben.

Somit haben wir die eine Richtung der Äquivalenz bereits gezeigt

primitiv rekursiv $⟹$ for-berechenbar:

Am Ende werden wir sehen, dass die Berechnung für diese Richtung exakt gleich ablaufen wird, man also mit einer Induktion die Schritte beweisen und dann zu einer for-Schleife umformen kann. Daraus folgt also die Äquivalenz!

$\mu$-rekursive Funktionen:

Wir haben soeben die Äquivalenz zwischen for-Programmen und der rekursiven Funktion gezeigt. Also wissen wir auch, dass diese rekursiven Funktionen nicht turing-äquivalent sind, denn while $/⪯$ for!

Wir würden jetzt gerne ein Konstrukt von rekursiven Funktionen bauen, was dennoch Turing-äquivalent ist, also mächtiger als normale rekursive Funktionen. Wir führen hierfür nun einen zweiten Rekursionsoperator ein, die $\mu$-Rekursion wobei wir $\mu$ symbolisch als Minimum betrachten. #card Dabei ist eine $(k+1)$-stellige Funktion $f:{\mathbb{N}}^{k+1}⟶\mathbb{N}$ gegeben. und wir wollen über ihre erstes Argument ein Minimum bilden: Also am Ende möchten wir folgendes finden: $min\{n|f(n)=0\}$

Definition:

Die Menge $M$ der $\mu$-rekursiven Funktionen wird induktiv folgend definiert. es gibt zwei eindeutige Beschreibung dieser Funktion, welche? #card

1. Alle primitiv rekursiven Funktionen sind in $M$ enthalten.
2. Alle Funktionen sind enthalten, die durch Anwendung des $\mu$-Operators aus primär rekursiven Funktionen gebaut werden können: Das heißt folgend: Sei $f:{\mathbb{N}}^{k+1}⟶\mathbb{N}$ eine möglicherweise auch nur partiell definierte Funktion. Dann ist $\mu f:{\mathbb{N}}^k⟶\mathbb{N}$ dann folgend definiert: $(\mu f)(x_1,\dots ,x_k)=\min \{m\in {\mathbb{N}}_0|f(m,x_1,\dots ,x_k)=0\text{ und fu¨r alle }u<m:f(u,x_1,\dots ,x_k)\text{ definiert }\}$ Ist diese folgende Menge leer, dann ist $(\mu f)(x_1,\dots ,x_k)$ undefiniert.

Partiell definiert heißt in diesem Kontext, :: dass die Funktion nicht terminieren muss und so auch an einer Stelle undefiniert sein kann.

Existenz von partiell definierten Funktionen:

Die $\mu$-rekursive Funktionen müssen nicht total sein, also sie können auch nur partiell definiert sein. #card Das heißt dann, dass eine Funktion $f:{\mathbb{N}}^k⟶\mathbb{N}$ nicht jedem Element ihres Definitionsbereiches einen Wert zuweisen muss. Es kann also Definitionslücken geben.

Konstruktion:

Betrachten wir folgend die Intuition zur Funktion: $(\mu f)(x_1,\dots ,x_k)=\min \{m\in {\mathbb{N}}_0|f(m,x_1\dots ,x_k)=0\}$ wir suchen also das kleinste $m$ so, dass unser Term mit 0 resultiert. Weiter definieren wir die Menge dann so: $\{\forall u<m:f(u,x_1,\dots ,x_k)\text{ ist definiert}\}$ Es kann sein, dass die Menge leer ist. In dem Fall ist dann der Funktionswert $\mu f$ an dieser Stelle nicht definiert und $\mu f$ nur eine partielle Funktion

Unterschied zur primitiven Rekursion:

Worin bestehen die zwei großen Unterschiede zur primitiven Rekursion? #card

1. Ein Minimum über eine feste Anzahl von Variablen könnten auch primitiv rekursiv sein
2. Der Knackpunkt ist hier, dass wir ein Minimum über die Menge $\{u|f(u,\dots )=0\}$ bilden, von der wir vorher gar nicht wissen, wie viele Elemente sie enthalten könnte. –> Also unser Input kann scheinbar unendlich groß sein! Anders, als bei der primitiven Rekursion, wo unsere Anzahl / bzw. Menge begrenzt war.

wir wollen jetzt ferner zeigen, dass while-Programme $\equiv$ $\mu$-rekursiven Funktionen sind!

$\mu$-rekursive Funktionen $\equiv$ while

Die Menge der $\mu$-rekursiven Funktionen stimmt genau mit der Menge der whhile-berechenbaren Funktionen überein.

Eine mögliche Beweisskizze könnte folgend aussehen: Wir werden wieder eine strukturelle Induktion anwenden Wir wissen bereits: primitiv rekursiv $\equiv$ for. Jetzt müssen wir nur noch die Äquivalenz zwischen $\mu$-Operator und while-Schleife zeigen.

Beweis:

while-Schleife $⟶\mu$-Operator, Intuition: Betrachte folgende While-Schleife: while $x_i\notin 0$ do $Q$ end wobei wir annehmen, dass $Q$ durch eine $\mu$-rek. Funktion dargestellt werden kann. ei $k(m,\dots )$ der Wert der Variable $x_i$, nachdem die while-Schleife $m$ malch durchlaufen wurde. Durch den $\mu$-Operator können wir anschließend herausfinden, wann die Variable $x_i$ zum ersten Mal 0 entspricht! Dann können wir ab da eine primitiv rekursive Funktion definiere, die genau so oft hintereinander ausgeführt wird!

Beweisen wir die andere Richtung / Implikation : $\mu$-rekursive $⟶$ while-schleife : hier ist er Beweis ähnlich wie zuvor, jedoch jetzt icht ausgeführt, da nicht relevant.

Resultat der Äquivalenz:

Wir wissen jetzt: was? #card

1. primitiv rekursiv $\equiv$ for
2. $\mu$-rekursiv $\equiv$ while
3. for$⪯$ while, aber nicht umgekehrt. Also muss es Funktionen geben die $\mu$-rekursiv sind, aber nicht primitiv rekursiv!. Ein solches Beispiel wäre die Ackermann-Funktion::