LOOP Berechenbarkeit |
10.05.2017, 15:49 | Auf diesen Beitrag antworten » |
Schnecke | LOOP Berechenbarkeit Hallo liebe Gemeinde, stehe vor einem Problem, hoffe ihr könnt mir helfen. Aufgabenstellung: Sei a aus N eine Konstante und y : N -> N irgendeine LOOP-berechenbare Funktion. Sei eine weitere Funktion z : N -> N definiert als
Offensichtlich gilt für den ersten Punkt nur die Konstante, beim zweiten Punkt besteht die Komposition. Es soll nun gezeigt werden, dass z (wie es definiert ist) definitiv auch eine LOOP-berechenbare Funktion ist. Dieses Schema soll auch angewendet werden, um zu zeigen, dass f(x) = 2^x LOOP-berechenbar ist. Ansatz: Ich habe mir zunächst zwei LOOP-berechenbare Funktionen gebaut, nämlich
Dann habe ich hinsichtlich der Definition von z einfach einmal beliebige Zahlen eingesetzt und festgestellt, dass z LOOP-berechenbar ist. Zum Beispiel ist z(0) = 2 und z(0+1) = g(3) = 4. Ein LOOP-Programm für 2^x kann ich auch schreiben, gar kein Problem. Jedoch fehlt mir komplett der Ansatz, es zu zeigen, dass z LOOP-berechenbar ist. Es muss ja irgendeine Schema sein, womit ich dann auch 2^x zeigen kann, ohne einfach ein LOOP-Programm angeben zu müssen. Hat jemand vielleicht eine Idee, wie man es machen könnte? LG |
|
|