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.