Aufgabe:
Welche Funktion entsteht aus der primitiven Rekursion von den Funktionen \(g\) und \(h\)?
1. \(f_1=PR(g,h)\) mit \(g=succ\circ zero_0, h=zero_2\)
2. \(f_2=PR(g,h)\) mit \(g=zero_0, h=f_1\circ P_1^{(2)}\)
3. \(f_3=PR(g,h)\) mit \(g=P_1^{(2)}, h=P_2^{(4)}\)
4. \(f_4=PR(g,h)\) mit \(g=f_3\left(f_1(x),succ(x),f_2(x)\right)\)
Problem/Ansatz:
Definition:
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\),\(j\in \mathbb{N}\), \(j\geq 1\)
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:
\(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_i,t\in \mathbb{N}\), 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.
(1.) \(g:N^0\to N\), \(h:N^2\to N\)
\(f(0)=1\)
\(f(0+1)=h(0,f(0))=h(0,1)=0\)
\(f(1+1)=h(1,f(1))=h(1,0)=0\)
\(\forall n\in N_{>0}:f(n+1)=h(n,f(n))=0\), \(f_1\) ist definiert als \(f_1:N^1\to N\) mit \(f_1(x)=\begin{cases}1, x=0\\ 0, x>0\end{cases}\)
(2.) \(g:N^0\to N\), \(h:N^2\to N\)
\(f(0)=0\)
\(f(0+1)=h(0,f(0))=h(0,0)=1\)
\(f(1+1)=h(1,f(1))=h(1,1)=0\)
\(\forall n\in N_{>0}: f(n+1)=h(n,f(n))=0\), \(f_2\) ist genauso definiert wie \(f_1\), also \(f_1(x)=f_2(x)\)
(3.) \(g:N^2\to N\), \(h:N^4\to N\)
\(f(x,y,0)=x\)
\(f(x,y,0+1)=h(x,y,0,f(x,y,0))=h(x,y,0,x)=y\)
\(f(x,y,1+1)=h(x,y,1,f(x,y,1))=h(x,y,1,y)=y\)
\(\forall z \in N_{>0}: f(x,y,z+1)=h(x,y,z,f(x,y,z))=y\), \(f_3\) ist definiert als \(f_3:N^3\to N\) with \(f_3(x,y,z)=\begin{cases}x, z=0\\ y, z>0\end{cases}\)
EDIT: (4.) \(f_4=f_3(f_1(x),succ\circ x,f_2(x))\)
\(f_4=f_3(f_1(0), 1, f_2(0))=f_3(1,1,0)=1\)
\(f_4=f_3(f_1(0+1), 2, f_2(0+1))=f_3(0,2,1)=2\)
\(f_4=f_3(f_1(1+1), 2, f_2(1+1))=f_3(0,3,0)=0\)
\(\forall n \in\mathbb{N}_{>2}: f_4=f_3(f_1(n+1),2,f_2(n+1))=f_3(0,n+2,0)=0\)
