Iterative Ackermannfunktion: Und sie gibt es doch (puh!)

[Der_Unwissende]

Hey,
das ist doch mal ein Thread der mich interessiert (für alle die nicht den Thread Theorie: Rekursive Funktion Abbrechen und Fortsetzen gelesen haben, ich bin der jmd (einer der?) der diese Behauptung aufgestellt hat)

Ok, ohne es jetzt zu überprüfen, geb ich dir mal Recht, dass ist der Algorithmus für die von-Neumann-Funktion in iterativ. Damit ist natürlich dieser Thread beendet (ausser jmd. traut an Beweis oder Gegenbeweis).
Aber

Zitat:

das nicht jede rekursive Funktion in ein iteratives Äquivalent überführt werden kann (was Quatsch ist)

es ist eben noch nicht gezeigt dass sich jede rekursive Funktion in eine iterative Überführen lässt.
Zugegeben, ich habe mich bisher immer auf Ackermann berufen, aber Ackermann ist halt nur eine von überabzählbar vielen rekursiven Funktionen. Es gibt halt schon überabzählbar viele Funktionen, die iterativ sind und jede iterative Funktion lässt sich erst recht in Rekursion überführen. Was hier aber eigentlich gesucht ist, ist eine Bijektion zwischen der Menge der rekursiven Funktionen und der Menge der iterativen Funktionen.
Sinnvollerweise kann man sich natürlich auf die wirklich (eben nicht nur durch ein CPU) berechenbare Funktionen beziehen (auch Turing-berechenbar oder intuitiv berechenbar genannt). Ok, jetzt fehlt hier für die (nur noch unendlich abzählbare Funktionen) die Bijektion. Das wäre ein Beweis. Ackermann könnte ja nur eine schlecht gewählte Funktion gewesen sein (ok, muss natürlich sagen, dass meine Unsicherheit stark auf dieser Funktion beruht hatte).
Ach ja, @alzaimar, im letzten Thread schrieb ich auch schon, dass ich mir nicht mehr sicher bin. Ich denke, dass es einen Beweis gab, der ganz klar zeigte ob es eine solche Bijektion gibt oder nicht, ich hab ihn halt nur nicht mehr in Erinnerung. Glaube eh, dass ich auch einen falschen Beweis akzeptieren würde (ist denke ich doch mal nicht mehr soweit her mit meinem Wissen in der TI).

Na ja, danke jedenfalls mal für die iterative Variante von Ackermann! Und auch wenn sie nicht so elegant und hübsch ist, wie die rekursive Funktion, so kann ich trotz allem nur auf den geringeren Ressourcenbedarf verweisen. Oh man, da müsste ich eigentlich glatt mal gucken ob ich da nicht Lüge, hm, noch eine interessante Frage. Gibt es eigentlich einen Algorithmus, wo rekursiv deutlich sinnvoller (also rein auf Ressourcen bezogen) ist als iterativ?
Ich seh schon, auch hier kommt man schnell off topic.

Egal, hoffe jedenfalls, dass dir das Ruhe lässt, sonst würde ich mich noch schlecht fühlen, wenn du jedesmal 'ne Ewigkeit suchst, nur weil ich dumme (nicht haltbare) Thesen in den Raum schmeisse. Mein Name ist doch schließlich Programm

Also denne,
Gruß Der Unwissende