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

[alzaimar]

Die Ackermannfunktion ist ein Paradebeispiel für die Eleganz der Rekursion und wird hier im Forum immer wieder gerne als Beispiel dafür genommen, das nicht jede rekursive Funktion in ein iteratives Äquivalent überführt werden kann (was Quatsch ist).

Das hat mir einfach keine Ruhe gelassen. Bevor ich nun die Lösung präsentiere, hier zunächst die 'klassische Defintion':

Delphi-Quellcode:

Function Ack(m, n: Integer): Integer;
Begin
  If m = 0 Then
    result := n + 1
  Else If n = 0 Then
    Result := Ack(m - 1, 1)
  Else
    Result := Ack(m - 1, Ack(m, n - 1))
End;

Sinn und Zweck dieser Funktion ist sehr gut im Wiki erklärt.

Und für Alle, die es nicht glauben wollten, ist hier eine rein iterative Variante, die ich... nee, nicht selbst entwickelt habe... sondern nach langem Suchen im Internet gefunden habe.
Sie stammt aus einem Artikel über die Programmiersprache ICON.

Delphi-Quellcode:

Function IconAckermann (i, j: Integer): Integer;
Var
  Value,
  Place : Array Of Integer;
  k : Integer;

Begin
  If i = 0 Then
    Result := j + 1
  Else Begin
    setLength(Value, i + 2);
    SetLength(Place, i + 2);
    Value[1] := 1;
    Place[1] := 0;
    Repeat
      inc(Value[1]);
      inc(Place[1]);
      For k := 1 To i Do Begin
        If Place[k] = 1 Then Begin
          value[k + 1] := value[1];
          place[k + 1] := 0;
          If k <> i Then Break;
        End
        Else Begin
          If place[k] = value[k + 1] Then Begin
            value[k + 1] := value[1];
            inc(Place[k + 1]);
          End
          Else
            Break;
        End;
      End;
      If Place[i + 1] = j Then Begin
        Result := Value[1];
        Exit
      End;
    Until False;
  End
End;

[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

[alzaimar]

Zitat von Der_Unwissende:

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.

Für Dich (und hier) vielleicht nicht. Ich hab mir einen Beweis ausgedacht, der darauf beruht, das ich ein Programm habe, das die Aufrufreihenfolge einer rekursiven Funktion zu festen Inputparametern erzeugt und diese iterativ abarbeitet, also einen Compiler und einen Interpreter.

Es gibt übrigens durchaus Verfahren, die diese Überführung automatisieren. Bei den Recherchen zu dem Ackermann stiess ich auf solch ein Verfahren (googel mal nach "Ackermann iterativ", etwas weiter hinten fangen dann die interessanten Skripte an).

Zitat:

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.

Mach mal nur weiter so . Ich mach hier sowieso nur, was mir Spass macht.

Deine Skepsis ist übrigens sehr weit verbreitet. Sämtliche Skripte behaupten die Überführbarkeit jedes Rekursiven in einen iterativen Algorithmus. Fast alle Studenten glauben das nicht. Beweise sind dünn gesäht, fast so dünn wie iterative Achermännchen.

Zitat:

Also denne,

bis denne

Mark

[jim_raynor]

Das würde mich mal interessieren, wer behauptet, dass man nicht jede Funktion iterativ lösen kann. Natürlich kann man das. Die Rekursion unterstützt dich nur bei der Bildung eines Stacks und vereinfacht so die Speicherung der Variablen. Dieses müsstest du in einer iterativen Lösung einfach nur nachbilden (was zugegebener maßen nicht immer einfach ist). Aber ganz ehrlich. Die rekursive Variante finde ich wesentlich eleganter

[Der_Unwissende]

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.

[mschaefer]

N´abend

Zitat von jim_raynor:

Das würde mich mal interessieren,
wer behauptet, dass man nicht jede Funktion iterativ lösen kann. Natürlich kann man das.

Ja das würde ich behaupten.
1. Das ist immer dann nicht möglich, wenn die Funktionen in einem Wertebereich nicht definiert sind.
-> Iteration lauft in eine undefinierten Bereich und bricht ab <- Fehler

2. Dann wenn Funktionen über Wertebereiche immer den gleichen Wert liefern, also nicht stetig sind.
Zum Beispiel bei sogeanannten Treppenfunktionen.
-> Im ungünstigsten Fall läuft die Iteration sich fest <- hört nie auf
-> Im wenig günstigen Fall läuft sie sehr langsam bis zur Lösung

Nun allgemeine Funktionssolver sind eine mathematisch doch recht komplexe Materie, das braucht Zeit.
Tja nun weist Du wer (einer davon), hilft Dir aber wahrscheinlich nicht wirklich weiter...

Grüße // Martin

[alzaimar]

Ich glaub, er meint 'rekursive Funktion/Prozedur'.
Ansonsten hast Du natürlich Recht. Viele Funktionen sind nicht iterativ lösbar, weil sie einfach nicht lösbar sind.

[mschaefer]

Ok, dann ist das korrekt, letzlich ist die Rekursion lediglich eine Verfahrensweise der Iteration. Tja Mark, Du hast da ja ein interessantes Hobby. Da gibt es bestimmt bald Gelegenheit sich mit Hagen über mathematische Algorithmen auszutauschen, sozusagen in der "Knobelelite" !

Schönes Wochenende Euch // Martin

[Phoenix]

Also.. Fakt ist, das jede Rekursive Funktion auch Iterativ lösbar ist. Das ist sogar mathematisch bewiesen worden, ich hab die Quelle nur nicht zur Hand. Werde aber am Montag gleich meinen Prof fragen, der wird wissen wo das steht. (Oder, was wahrscheinlicher ist, mir einen Tip geben wie ich es selber beweisen soll... ).

Was im Allgemeinen dazu auch gilt: Die Rekursive Lösung ist in der Regel eleganter und einfacher, die Iterative in der Regel performanter weil nicht so Stack-Lastig und dadurch besser optimierbar.

[alzaimar]

Zitat von mschaefer:

... Du hast da ja ein interessantes Hobby. ...

Einerseits Hobby, andererseits Beruf. Es ist einfach eminent wichtig, über Algorithmen, Möglichkeiten ('Was geht?'), NP-komplette Probleme, Suchverfahren etc. zumindest eingermassen Bescheid zu wissen. Bedauerlicherweise liegt der Schwerpunkt in dem Informatikstudium nicht hier. Das merke ich, wenn Studenten oder Berufsanfänger ein Subsystem implementieren sollen, und bei Suchverfahren grundsätzlich durchiterieren. Die haben noch nie was von Binary Search oder Hashtabellen gehört. Oder irgendwas dämlicherweise rekursiv implementieren und sich dann wundern, wenn ihnen der Stack um die Ohren haut.

So wie der Maschinenbauer das Grundhandwerk beherrschen sollte, muss das ein Informatiker auch.

Zurück zum Thema:
Ich hab mal eine iterative Quicksortvariante geschrieben, weil ich es einfach mal wissen wollte (so wie beim Ackermännchen):
Bei kleinen N ist die rekursive Implementierung doch schneller, bei großen N die Iterative.