Erstmal allgemein zur Definition der primitiv-rekursiven Funktionen:
Folgende Funktionen sind prim. Grundfunktionen:
Projektionsfunktion:
\(P_i^j:\mathbb{N}^j\to \mathbb{N}\)
\(P_i^j(x_1,\dots,x_j)=x_i\) für alle \(1\leq i\leq j,\quad i,j\in \mathbb{N},\quad j\geq 1\), \(x_1,\ldots,x_j\in\mathbb{N}\)
Nachfolgerfunktion:
\(s:\mathbb{N}\to\mathbb{N}\)
\(s(x)=x+1\)
Nullfunktion:
Für alle \(k\in \mathbb{N}\) die Erzeugung der Null-Funktion von Stelligkeit \(k\):
\(zero_k:\mathbb{N}^k\to \mathbb{N}\)
\(zero_k(x_1,\dots,x_k)=0\)
Operationen auf prim. rek. Funktionen:
Komposition: Sei \(g:\mathbb{N}^k\to\mathbb{N}\) und \(h_1,\ldots,h_k:\mathbb{N}^l\to\mathbb{N}\) zwei primitiv rekursive Funktionen, dann ist die Komposition \(g:\mathbb{N}^l\to\mathbb{N}\) mit \(g(h_1,\ldots,h_k)(x_1,\ldots,x_l)=g\left(h_1(x_1,\ldots,x_l),\ldots, h_k(x_1,\ldots,x_l)\right)\)
\(PR(x,y)\) is die Primitive Rekursion:
Sei \(k\geq 0\), \(g:\mathbb{N}^k\to \mathbb{N}\) und \(h:\mathbb{N}^{k+2}\to\mathbb{N}\), für alle \(x_1,\ldots,x_k,t\in \mathbb{N}\) zwei primitiv rekursive Funktionen, dann ist die Funktion \(f:\mathbb{N}^{k+1}\to\mathbb{N}\) definiert durch
i) \(f(x_1,\dots,x_k,0):=g(x_1,\dots,x_k)\)
ii) \(f(x_1,\dots,x_k,t+1)=h(x_1,\dots,x_k,t,f(x_1,\dots,x_k,t))\)
aus primitiver Rekursion von g und h entstanden.
Alle Funktionen, die mithilfe der Grundfunktionen bzw. schon primitiven Funktionen und in endlich vielen Schritten aus der Komposition oder primitiven Rekursion entstanden sind, sind primitiv rekursiv.
Zur Aufgabe 1.:
Da \(g()=\operatorname{succ}\circ \operatorname{zero}_0()\) weißt du, dass \(g:\mathbb{N}^0\to\mathbb{N}\) eine Stelligkeit von 0 hat. (Wir bilden 0 Parameter auf die 1 ab.)
Weil \(h(x,y)=\operatorname{zero}_2(x,y)\) (1) weißt du, dass \(h:\mathbb{N}^2\to\mathbb{N}\) eine Stelligkeit von 2 hat. (Wir nehmen 2 beliebige Parameter und bilden sie immer auf 0 ab.)
Da du nun die Stelligkeiten von \(g\) und \(h\) kennst, muss deine gesuchte Funktion \(f\) eine Stelligkeit genau zwischen den beiden Funktionen \(g,h\) aufweisen: \(f:\mathbb{N}^1\to\mathbb{N}\).
Jetzt setzen wir suksessive Werte für die Funktionen ein, um dann eine Vermutung für die gesuchte Funktion \(f\) aufzustellen: (Fangen wir mit dem Rekursionsbeginn an.)
$$\begin{aligned} f(0):&=g()= \operatorname{succ}\circ \operatorname{zero}_0()=1\\ f(0+1)&=h(0,f(0))=\operatorname{zero}_2(0,f(0))=0\\ f(1+1)&=h(1,f(1))=\operatorname{zero}_2(1,f(1))=0\\ \vdots\\ f(n+1)&=h(n,f(n))=\operatorname{zero}_2(n,f(n))=0\quad \forall n\in\mathbb{N}\setminus \{0\} \end{aligned}$$
Wie du sehen kannst, bildet die \(h\)-Funktion jeden beliebigen Wert immer auf \(0\) ab, egal was wir einsetzen. Daher stellen wir folgende Vermutung auf: Die gesuchte Funktion \(f\) ist \(f(x)=\begin{cases}1 & x=0\\ 0 & x>0\end{cases}\).
Das müssen wir jetzt noch durch Induktion beweisen:
Induktionsanfang: \(f(0)=1\quad \checkmark\)
Induktionsbehauptung: \(f(x)=\begin{cases}1 & x=0\\ 0 & x>0\end{cases}\) für ein beliebig festes \(x\in\mathbb{N}\).
Induktionsschritt: \(x\to x+1\), also \(x+1\) muss größer 0 sein.
$$\begin{aligned}f(x+1)&=h(x,f(x))\\ &\stackrel{(1)}{=}\operatorname{zero}_2(x,f(x))\\&={\underline{0}}\end{aligned}$$ Aussage stimmt, für \(x+1>0\) ist \(f(x+1)=0\), demnach war unsere Vermutung korrekt.
Mit dem gleichen Verfahren können wir auch die beiden anderen Aufgaben lösen.
