LOOP Berechenbarkeit

Neue Frage »

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

  • 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
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »