Rekursion -> Iteration
-
Hi!
Gibts es rekursive Funktionen die sich nicht iterativ auflösen lassen?
Will heißen: Ich brauche ein Funktion die nicht primitiv rekursiv, nicht partiell rekursiv und nicht durch eine Turingmaschine berechenbar ist.
-
es lässt sich so ziemlich alles rekursiv lösen, was auch iterativ geht.
-
DocJunioR schrieb:
es lässt sich so ziemlich alles rekursiv lösen, was auch iterativ geht.
Die Frage war andersrum^^
-
Es lässt sich alles iterativ lösen, was auch rekursiv geht.
Zufrieden?
-
Hauptmann schrieb:
Gibts es rekursive Funktionen die sich nicht iterativ auflösen lassen?
Wenn das so gemeint ist, wie ich es verstehe, lautet die Antwort nein, jede Rekursion kann durch Zuhilfenahme eines Stacks mechanisch in eine Iteration umgewandelt werden.
Will heißen: Ich brauche ein Funktion die nicht primitiv rekursiv, nicht partiell rekursiv und nicht durch eine Turingmaschine berechenbar ist.
Das ist eine vollkommen andere Frage. Es gibt Funktionen, die nicht berechenbar sind, ob nicht von einer Turing-Maschine oder von sonstwas nicht, spielt dabei keine Rolle. Stichwort Halteproblem und Konsorten.