Wie überprüfen Sie, ob zwei Algorithmen für Eingaben dasselbe Ergebnis liefern?

17

Wie können Sie überprüfen, ob zwei Algorithmen (z. B. Merge Sort und Naive Sort) für jede Eingabe dasselbe Ergebnis liefern, wenn die Menge aller Eingaben unendlich ist?

Update: Vielen Dank, Ben, für die Beschreibung, wie dies im allgemeinen Fall nicht algorithmisch möglich ist. Daves Antwort ist eine großartige Zusammenfassung sowohl algorithmischer als auch manueller Methoden (abhängig vom menschlichen Verstand und der Metapher), die nicht immer funktionieren, aber sehr effektiv sind.

computability formal-methods software-engineering software-verification Andres Riofrio
quelle
5
Wie Yuval sagte, gibt es keine Prozedur, die das für zwei beliebige Programme bestimmen kann. Aber in einem speziellen Fall wie Ihrem Beispiel können Sie es beweisen: Wenn Sie beispielsweise beweisen, dass beide Algorithmen eine sortierte Sequenz zurückgeben und stabil sind, sind Sie fertig.
Sasho Nikolov
1
Möchten Sie eine automatische Technik / einen automatischen Algorithmus oder eine Reihe manueller Techniken?
Dave Clarke
@SashoNikolov, wenn Leistung als Teil der Ausgabe betrachtet wird, müsste man auch zeigen, dass beide in der gleichen Zeit- / Raumkomplexität arbeiten.
edA-qa mort-ora-y
1
Meinst du "checken" oder beweisen? Meinen Sie "irgendeine Eingabe" oder alle Eingaben? Was ist die Motivation und der Kontext für die Frage?
Kaveh
2
@AndresRiorio: Beweistechniken unterscheiden sich von Algorithmen, die das allgemeine Problem lösen. Zum Beispiel ist das Problem des Anhaltens nicht zu entscheiden, aber es ist sicherlich möglich, die Beendigung vieler Programme (von Hand oder mit automatisierten Heuristiken) nachzuweisen.
Raphael

Antworten:

16

Im Gegensatz zu dem, was die Neinsager sagen, gibt es dafür viele effektive Techniken.

  • Bisimulation ist ein Ansatz. Siehe zum Beispiel Gordons Artikel über Coinduction und Functional Programming .

  • Ein anderer Ansatz ist die Verwendung operationeller Theorien zur Programmäquivalenz, wie beispielsweise die Arbeit von Pitts .

  • Ein dritter Ansatz besteht darin, zu überprüfen, ob beide Programme dieselbe Funktionsspezifikation erfüllen. Es gibt Tausende von Artikeln zu diesem Ansatz.

  • Ein vierter Ansatz besteht darin, zu zeigen, dass ein Programm mithilfe von Sound- Programmtransformationen in das andere umgeschrieben werden kann .

Natürlich ist keine dieser Methoden aufgrund der Unentscheidbarkeit vollständig, aber es wurden Volumen und Arbeitsvolumen erzeugt, um das Problem anzugehen.

Dave Clarke
quelle
heu · ris · tic . [GR. εὑρίσκω "entdecken"] n. 1. Eine Technik zur Lösung eines Problems, bei der ignoriert wird, ob sich die Lösung als richtig erweisen lässt, die jedoch normalerweise eine gute Lösung ergibt oder ein einfacheres Problem löst, das die Lösung des komplexeren Problems enthält oder sich mit dieser überschneidet. 2. ( Theor. ) Ein Algorithmus, der nicht funktioniert.
JeffE
1
Bart Simpson: "Kann nicht gewinnen. Versuche es nicht."
Dave Clarke
9
@JeffE: Wenn Sie überprüfen möchten, ob zwei Algorithmen dasselbe Ergebnis liefern, führen Sie einen Proof durch. Dafür gibt es viele gute Techniken. Sicher, alle Methoden sind unvollständig, aber wen interessiert das? Goedels Unvollständigkeitssatz ist kein Grund, die Mathematik aufzugeben!
Neel Krishnaswami
3
@JeffE Nur weil es keine berechenbare Funktion gibt, mit der festgestellt werden kann, ob zwei beliebige Algorithmen dasselbe Ergebnis liefern , können Sie die Frage nicht für zwei bestimmte Algorithmen beantworten , zumal die Suche nach einem Proof nicht berechenbar ist funktion . In ähnlicher Weise gibt es eine Vielzahl von Dokumenten, die für bestimmte Algorithmen eine garantierte Beendigung nachweisen, ungeachtet der Tatsache, dass es nicht möglich ist, mechanisch zu bestimmen, ob ein beliebiger Algorithmus immer beendet wird.
Ben
2
In der Praxis ermöglichen zwei Algorithmen, die dieselbe Funktion berechnen sollen, kaum einen auf Bisimulation basierenden Äquivalenznachweis. (Bei den oben genannten Sortieralgorithmen sind die Zwischenstufen der Schleifen / Rekursionen unterschiedlich.) Ich würde sagen, dass die Verwendung einer guten alten Hoare-Logik zeigt, dass beide die gleiche Spezifikation des E / A-Verhaltens implementieren gehen.
Kai
10

Um die "Es ist unmöglich" -Aussagen etwas näher zu erläutern, hier eine einfache Beweisskizze.

Wir können Algorithmen mit Ausgabe von Turing Machines modellieren, die mit der Ausgabe auf ihrem Band anhalten. Wenn Sie Maschinen haben möchten, die anhalten können, indem Sie entweder die Ausgabe auf dem Band annehmen oder ablehnen (in diesem Fall gibt es keine Ausgabe), können Sie leicht eine Codierung erstellen, mit der Sie diese Maschinen mit der Option "anhalten oder nicht anhalten" modellieren können. Es gibt keine "Ausschuss" -Maschinen.

Angenommen , ich habe einen Algorithmus P, um zu bestimmen, ob zwei solcher TMs für jeden Eingang den gleichen Ausgang haben. Dann kann ich mit einem TM A und einer Eingabe X ein neues TM B konstruieren , das wie folgt funktioniert:

  1. Überprüfen Sie, ob die Eingabe genau X ist
  2. Wenn ja, geben Sie eine Endlosschleife ein
  3. Wenn nein, führen Sie A für die Eingabe aus

Jetzt kann ich P auf A und B ausführen . B hält nicht an X an , sondern hat dieselbe Ausgabe wie A für alle anderen Eingaben. Wenn A also nicht an X anhält, haben diese beiden Algorithmen für jede Eingabe dieselbe Ausgabe. Es wurde jedoch angenommen, dass P in der Lage ist, zu erkennen, ob zwei Algorithmen für jede Eingabe dieselbe Ausgabe haben. Wenn wir also P hätten , könnten wir feststellen, ob eine beliebige Maschine bei einer beliebigen Eingabe anhält, was das Halteproblem ist. Da das Halteproblem als unentscheidbar bekannt ist, kann P nicht existieren.

Dies bedeutet, dass es keinen allgemeinen (berechenbaren) Ansatz gibt, um zu bestimmen, ob zwei Algorithmen die gleiche Ausgabe haben, die immer funktioniert. Daher müssen Sie die Argumentation speziell auf das zu analysierende Algorithmenpaar anwenden. In der Praxis kann es jedoch berechenbare Ansätze geben, die für große Klassen von Algorithmen funktionieren, und es gibt sicherlich Techniken, mit denen Sie versuchen können, einen Beweis für einen bestimmten Fall zu erarbeiten. Die Antwort von Dave Clarke gibt Ihnen einige relevante Dinge, die Sie hier ansehen sollten. Das Ergebnis "Unmöglichkeit" gilt nur für die Entwicklung einer generischen Methode, die das Problem für alle Algorithmenpaare ein für alle Mal löst.

Ben
quelle
P
@Raphael Ja, das Argument, das ich skizziert habe, sagt nichts über ein derart eingeschränktes P aus , nur dass es kein vollständig allgemeines P geben kann. Mein Instinkt ist, dass das Stopp-Problem immer noch unentscheidbar ist, selbst wenn Sie es auf "Sortieralgorithmen" anstatt auf allgemeine Algorithmen beschränken. In diesem Fall gilt der Unmöglichkeitsbeweis immer noch, obwohl ich noch nie eine solche Behauptung gehört habe.
Ben
2
Im Allgemeinen besagt der Satz von Rice , dass es keinen berechenbaren Weg gibt, etwas über einen Algorithmus zu beweisen, sobald es mindestens einen Algorithmus gibt, der die Eigenschaft hat, die Sie zu beweisen versuchen, und mindestens einen, der dies nicht tut. Beispielsweise gibt es bei einem Algorithmus A keine berechenbare Funktion, die einen Algorithmus B als Eingabe verwendet und prüft, ob B A entspricht.
Gilles 'SO - hör auf, böse zu sein'
Es ist wichtig anzumerken, dass der Satz von Rice nur für Eigenschaften von Sprachen gilt , nicht für Turing-Maschinen (wenn Sie diese als Modell für "Algorithmus" verwenden). Wenn es möglich ist, dass zwei Turing-Maschinen existieren, die beide dieselbe Sprache erkennen, aber die eine Eigenschaft hat und die andere nicht, dann gilt das Rice-Theorem nicht, und es könnte eine allgemein berechenbare Methode zum Testen der Eigenschaft geben. Aber der Satz von Rice gilt eindeutig für diesen Fall, ja.
Ben
2

Es ist im Allgemeinen unmöglich, aber viele Einschränkungen können es möglich machen. Beispielsweise können Sie die Gleichwertigkeit von zwei Programmen mit linearem Code mithilfe von BDDs überprüfen. Die symbolische Ausführung kann viele andere Fälle behandeln.

James Koppel
quelle
1

Es ist unmöglich, einen Algorithmus zu entwickeln, der diese Gleichheit im Allgemeinen beweist. Hinweis: Reduzierung des Halteproblems.

Yuval Filmus
quelle
Es gibt viele Techniken, obwohl keine vollautomatisch sind.
Dave Clarke
Ich weiß nicht, ist möglich oder nicht, durch Ihre Antwort ist nur ein Kommentar. keine Antwort.
@ SaeedAmiri: Ich habe mich im Kontext der Antwort ein bisschen ausgearbeitet; Ich denke, es ist vollständig genug, wenn auch nicht besonders gut.
Raphael
@Raphael, Die Reduzierung, die Yuval in den Sinn kommt, ist offensichtlich, und ich glaube, OP ist sich dessen nicht bewusst, aber das IMO-Problem ist, einen Weg für Sonderfälle zu finden für den allgemeinen Fall.
2
@ SaeedAmiri: Das müssen die OP und die Wähler dann entscheiden, nicht wir.
Raphael