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

[Phoenix]

Zitat von Der_Unwissende:

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.