0 Daumen
28 Aufrufe

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}\)

Ist das bis hierhin korrekt??

von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

1 Antwort
Gefragt 19 Jan 2015 von Gast
1 Antwort
Gefragt 16 Dez 2014 von Gast
2 Antworten

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community