Hallo.



Sei (f_n) eine Folge von LOOP-berechenbaren Funktionen, so dass f_n durch ein LOOP-Programm mit n LOOP-Schleifen, nicht aber durch ein LOOP-Programm mit n-1 LOOP-Schleifen berechnet werden kann.



Zeigen oder widerlegen sie: Die Funktion g mit g(k,n)=f_k(n) ist Loop-berechenbar.



hat da wer ne Idee dazu?

Zeigen oder widerlegen sie: Die Funktion g mit g(k,n)=f_k(n) ist Loop-berechenbar.

Was ist denn k(n)?
Ohne zu wissen, wie der neue Index zu f_n entsteht,
geht da doch eher gar nix !?

So fällt mir kaum etwas Schlaues dazu ein, sorry

sorry die schreibweise ist verwirrend.
gemeint ist
[img]http://mokrates.de/cgi-bin/texstring?f_n[/img]
und g(k,n) = f_k(n) sollte heissen:

[img]http://mokrates.de/cgi-bin/texstring?f_k(n)[/img]

Sei (f_n) eine Folge von LOOP-berechenbaren Funktionen, so dass f_n durch ein LOOP-Programm mit n LOOP-Schleifen, nicht aber durch ein LOOP-Programm mit n-1 LOOP-Schleifen berechnet werden kann.



Zeigen oder widerlegen sie: Die Funktion g mit g(k,n)=f_k(n) ist Loop-berechenbar.

Annahme: Sei g berechenbar.
Dann folgt dass fuer jedes k g mit n loop-schleifen berechenbar ist. waehle nun k=n+1, also:
g mit n loop-schleifen berechenbar, aber g=
[img]http://mokrates.de/cgi-bin/texstring?f_n+1(n)[/img] nach konstruktion in n+1 schleifen berechenbar und nicht in n.
-> annahme falsch->g nicht berechenbar