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

[Robert Marquardt]

Es gilt nicht nur das jeder rekursive Algorithmus ein iteratives Aequivalent hat, sondern auch umgekehrt.
Der Beweis kann einfach ueber eine von-Neumann-Maschine gefuehrt werden.
Die von-Neumann-Maschine ist vollstaendig, sprich es koennen alle Algorithmen auf ihr implementiert werden.
Jeztz muss nur in einer rein rekursiven (Lisp) und in einer rein iterativen (z. B. Pascal Subset) Sprache eine von-Neumann-Maschine implementiert werden und fertig ist der Beweis.

Ich stelle fest das ich in den Achzigern der Studiengang Informatik besser war.
Ich lege allen Anfaengern Compilerbau ans Herz, damit man in voller Konsequenz begreift was XML eigentlich ist.

[glkgereon]

Zitat:

Zitat von Robert Marquardt

Ich lege allen Anfaengern Compilerbau ans Herz, damit man in voller Konsequenz begreift was XML eigentlich ist.

Gerne. Hast du ein Tipp für ein Buch oder ähnliches?

(Ich hab hier die "Praxisorientierte Einführung in den Compilerbau" von Baeumle und Alenfelder...aber die finde ich doch noch etwas abgehoben...)

[Der_Unwissende]

Zitat:

Es gilt nicht nur das jeder rekursive Algorithmus ein iteratives Aequivalent hat, sondern auch umgekehrt.

Stand nie zur Debatte, der umgekehrte Weg, also iterativ -> rekursiv ist ja schließlich trivial. Aber (auch das wurde schon erörtert),

Zitat:

Jeztz muss nur in einer rein rekursiven (Lisp) und in einer rein iterativen (z. B. Pascal Subset) Sprache eine von-Neumann-Maschine implementiert werden und fertig ist der Beweis

stimmt so natürlich überhaupt nicht. Es fehlt a) der Beweis, dass dein Von-Neumann-Rechner vollständig ist und natürlich dass du mit Lisp und dem Pascal Subset jeden Algorithmus implementieren kannst.
Ansonsten kann ich auch einfach sagen, dass es keine NP vollständigen und damit natürlich auch keine NP schweren Probleme mehr gibt, denn ein Quantencomputer hat gleichzeitig 0 und 1 in jedem Qubit stehen. Ist aber kein Beweis (der echte Beweis ob NP <> P ist, ist immerhin mit 10000$ dotiert, eins der 10 schwersten mathematischen Probleme).

Grundsätzlich kann man jedenfalls mit Beweisen, die auf einem Rechnermodell aufbauen nur maximal zeigen, dass etwas gleichmächtig mit dem Rechnermodell ist. Wenn du also sagst, dass jeder Algorithmus sich sowohl rekursiv als auch iterativ lösen lässt, so stimmt das nur für berechenbare Algorithmen. Ist jetzt sicher Definitionssache, ob man etwas was nicht berechenbar ist noch als Algorithmus durchgehenlassen kann oder nicht. Aber wenn es ein Problem gibt, dass sich iterativ formulieren lässt, jedoch als nicht berechenbar gilt, dann musst du auch dafür zeigen, wie man es in rekursion überführt. Das eigenltiche Problem ist und bleibt eigentlich nur diese Bijektion. Wenn also jmd. einen Algorithmus postet, der zeigt wie man deterministisch eine Funktion die Rekursiv ist in eine Iterative überführt und natürlich die Umkehrabbildung, dann ist das ein eideutiger Beweis (und der dürfte etwas weniger trivial sein als einfach über CPU oder Rechnermodell zu sprechen). Andere Ansätze sind (meiner Ansicht nach) weiterhin, sich auf berechenbare Probleme (total rekursive) zu beschränken. Da lässt ja schon der Name total rekursiv vermuten, dass sich all die Probleme rekursiv lösen lassen, die Frage ist dann halt ob es genau so iterativ gilt.

Zu den Dingen wie

Zitat:

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

möchte ich auch noch was sagen, kommt aber in neuen Beitrag.

[Flocke]

Zitat:

Zitat von alzaimar

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.

Bei der ganzen Diskussion fehlt mir zunächst einmal die Definition: "was ist rekursiv?"

Sicher kann ich Quicksort ohne eigenen Funktionsaufruf hinschreiben, indem ich von den zwei Teilsegmenten einen auf einen Stack lege und mit dem zweiten direkt weitermache. Nichtsdestotrotz ist der Algorithmus rekursiv, denn das Problem wird dadurch gelöst, dass man auf zwei kleinere Teilabschnitte dasselbe Verfahren anwendet. Ob ich das nun über den CPU-Stack löse (Aufruf) oder den Stack selbst implementiere ändert nichts an der Verfahrensweise des Algorithmus.

Du (aber nicht alleine) hattest in dem anderen Thread ja mal als Beweis angeführt, dass eine CPU immer iterativ arbeitet und somit, sofern jeder rekursive Algorithmus implementiert werden kann, die Übersetzung in eine (iterative) Maschinensprache beweist, dass er iterativ ausgeführt werden kann. Ich hatte dann ja eine kleine rekursive Assemblerroutine hingeschrieben.

Allerdings ist es hier doch nur eine Schreibweise. Einen Unterschied darin zu sehen, ob eine Routine sich mit "call" selbst aufruft oder die Werte mit "push" auf den Stack legt und dann mit "jmp" wieder zum Start springt, ist doch eigentlich Haarspalterei.

Zurück zum Thema: für mich kommt es also nicht auf die Implementierung an sondern auf die Funktionsweise. Und hier ist jeder Algorithmus rekursiv, der nach "Divide and Conquer" verfährt und zur Lösung des Problems wieder den Algorithmus selbst auf Teilbereiche anwendet.

(los, zerreisst mich :mrgreen: )

[Robert Marquardt]

Zitat:

Zitat von Der_Unwissende

stimmt so natürlich überhaupt nicht. Es fehlt a) der Beweis, dass dein Von-Neumann-Rechner vollständig ist und natürlich dass du mit Lisp und dem Pascal Subset jeden Algorithmus implementieren kannst.

a) muss man in weiterfuehrender Literatur nachschlagen.
Das ich fuer Lisp oder das Pascal-Subset etwas beweisen muss ist hingegen nicht noetig.
Die implementierte Maschine fuehrt ja eine eigene Sprache aus.
Die Paarung rekursive Maschine mit beliebigem Programm ist rekursiv und die Paarung iterative Maschine mit beliebigem Programm ist iterativ.
Dafuer ist halt das Studium da. Man muss sich mit hoeherer Mathematik beschaeftigen.

[brechi]

Muss Flocke auch zustimmen.
Durch Hilfe mit einem Stack kann man sehr wohl die meisten (alle) rekursiven Funktionen in iterative umprogrammieren. Aber vielleicht sollte man mal schaun wie rekursiv und iterativ definiert sind. Hab jetzt nicht nachgeschaut aber für mich ist iteraritv wenn das Problem in kleine Teilprobleme zerlegt wird und diese nacheinander bearbeitet werden, und rekursiv wenn man vorherige berechnungen später wieder aufnimmt, also verschachtelt. D.h. form man einen rekursiven Alg in einen iterariven mit hilfe eines eigenen Stacks durch, bleibt er wie Flocke sagt in dem Fall rekursiv, auch wenn die eigentliche Funktion selbst nicht mehr aufgerufen wird.
Ist aber ein rekursiver Alg nur rekursiv wenn er sich selbst aufruft, dann kann man den immer mit einem eigenen Stack in einen iterativen umwandeln.

[Phoenix]

Zitat:

Zitat von Der_Unwissende

Zitat:

Zitat:

Zitat von Robert

Jeztz muss nur in einer rein rekursiven (Lisp) und in einer rein iterativen (z. B. Pascal Subset) Sprache eine von-Neumann-Maschine implementiert werden und fertig ist der Beweis

stimmt so natürlich überhaupt nicht. Es fehlt a) der Beweis, dass dein Von-Neumann-Rechner vollständig ist und natürlich dass du mit Lisp und dem Pascal Subset jeden Algorithmus implementieren kannst.

Dem ist nicht so. Natürlich stimmt das.

Wir zäumen gerade das Pferd von der falschen Seite auf. Korrekt wäre es so:

Nehmen wir mal die grundlegenden Fakten der theoretischen Informatik zur Hand:
1.) Jeder Computer lässt sich durch eine Turing-Maschine simulieren.
2.) Was nicht mit einer Turing-Maschine lösbar ist ist mit einem Rechner nicht lösbar (siehe Halteproblem).
3.) Eine Turing-Maschine kann nur folgendes: Lesen, Schreiben und den Kopf auf dem Band um ein(!) Feld bewegen.

Das bedeutet schonmal: Mächtiger als eine universelle Turing-Maschine geht mit einem Computer nicht. Aus Punkt 3 ergibt sich schlussendlich, dass eine Turing-Maschine ausschliesslich iterativ vorgehen kann (sie erlaubt keinerlei Sprünge).

Oder andersrum: Jede Turing-Vollständige Programmiersprache ist gleich mächtig. Das bedeutet das eine Turing-Vollständige Programmiersprache die keine Rekursion kennt gleich mächtig ist wie eine, die Rekursion kennt. Das bedeutet beide können das gleiche Leisten und das heisst jede Rekursion muss auch Iterativ lösbar sein (Ob man eine Lösung findet oder gar ohne Brute-Force finden kann ist eine andere Sache, aber es muss zumindest eine geben).

Es gibt dann weiterhin Beweise dass sich alle Turing-Programme auch in GOTO-Programmierung (also mit dem 'Feature' von Sprüngen, das die Turing-Maschine nicht bietet) lösen lassen und umgekehrt. Weiterhin ist dann bewiesen dann GOTO-Programme auch WHILE-Berechenbar sind und umgekehrt und so baut sich dann Stück für Stück der Umfang der heutigen Programmiersprachen auf.

[Robert Marquardt]

Turing nicht von Neumann. Der Mann hat recht.

Meine Argumentation geht so:
Die Menge der Turingprogramme umfasst alle Programme.
Die Menge der Tupel Turingprogramm und iterativ implementierte Turingmaschine ist offensichtlich gleichmaechtig und iterativ.
Die Menge der Tupel Turingprogramm und rekursiv implementierte Turingmaschine ist offensichtlich gleichmaechtig und rekursiv.
Mithin ist der Beweis angetreten das alle Programme rekursiv und iterativ implementiert werden koennen. Allein durch die Wahl der ausfuehrenden Turingmaschine.

[kopernikus]

Der im ersten Beitrag angegebene Quelltext für die iterative Berechnung der Ackermann-Funktion enthält noch einen kleinen Fehler, der sich allerdings nur bei j=m=0 auswirkt. Es fehlt eine Initialisierung des Arrays place auf -1.

Mit ein paar Schönheitskorrekturen muss es heißen:

Delphi-Quellcode:

function ack (n,m : int64): int64;
var
   value,place : array of int64;
   k : integer;
begin
  result:=0;
  if n=0 then result:=m+1
  else begin
    setlength(value,n+1);
    setlength(place,n+1);
    for k:=0 to n do place[k]:=-1;
    value[0]:=1;
    place[0]:=0;
    repeat
      inc(max);
      inc(value[0]);
      inc(place[0]);
      for k:=0 to n-1 do begin
        if place[k]=1 then begin
          value[k+1]:=value[0];
          place[k+1]:=0;
          if k<>n then break;
          end
        else begin
          if place[k]=value[k+1] then begin
            value[k+1]:=value[0];
            inc(place[k+1]);
            end
          else break;
          end;
        end;
      until place[n]=m;
    result:=value[0];
    end
  end;

[gammatester]

Zitat:

Zitat von kopernikus (Beitrag 1208073)

Der im ersten Beitrag angegebene Quelltext für die iterative Berechnung der Ackermann-Funktion enthält noch einen kleinen Fehler, der sich allerdings nur bei j=m=0 auswirkt. Es fehlt eine Initialisierung des Arrays place auf -1.

Was ist j? Bei Dir gibts das nicht. Meinst Du mit den Originalvariablen i=j=0? Der Fall ist aber behandelt mit

Delphi-Quellcode:

If i = 0 Then
    Result := j + 1