Zitat:
Ein Spezialfall der Rekursion ist die primitive Rekursion
Schön, damit wären wir wieder am Ausgangspunkt (glaube ich). Denn was ist die Alternative zu primitiver Rekursion? Richtig, nü-rekursive Funktionen, ergo Ackermann.
Eigentlich glaube ich ist es auch vollkommen egal ob man nun jede rekursive Funktion überführen kann oder nicht, ein Beweis dürfte für die Ackermann so gut wie unmöglich sein. Immerhin ist es nicht mal klar, ob diese Funktion immer terminiert. Also hier kann man sogar das ganze auf ihre Endlichkeit beschränken, das Ergebnis sollte für jede Eingabe immer gleich sein.
Was die Argumentation mit der CPU angeht, damit es ein Beweis wäre, müsste natürlich auch erstmal gezeigt werden, dass
a) die CPU nur iterativ arbeitet (ok, nehmen wir doch mal an dass das trivial gegeben wäre) aber auch
b) sich jeder Rekursive Algorithmus durch eine CPU berechnen lässt.
Das sollte schon deutlich schwerer sein. Ich schmeiß jetzt mal (ohne weiter drüber nachzudenken) Halteproblem eines Rekursiv laufenden Programms in den Raum. Na gut, ist glaube ich ein sehr schlechtes Beispiel, immerhin Semi-Entscheidbar (oder?)
Aber wenn es einen nicht entscheidbaren Algorithmus gibt der rekursiv läuft (und bei überabzählbar vielen wäre das wohl keine Kunst), dann wäre dies schon mal ein Problem das keine CPU berechnen kann.
Kommen wir also zur Einschränkung, dass eine CPU alle berechenbaren Probleme iterativ lösen könnte. Und damit auch schon zu den Grenzen einer realen CPU und künstlichen Modellen wie den Primitiv-Rekursiven Funktionen, dem Lambda-Kalkül und natürlich der guten alten Turing-Maschine (und wohl weiteren). Die sind wohl ohne Frage mächtiger als jede CPU es je sein wird (sorry an alle die eh nur noch Bahnhof verstehen).
Kurzum, es wird wohl nichtmal jede entscheidbare Funktion durch eine CPU berechenbar sein (ok, es gibt nur abzählbar viele, aber die Menge dieser Funktionen dürfte sich wohl bijektiv auf die Menge der natürlichen Zahlen abbilden lassen). Also gibt es abzählbar viele Probleme (wohl auch unendlich), für die dieser Beweis nicht gilt. Damit stellt sich die Frage ob es irgendeinen Sinn macht so zu argumentieren (fand die Argumentation gar nicht schlecht, bitte nicht falsch verstehen). Die Verallgemeinerung dass jeder Rekursive Algorithmus sich iterativ berechnen lässt (implizit vorrausgesetzt er ist berechenbar) kann nicht auf Eigenschaften einer CPU zurückgeführt werden.
Eine andere Sache ist, wen interessiert eigentlich genau ob sich nun jede Funktion von rekursiv nach iterativ überführen lässt? Denke mal hier ist es mehr als out of topic, aber sicherlich eine interessante (vielleicht schon lange gelöste) Frage der Theoretischen Informatik.
By the way, mich würde die Antwort interessieren (nicht der Beweis
)