Zitat:
Die Rekursion unterstützt dich nur bei der Bildung eines Stacks und vereinfacht so die Speicherung der Variablen
Mag ja sein, aber das ist doch gar nicht das worum es geht. Die Frage ob sich jeder rekursive Algorithmus auch iterativ lösen lässt kann nur für ein sehr allgemeines Rechnermodell beantwortet werden. Also müsste schon jmd. den konkreten Beweis antreten, dafür gäbe es wohl viele Wege
1) Für jeden (der überabzählbar vielen) Algorithmen ein iteratives Pendant aufzeigen - natürlich unmöglich
2) Eine Turingmaschine bauen, die rekursive Algorithmen in iterative überführt (hier frage ich mich ob man sich dann noch auf berechenbare rekursive Funktionen beschränken muss? Schließlich würde die TM ja nur überführen und nicht das erzeugte berechnen)
3) Die Einschränkung auf berechenbare Funktionen hinnehmen und dann nochmal zeigen (wurde definitv schon längst bewiesen), dass die Turing-Berechenbaren Funktionen oder (nach Church) die Menge der intuitiv berechenbaren Funktionen Äquivalent ist zu der Menge der Nü-Rekursiven Funktionen (da hätten wir natürlich auch Ackermann drin).
3) ist mir während unserer Diskussion einfach mal nicht eingefallen, aber eigentlich ist es das (für total rekursive Funktionen) doch schon. Denn alle diese Funktionen sind nach der (unbewiesenen) Churchen These iterativ durch die Turingmachine berechenbar. Und ich weiß noch, dass irgendwer gezeigt hat, das Lambda-Kalkül, Nü-Rekursive-Funktionen (Primitiv-Rekursiv + Ackermann) und Turingberechenbar gleichmächtig sind (und es eine paarweise Bijektion gibt).
Ja, ist natürlich sehr Argumentativ und immer noch kein Beweis, aber hier stösst man ja auch an das Problem, welche Funktionen überhaupt intuitiv berechenbar sind. Ich glaube es gibt weder einen Beweis, noch ein Gegenbeispiel für die Churche These, aber das machts ja nicht leichter.
Das es Algorithmen gibt, die jedes Programm (das für und auf einem PC u.ä. entwurfen wurde) ist klar, aber es ging ja um allgemeingültig. Werd mir vielleicht wirklich mal die Beweise durch googlen anschauen oder irgendwie mal wieder an ner Uni nen Prof der TI fragen oder so. Hm, hab doch noch irgendwo den Cormen, ob da auch was drin war zu dem Thema?
Na ja, irgendwo wird sich schon was dazu finden lassen.