Tool das Iteration in Rekursion (oder umgekehrt) umwandelt

[peterchen]

Prinzipiell kannst du mit der Hilfe eines Stacks einen rekursiven Algorithmus in einen iterativen umwandeln - z.B. wenn du auf einer Architektur arbeitest, die Rekursion nicht unterstützt. Andererseits ist das noch keine "echte iterative alternative", sondern die "Fortsetzung von Rekursion mit anderen Mitteln".

[Jester]

Gerard schrieb:

klar ist das möglich, alles was ein mensch kann kann theoretsich auch ein pc es ist nur eine frage des aufwands.
der aufwand wird nicht klein sein bei den ganzen irrwegen in der c++ syntax und das ergebnis wird nicht so schön wie vom menschen

Das mag zwar so sein... wobei man darüber auch diskutieren könnte. Aber es gibt Probleme, die sind auch für Menschen nicht entscheidbar, und zwar mathematische/algorithmische Probleme bei denen nachgewiesen ist, daß sie nicht entscheidbar sind.

[Bashar]

Die Erkenntnis, dass man nicht für beliebige Programme entscheiden kann, ob sie rekursiv oder iterativ ablaufen, bringt uns doch an der Stelle überhaupt nichts. Real existierende Programme bilden schließlich nur eine verschwindende Teilmenge aller prinzipiell möglichen Programme. Wobei, das unterstelle ich hier mal, nur ein noch viel verschwindend kleinerer Anteil realer Programme in einem Stil geschrieben ist, der es unmöglich macht, diese Entscheidung zu treffen.

[Gast]

klar ist das möglich, alles was ein mensch kann kann theoretsich auch ein pc es ist nur eine frage des aufwands.

Ein Mensch kann es für beliebige Algorithmen und Funktionen auch nicht. Und das sind nicht nur exotische Ausnahmefälle.

Die Erkenntnis, dass man nicht für beliebige Programme entscheiden kann, ob sie rekursiv oder iterativ ablaufen, bringt uns doch an der Stelle überhaupt nichts.

Doch die bringt uns weiter. Aus ihr folgt direkt, dass ein solches allgemeines Tool unmöglich ist. Allgemeine Frage, allgemeine Antwort.

So könntest du auch die ganze Theoretische Informatik und Berechenbarkeitstheorie bis hin zum Unvollständigkeitssatz anzweifeln. Das sind bzw. da werden nur solch allgemeine (unentscheidbarkeits) Aussagen gemacht.

Oder bist du vielleicht auch der Meinung, dass das Halteproblem prinzipiell lösbar ist und man die Ausnahmen einfach ignorieren sollte weil sie angeblich sowieso nie bis selten vorkommen ?

Wundert mich eigentlich, dass grade von dir (Bashar) ein solcher Einwand kommt.

[Jester]

Naja, ganz unbegründet ist Bashars Einwurf auch nicht. Wenn wir uns auf eine geeignete Teilmenge einigen, dann wird es schon deutlich leichter das zu entscheiden.

Und zwar auf Funktionen die, wenn sie rekursiv sind sich selbst direkt aufrufen. Das ist zwar immer noch nicht 100% entscheidbar, aber wenn wir unsere Definition noch soweit anpassen, daß wir sagen, wenn in einer Funktion ein Aufruf ihrer selbst steht, dann ist die Funktion rekursiv, dann wird es mit einem mal sehr leicht entscheidbar.
Man muß ja nur den Text durchlesen und nachschauen, ob die Funktion aufgerufen wird.

Gut, warum diese Einschränkung? Und warum so?

Also, den direkten Rekursionsaufruf, weil man es durch durchlesen der Funtkion ganz einfach nachschauen kann. Man müßte halt noch prüfen, daß keine andere überladene Funktion aufgerufen wird, aber das kann der Compiler auch. Also ist es möglich.

Warum die Definition, daß es rekursiv ist, wenn der Aufruf im Text vorkommt?

void CallMe()
{
bool DoIt = // Code

if(DoIt) CallMe()
}

Es ist nicht sicher, ob DoIt jemals wahr wird (es ist nicht entscheidbar). Aber in den meisten Fällen wird so eine Rekursion, die keine ist nicht auftreten, das wäre dann ja ein Programmierfehler... und die Programme verifizieren wäre vielleicht doch ein noch größerer Aufwand.

Auf diese Art und Weise erhalten wir jedenfalls mal eine Definition von Rekursion, bei der entscheidbar ist, ob die Funktion rekursiv ist oder nicht.

Aber wie man die jetzt auflösen könnte... ist mir ein Rätsel. Aber das ist wenn ich mich recht entsinne auf jeden Fall berechenbar.

MfG Jester

[Bashar]

space:

Doch die bringt uns weiter. Aus ihr folgt direkt, dass ein solches allgemeines Tool unmöglich ist. Allgemeine Frage, allgemeine Antwort.

Wie wärs mit Allgemeine Frage - Spezielle Antwort? Wenn ein Problem sich im Allgemeinen als unlösbar herausstellt, ist das kein Grund, die Arme zu verschränken und sich zurückzulehnen. Es kann ja im speziellen Fall immer noch zu lösen sein. Beispielsweise ist Tail Call Elimination eine Form, Rekursion in Iteration umzuwandeln.

Die Wortwahl "Tool" impliziert dabei, dass es um praktisch vorkommende Probleme geht, die auch mal zulassen, dass keine Lösung gefunden wird. Wissenschaftlich würde man dagegen vielleicht "allgemeingültiges Verfahren" sagen.

Oder bist du vielleicht auch der Meinung, dass das Halteproblem prinzipiell lösbar ist und man die Ausnahmen einfach ignorieren sollte weil sie angeblich sowieso nie bis selten vorkommen ?

Kommt drauf an wie man Lösung definiert. Das Halteproblem ist unlösbar, wenn man für jedes mögliche Eingabeprogramm eine eindeutige Entscheidung fordert. Was, wenn ich diese Forderung fallenlasse und sage, dass die drei Antworten Ja, Nein und "Weiß nicht" zugelassen sind?

[Jester]

Das kann man so nicht beantworten...
Du müßtest erst definieren, wann welche Antwort kommt.
Je nachdem kann es entscheidbar sein oder auch nicht.

[Bashar]

Jester schrieb:

Du müßtest erst definieren, wann welche Antwort kommt.

Ich dachte da sei offensichtlich. JA und NEIN, wenn das Programm aufgrund was für Berechnungen auch immer zu einem eindeutigen Schluss kommt, und WEISS NICHT, wenn es das -- aus was für Gründen auch immer -- nicht tut.

[Jester]

Das Problem ist doch, ab wann soll das Programm denn jetzt sagen weiß nicht?

Man könnte ja das Programm einfach laufen lassen, wenn es terminiert geben wir ja aus. Problem, was wenn es lange dauert. Ist das dann ein weiß nicht, oder ein nein?

Wie entscheidet das Programm, ob es was rauskriegt oder nicht?
Und nein, die Ausgabe ist auch nicht offensichtlich:
return WEISS_NICHT;
wäre wohl eine korrekte Implementierung, so wie Du das beschrieben hast.

Genau da hängt es nämlich, wie entscheidet das Programm, ob es was weiß oder nicht?

[Bashar]

Vielleicht genauso wie ein Mensch das machen würde. Oder hast du noch nie eine Endlosschleife gesehen? Ein Aufgeben kann aus verschiedensten Gründen passieren. Vielleicht hat es eine bestimmte Schwelle an eigenem Resourcenverbrauch (Speicher oder Rechenzeit) überschritten.

Wenn man das zu überprüfende Programm einfach simulativ ablaufen lassen würde, könnte man natürlich immer nur JA oder WEISS NICHT als Ergebnis erhalten.

Pauschal WEISS NICHT zurückzugeben wär natürlich eine korrekte Implementierung. Aber keine besonders gute oder nützliche.