0 Daumen
80 Aufrufe

Hallo,
ich studiere Medizininformatik und muss mich deshalb auch mit dem Modul "Theoretische Informatik" auseinander setzen.
Ich habe folgende Aufgaben bekommen zur Primitiven Rekursion.

Welche Funktionen entstehen durch primitive Rekursion aus:

\(\text{1. } \mathit{h=zero}_2, \quad \mathit{g=succ}_0\mathit{zero}_0\)
\(\text{2. } \mathit{g=zero}_0, \quad h=f_1\bigl(p_1^{(2)}(t,f_2(t))\bigr)\)
\(\text{3. } \mathit{g(x,y)=x}, \quad h(x,y,z,f_5(x,y,z))=p_2^4(h)=y\)

Ich sehe irgendwie bei primitiver Rekursion nicht wirklich durch.
Ich weiß, es gibt als Definition Projektion, Nachfolgerfunktion und Nullfunktion.
Da ich aber h und g schon gegeben habe und somit den Weg sozusagen rückwärts laufen muss, um zur Funktion zu kommen, weiß ich nicht so Recht wie ich das vorgehen soll.

Könnte mir bitte einer das anhand einer der Beispiele erklären bitte?

Vielen Dank schon mal!!

von

1 Antwort

0 Daumen
 
Beste Antwort

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.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community