Geschrieben von Schnecke am 10.05.2017 um 15:49:
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
- z(0) = a
- z(x+1) = y(z(x))
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
- y(x) = x + 1
- z(x) = x + 2
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