rekursive Funktionen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:28 Fr 02.05.2008 | | Autor: | Docy |
| Aufgabe | Seien [mm] f_1 [/mm] und [mm] f_2 [/mm] wie folgt definiert: [mm] f_1(0)=1=f_2(0) [/mm] und
[mm] f_1(x+1)=f_1(x)+f_2(x)
[/mm]
[mm] f_2(x+1)=f_1(x)*f_2(x)
[/mm]
Beweisen oder widerlegen Sie: [mm] f_1, f_2 \in [/mm] Prim. Sie können eine bijektive, primitiv rekursive Funktion c: [mm] \IN² \mapsto \IN [/mm] und primitiv rekursive Funktionen [mm] k_1 [/mm] und [mm] k_2 [/mm] verwenden, mit [mm] k_1(c(x,y))=x [/mm] und [mm] k_2(c(x,y))=y
[/mm]
|
Hallo alle zusammen,
könnte mir jemand bitte bei dieser Aufgabe helfen? Ich hab da überhaupt nicht die leiseste Ahnung, wie ich da rangehen soll. Bin dankbar für jegliche Hilfe
Gruß Docy
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:02 So 04.05.2008 | | Autor: | barsch |
Hi,
die Antwort kann ich dir auch nicht geben, aber vielleicht hilft dir das weiter:
[mm] f_1(0)=f_2(0)=1
[/mm]
[mm] x=0:f_1(0+1)=f_1(0)+f_2(0)=2 [/mm] ist Prim
[mm] x=1:f_1(1+1)=f_1(1)+f_2(1)=f_1(0+1)+f_2(0+1)=f_1(0)+f_2(0)+f_1(0)*f_2(0)=1+1+1*1=3 [/mm] ist Prim
[mm] x=2:f_1(2+1)=f_1(2)+f_2(2)=f_1(1+1)+f_2(1+1)=f_1(0)+f_2(0)+f_1(0)*f_2(0)+f_1(0+1)*f_2(0+1) =f_1(1+1)+f_2(1+1)=f_1(0)+f_2(0)+f_1(0)*f_2(0)+(f_1(0)+f_2(0))*(f_1(0)*f_2(0))=1+1+1*1+(1+1)*(1*1)=5 [/mm] ist Prim
[mm] x_3:...
[/mm]
Erkennt man eine gewisse Regelmäßigkeit - was mir momentan nicht gelingt -, kann man evtl. beweisen, dass [mm] f_1,f_2\in{Prim}.
[/mm]
MfG barsch
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:21 Di 06.05.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
