Algorithmus zur Lösung des "Halteproblems" von Turing

  • "Alan Turing hat 1936 bewiesen, dass es keinen allgemeinen Algorithmus gibt, um das Halteproblem für alle möglichen Programmeingabepaare zu lösen."

    Kann ich einen allgemeinen Algorithmus finden, um das Halteproblem für einige mögliche Eingangspaare zu lösen?

    Kann ich eine Programmiersprache (oder Sprachen) finden, in der ich für jede Art von Programm in dieser Sprache entscheiden kann, ob das Programm beendet oder für immer ausgeführt wird?

    03 October 2012
    Kaveh
5 answers
  • Kann ich einen allgemeinen Algorithmus finden, um das Halteproblem einiger möglicher Programm-Eingangspaare zu lösen?

    Ja sicher. Sie könnten beispielsweise einen Algorithmus schreiben, der "Ja, es endet" für jedes Programm zurückgibt, das weder Schleifen noch Rekursion enthält, und "Nein, es wird nicht beendet" für jedes Programm, das eine while(true) -Schleife enthält, die auf jeden Fall erreicht wird und nicht ausgeführt wird Es enthält keine break-Anweisung und "Dunno" für alles andere.

    Kann ich eine Programmiersprache (oder -sprachen) finden, in der ich für jeden Typ bin des Programms in dieser Sprache kann er entscheiden, ob das Programm beendet wird oder für immer ausgeführt wird?

    Nicht wenn diese Sprache Turing-complete ist, nein.

    Es gibt jedoch Nicht-Turing-Komplettsprachen wie beispielsweise Coq , Agda oder Microsoft Dafny , für das das Halting-Problem entscheidbar ist (und in der Tat von den jeweiligen Typsystemen entschieden wird, wodurch sie zu Gesamtsprachen werden (dh ein Programm, das möglicherweise n ot terminate kompiliert nicht)).

    08 December 2011
    EAMannAndrew
  • ausgezeichnet und (wahrscheinlich unbeabsichtigt tiefe) Frage. In der Tat gibt es Anhalteerkennungsprogramme, die mit wenigen Eingaben erfolgreich sein können. Es ist ein aktives Forschungsgebiet. Es hat sehr enge Verbindungen zu (automatisierten) Theorembewertungsbereichen.

    jedoch scheint die Informatik keinen exakten Begriff für "Programme" zu haben, die "manchmal" Erfolg haben. Das Wort "Algorithmus" ist normalerweise für Programme reserviert, die immer stehen bleiben.

    Das Konzept scheint sich deutlich von den probabilistischen Algorithmen zu unterscheiden, wo CS-Theoretiker darauf bestehen eine bekannte oder berechenbare Wahrscheinlichkeit für ihre Folge.

    Es gibt einen Begriff Semialgorithmen , der manchmal verwendet wird, aber offensichtlich ein Synonym für rekursiv aufzählbare oder nicht berechenbare.

    So nennen Sie sie hier Quasialgorithmen . Das Konzept unterscheidet sich von entscheidbar und unentscheidbar.

    könnte man sagen, dass man Quasialgorithmen nicht vergleichen kann. Tatsächlich scheint es jedoch eine natürliche Hierarchie (eine teilweise Anordnung) dieser Quasialgorithmen zu geben. Angenommen, ein Quasialgorithmus $ A $ kann das Stoppen einer begrenzten Anzahl von Eingabeprogrammen feststellen, z. ein anderer $ B $ kann das Anhalten eines Satzes $ Y $ erkennen. Wenn $ X \ Teilmenge Y $ ist, dh $ X $ ist richtige Teilmenge von $ Y $, dann ist $ B $ "leistungsfähiger" als $ A $.

    In CS scheint diese "Quasi-Algorithmus-Hierarchie" bisher meist nur informell untersucht zu werden.

    zeigt sich in der viel beschäftigten Biberforschung [1] und dem PCP-Problem [2] . Tatsächlich kann ein DNA-basierter Computerangriff auf PCP als Quasialgorithmus angesehen werden. [3] und es ist in anderen Bereichen zu sehen, die bereits erwähnt wurden, wie der Beweis des Theorems [4].

    [1] Neuer Jahrtausendangriff auf das geschäftige Beaver-Problem

    [2] Korrespondenzprobleme von Posts werden von Zhao

04 October 2012
Michael Neale
  • Ich denke, alle Antworten hier sind völlig und verpassen den Punkt völlig. Die Antwort auf die Frage lautet: Angenommen, das Programm soll anhalten, dann sollten Sie besser zeigen können, dass es stoppt. Wenn Sie nicht anzeigen können, dass das Programm schnell stoppt, sollte das Programm als sehr schlecht geschrieben und von der Qualitätskontrolle als solches abgelehnt werden.

    Ob Sie tatsächlich einen geeigneten Maschinenalgorithmus schreiben können, hängt von der Eingabe ab Programmiersprache und wie ehrgeizig Sie sind. Es ist ein vernünftiges Entwurfsziel für eine Programmiersprache, um den Abbruch leicht nachweisen zu können.

    Wenn die Sprache C ++ ist, können Sie das Tool wahrscheinlich nicht schreiben, es ist jedoch unwahrscheinlich Sie würden den Parser jemals in Gang bringen, geschweige denn die Beendigung beweisen. Für eine besser strukturierte Sprache sollten Sie in der Lage sein, einen Beweis zu generieren, oder zumindest mit bestimmten Annahmen: In letzterem Fall sollte das Werkzeug diese Annahmen ausgeben. Ein ähnlicher Ansatz wäre es, Beendigungsbestätigungen in die Sprache aufzunehmen und sie in komplexen Situationen zu verwenden, in denen das Tool den Bestätigungen vertrauen würde.

    Unter dem Strich scheint das niemand zu verstehen Es ist in der Tat möglich, ein Programm anzuhalten, weil (gute) Programmierer, die beabsichtigen, solche Anhalteprogramme zu schreiben, dies absichtlich tun und sich ein Bild machen, warum sie abbrechen und richtig handeln: Solcher Code ist absichtlich geschrieben, so dass klar ist, dass er anhält und korrekt ist und wenn ein vernünftiger Algorithmus dies nicht beweisen kann, möglicherweise mit einigen Hinweisen, sollte das Programm abgelehnt werden.

    Der Punkt: Programmierer schreiben keine beliebigen Programme, so die These der Das Stoppen des Theorems ist nicht zufriedenstellend und die Schlussfolgerung trifft nicht zu.

    15 December 2011
    Yttrill
  • Solange die Programmiersprache ausreichend komplex ist (dh wenn Turing abgeschlossen ist), gibt es immer Programme in der Sprache, die kein Programm beenden kann.

    Da mit Ausnahme der primitivsten Sprachen Turing vollständig ist (es sind nur Variablen und Bedingungen erforderlich), könnten Sie wirklich nur sehr kleine Spielzeugsprachen erstellen, für die Sie das Halteproblem lösen könnten.

    Bearbeiten: Lassen Sie mich im Hinblick auf die Kommentare genauer sagen: Jede Sprache, die Sie entwerfen könnten, für die Sie das Halteproblem lösen könnten, würde dies tun muss unbedingt Turing-unvollständig sein. Dies schließt jede Sprache aus, die eine geeignete Gruppe von Grundzutaten enthält (z. B. "Variablen, Bedingungen und Sprünge") oder, wie @ sepp2k sagt, eine generische "while" -Schleife.

    Anscheinend gibt es mehrere praktische "einfache" Sprachen (zB Theorem-Solver wie Coq und Agda). Wenn diese Ihrer Vorstellung von einer "Programmiersprache" genügen, können Sie prüfen, ob sie einer Vollständigkeit genügen oder ob das Halteproblem für sie lösbar ist.

    08 December 2011
  • Betrachten Sie einige formale Theorien $ T $. Betrachten Sie TMs mit Beweisen in $ T $, die sie anhalten / nicht anhalten. Dann können wir entscheiden, ob ein bestimmtes TM-Proof-Paar angehalten wird, indem der Proof überprüft wird. (Die Beispiele in der Antwort von sepp2k sind Sonderfälle.)

    Das ist ziemlich trivial. Wenn wir die Vereinigung eines c.e. Teilmenge des Anhaltens von TMs und eines beliebigen c.e. Untermenge von nicht haltenden TMs wird das Ergebnis aus einer Menge von TMs bestehen, für die das Halteproblem entscheidbar ist (beide Maschinen parallel ausführen, wenn der erste den TM anhält; wenn der zweite akzeptiert, hält der Computer nicht an). Dies führt jedoch nicht zu interessanten Sprachen.

    Der Grund ist einfach: In der Praxis ist es uns normalerweise egal, ob ein Programm an einer bestimmten Eingabe anhält, sondern wann es anhält In diesem Fall haben wir einen universellen Quantifizierer, der nicht verifiziert werden kann, sobald Programme ausdrucksstark genug sind. Wie ausdrucksstark Eine sehr geringe Aussagekraft reicht aus (z. B. $ \ mathsf {ALogTime} $). Sobald die Programme leistungsfähig genug sind, um auszudrücken, wenn eine gegebene Zeichenfolge $ c $ eine Stopping-Berechnung einer Turing-Maschine $ M $ für eine leere Eingabe (ein vollständig syntaktisches Problem, das ziemlich leicht zu lösen ist) ist, dann das Stoppproblem für diese Programme werden unentscheidbar.

    03 October 2012
    Kaveh