Gibt es eine Untergruppe von Programmen, die das Problem des Anhaltens vermeiden?

21

Ich las gerade eine weitere Erklärung des Halteproblems und dachte an all die Probleme, die ich gesehen habe und die als Beispiele angeführt sind, beinhalten unendliche Sequenzen. Aber ich verwende in meinen Programmen niemals unendliche Sequenzen - sie dauern zu lange. Alle Anwendungen der realen Welt haben Unter- und Obergrenzen. Sogar reelle Zahlen sind keine reellen Zahlen - es handelt sich um Näherungswerte, die als 32/64 Bit usw. gespeichert sind.

Die Frage ist also, ob es eine Untergruppe von Programmen gibt, die bestimmt werden können, wenn sie anhalten. Ist es gut genug für die meisten Programme. Kann ich eine Reihe von Sprachkonstrukten erstellen, mit denen ich die Haltbarkeit eines Programms bestimmen kann? Ich bin mir sicher, dass dies irgendwo zuvor untersucht wurde, daher wären alle Hinweise willkommen. Die Sprache wäre nicht vollständig, aber gibt es so etwas wie fast vollständig, was gut genug ist?

Natürlich müsste ein solches Konstrukt eine Rekursion und unbegrenzte while-Schleifen ausschließen, aber ich kann ein Programm ohne diese einfach genug schreiben.

Das Lesen von der Standardeingabe als Beispiel müsste eingeschränkt sein, aber das ist einfach genug - ich beschränke meine Eingabe auf 10.000.000 Zeichen usw., abhängig von der Problemdomäne.

tia

[Aktualisieren]

Nachdem ich die Kommentare und Antworten gelesen habe, sollte ich vielleicht meine Frage wiederholen.

Für ein bestimmtes Programm, in dem alle Eingaben beschränkt sind, können Sie bestimmen, ob das Programm anhält. Wenn ja, wie lauten die Einschränkungen der Sprache und wie lauten die Grenzen des Eingabesatzes? Die maximale Menge dieser Konstrukte würde eine Sprache bestimmen, die angehalten werden kann oder nicht. Gibt es eine Studie darüber?

[Update 2]

Hier ist die Antwort: Ja, schon 1967 von http://www.isp.uni-luebeck.de/kps07/files/papers/kirner.pdf

Dass das Stopp-Problem zumindest theoretisch für Systeme mit endlichen Zuständen gelöst werden kann, hat Minsky bereits 1967 argumentiert [4]: ​​„... jede Maschine mit endlichen Zuständen wird, wenn sie sich selbst überlassen bleibt, schließlich in eine vollkommene Periodizität fallen sich wiederholendes Muster. Die Dauer dieses sich wiederholenden Musters darf die Anzahl der internen Zustände der Maschine nicht überschreiten ... “

(Und wenn Sie sich an endliche Turingmaschinen halten, können Sie ein Orakel bauen.)

daven11
quelle
13
msgstr "unendliche Sequenzen ... dauern zu lange". Hat mich laut zum Lachen gebracht.
Bryan Oakley
3
Ich glaube, SQL92 und reguläre Ausdrücke sind Beispiele für Sprachen, die garantiert zum Stillstand kommen.
Elian Ebbing
2
Bitte poste "Update2 ..." als Antwort.
S.Lott
2
Sie müssen die Rekursion nicht ausschließen. Wenn Sie die Rekursion auf strenge Unterbedingungen der Argumente der Angerufenen beschränken, können Sie die Kündigung immer nachweisen. Dies ist eine ausreichende Voraussetzung - es sind keine "begrenzten Schleifen" oder ähnliches erforderlich, solange Sie die Nummern der Kirche verwenden.
SK-logic
1
Die Sprache Idris verwendet die abhängige Eingabe und einen Proof Checker, um zu beweisen, dass Ihre Programme vor dem Ausführen beendet werden. Es ähnelt Haskell und ermöglicht eine Rekursion, jedoch keine allgemeine Rekursion. Nur eine Rekursion, die (durch die abhängigen Typen) nachgewiesen werden kann, führt zu einem Endzustand.
Jack

Antworten:

8

Das Problem liegt nicht bei der Eingabe (bei unbegrenzten Eingaben können Sie natürlich unbegrenzte Laufzeit haben, um die Eingabe zu lesen), sondern bei der Anzahl der internen Zustände.

Wenn die Anzahl der internen Zustände begrenzt ist, können Sie theoretisch das Halteproblem in allen Fällen lösen (emulieren Sie es einfach, bis Sie zum Halten oder zur Wiederholung eines Zustands gelangen). Wenn dies nicht der Fall ist, gibt es Fälle, in denen es nicht lösbar ist . Aber selbst wenn die Anzahl der internen Zustände in der Praxis begrenzt ist, ist sie auch so groß, dass die Methoden, die sich auf die Begrenztheit der Anzahl der internen Zustände stützen, keinen Beweis für die Beendigung irgendeines anderen als der trivialsten Programme liefern.

Es gibt praktischere Möglichkeiten, die Beendigung von Programmen zu überprüfen. Drücken Sie sie zum Beispiel in einer Programmiersprache aus, die weder rekursiv noch goto ist und deren Schleifenstrukturen alle an die Anzahl der Iterationen gebunden sind, die beim Eintritt in die Schleife angegeben werden müssen. (Beachten Sie, dass die Grenze nicht unbedingt mit der effektiven Anzahl von Iterationen verknüpft sein muss. Ein Standardweg, um die Beendigung einer Schleife zu beweisen, besteht darin, eine Funktion zu haben, die von einer Iteration zur anderen und Ihrer Eingabebedingung streng abnimmt Stellen Sie sicher, dass dies positiv ist, und geben Sie die erste Bewertung als Ihre Bindung an.

Ein Programmierer
quelle
10

Überlegen Sie sich zunächst, was passieren würde, wenn wir einen Detektor zum Stoppen hätten. Wir wissen aus dem diagonalen Argument, dass es mindestens ein Programm gibt, das dazu führen würde, dass ein Detektor, der anhält, niemals anhält oder eine falsche Antwort gibt. Aber das ist ein bizarres und unwahrscheinliches Programm.

Es gibt jedoch ein anderes Argument, dass ein Stopp-Detektor unmöglich ist, und das ist das intuitivere Argument, dass ein Stopp-Detektor magisch wäre. Angenommen, Sie möchten wissen, ob Fermats letzter Satz wahr oder falsch ist. Sie schreiben einfach ein Programm, das angehalten wird, wenn es wahr ist, und für immer ausgeführt wird, wenn es falsch ist, und führen dann den Anhalten-Detektor darauf aus. Sie führen das Programm nicht aus , Sie führen nur den Stopp-Detektor für das Programm aus . Ein Stopp-Detektor würde es uns ermöglichen, eine Vielzahl offener Probleme in der Zahlentheorie sofort zu lösen, indem wir einfach Programme schreiben.

Können Sie also eine Programmiersprache schreiben, die garantiert Programme erzeugt, deren Anhalten immer bestimmt werden kann? Sicher. Es kann einfach keine Schleifen, Bedingungen und beliebig viel Speicherplatz verwenden. Wenn Sie bereit sind, ohne Schleifen, ohne "Wenn" -Anweisungen oder mit einer streng begrenzten Speichermenge zu leben, können Sie sicher eine Sprache schreiben, deren Anhalten immer bestimmbar ist.

Eric Lippert
quelle
2
Man kann die if-Anweisung haben, wenn der Sprung immer vorwärts sein muss, niemals rückwärts. Ich denke an eine eingeschränkte Teilmenge der BASIC-Sprache, wobei "GOTO X" bedeutet, dass zur Zeilennummer currentLine + X gewechselt wird und X größer als 0 sein muss. Wenn die Zeile ungültig ist, dann halt. Dies würde die Speicheranforderungen erhöhen, aber eine nicht triviale Logik zulassen. Dies entspricht wahrscheinlich einer endlichen Zustandsmaschine, bei der die Eckpunkte einen Graphen bilden und dieser Graph möglicherweise keine Zyklen aufweist, oder die FSM ist ungültig. Jeder Zustand, der eine Sackgasse darstellt, muss ein akzeptierender Zustand sein.
Job
3
Es hätte Schleifen begrenzen können - für i = 1 bis 10 zum Beispiel ebenfalls gut verhaltene Iteratoren. Gibt es also eine Klasse endlicher Probleme, die gelöst werden können? Der Satz von Fermats ist wiederum in die unendliche Folge von Real involviert. Wenn wir die Domain jedoch auf Zahlen unter 1 000 000 beschränken, wird sie angehalten.
Daven11
2
Warum nicht Bedingungen? Es scheint, dass Bedingungen ohne Sprünge gezeigt werden können, um immer
anzuhalten
2
@nikie: Natürlich ist es ein schwaches Argument. Der Punkt ist, dass ein solcher Stopp-Detektor solche Aussagen beweisen oder widerlegen kann, ohne dass er den Beweis finden muss . Die Intuition, die der Leser hier entwickeln möchte, ist, dass eine Sprache, für die ein trivialer Stoppdetektor geschrieben werden könnte, nicht einmal einfache Probleme in der Zahlentheorie wie Fermats letzter Satz oder Goldbachs Vermutung darstellen kann und daher wahrscheinlich nicht ist eine sehr nützliche Sprache.
Eric Lippert
3
@ EricLippert: Falsch. Eine solche Sprache wird Schleifen, ordnungsgemäße Speicherung und viele andere nützliche Dinge haben. Es ist möglich, fast alles darin zu codieren . Siehe, hier ist es: coq.inria.fr
SK-logic
6

Ich empfehle Ihnen, Gödel, Escher, Bach zu lesen . Es ist ein sehr unterhaltsames und aufschlussreiches Buch, das unter anderem Gödels Unvollständigkeitssatz und das Halteproblem anspricht.

Um Ihre Frage auf den Punkt zu bringen: Das Problem des Anhaltens kann entschieden werden, solange Ihr Programm keine whileSchleife (oder eine der vielen möglichen Manifestationen) enthält.

zvrba
quelle
Entschuldigung, ich habe dich falsch verstanden. Ich habe meinen Kommentar gelöscht, aber ich werde die Empfehlung von GEB wiederholen.
Programmierer
@zvrba Das steht schon seit einiger Zeit auf meiner Leseliste - wahrscheinlich ist es Zeit zum Eintauchen.
daven11
5

Für jedes Programm, das mit einer begrenzten Menge an Speicher (einschließlich Speicher aller Art) arbeitet, kann das Problem des Anhaltens gelöst werden. Das heißt, ein unentscheidbares Programm benötigt zwangsläufig immer mehr Speicherplatz.

Diese Einsicht bedeutet jedoch nicht, dass sie für Probleme der realen Welt verwendet werden kann, da das Anhalten eines Programms mit nur wenigen Kilobyte Arbeitsspeicher leicht länger dauern kann als die verbleibende Lebensdauer des Universums.

user281377
quelle
3

(Teil-) Beantwortung Ihrer Frage "Gibt es eine Untergruppe von Programmen, die das Problem des Anhaltens vermeiden?": Ja, tatsächlich gibt es. Diese Untermenge ist jedoch erstaunlich nutzlos (beachten Sie, dass die Untermenge, von der ich spreche, eine strikte Untermenge der Programme ist, die anhalten).

Die Untersuchung der Komplexität von Problemen für 'die meisten Eingaben' wird als Komplexität im allgemeinen Fall bezeichnet . Sie definieren eine Teilmenge der möglichen Eingaben, beweisen, dass diese Teilmenge die meisten Eingaben abdeckt, und geben einen Algorithmus an, der das Problem für diese Teilmenge löst.

Zum Beispiel ist das Problem des Anhaltens für die meisten Eingaben in Polynomzeit lösbar (tatsächlich in linearer Zeit, wenn ich das Papier richtig verstehe ).

Dieses Ergebnis ist jedoch aufgrund von drei Randnotizen ziemlich nutzlos: Erstens sprechen wir über Turing-Maschinen mit einem einzigen Band und nicht über reale Computerprogramme auf realen Computern. Soweit ich weiß, weiß niemand, ob dies für Computer in der realen Welt gilt (obwohl Computer in der realen Welt möglicherweise die gleichen Funktionen wie Turing-Maschinen berechnen können, wie viele Programme zulässig sind, wie lang sie sind und ob sie anhalten völlig anders).

Zweitens muss man aufpassen, was die meisten Eingaben bedeuten. Dies bedeutet, dass die Wahrscheinlichkeit, dass ein Zufallsprogramm der 'Länge' n von diesem Algorithmus überprüft werden kann, gegen 1 geht, während n gegen unendlich geht. Mit anderen Worten, wenn n groß genug ist, kann ein Zufallsprogramm der Länge n mit diesem Algorithmus fast sicher überprüft werden.

Welche Programme können mit dem im Papier beschriebenen Ansatz überprüft werden? Im Wesentlichen alle Programme, die vor dem Wiederholen eines Status angehalten werden (wobei "Status" ungefähr einer Codezeile in einem Programm entspricht).

Obwohl fast alle Programme auf diese Weise überprüft werden können, ist keines der Programme, die auf diese Weise überprüft werden können, sehr interessant und sie werden normalerweise nicht von Menschen entworfen, so dass dies überhaupt keinen praktischen Wert hat.

Dies weist auch darauf hin, dass die Komplexität von Groß- und Kleinschreibung wahrscheinlich nicht in der Lage sein wird, das Problem zu lösen, da fast alle interessanten Programme (anscheinend) schwer zu überprüfen sind. Oder anders ausgedrückt: Fast alle Programme sind uninteressant, aber leicht zu überprüfen.

Alex ten Brink
quelle
2
-1, Das ist auf so vielen Ebenen falsch ...
user281377
1
Erstens können reale Computer nichts berechnen, was eine Turing-Maschine nicht kann. Bisher hat niemand einen realistischen Computer gezeigt, der (in Bezug auf die Rechenfähigkeit) leistungsfähiger ist als eine Turing-Maschine. Zweitens, wenn ein Programm seinen Status wiederholt, wird es nicht angehalten, sodass das Problem des Anhaltens für dieses Programm und diese Eingabe behoben ist. Denken Sie daran: Das Problem beim Anhalten besteht darin, zu entscheiden, ob ein Programm bei einer bestimmten Eingabe angehalten wird oder nicht. Eine Endlosschleife ist in Ordnung, sobald Sie sie positiv erkennen. Schließlich: Es gibt eine Vielzahl nützlicher Programme, für die das Problem des Anhaltens lösbar ist: Programme, die mit begrenztem Speicher arbeiten.
user281377
Was Ihre erste Ausgabe anbelangt: Wie in der Veröffentlichung bemerkt, bewahrt das Zeigen, dass ein Berechnungsmodell vollständig ist, nicht, wie viele Programme genau angehalten werden, so dass das Ergebnis, das sie nachweisen, für andere Berechnungsmodelle nicht unmittelbar von Bedeutung ist. Ich bin mir der Vollständigkeit von Turing sehr wohl bewusst und bin mir nicht ganz sicher, warum meine Antwort "falsch" ist.
Alex ten Brink
Was Ihre zweite Ausgabe betrifft: Die Zustände, von denen ich spreche, sind nicht die gleichen wie der 'Zustand einer Maschine', von dem man normalerweise spricht (was den Zustand von allem beinhaltet, was einen Zustand haben kann), sondern der Zustand, der endliche Zustandsautomat verwendet, um die Turing-Maschine zu steuern. Dies entspricht in etwa der Codezeile, an der ein Programm zu einem beliebigen Zeitpunkt während der Ausführung arbeitet. Wenn Sie eine Codezeile wiederholen, kann der Inhalt Ihres Speichers unterschiedlich sein. Dies bedeutet also nicht, dass Sie sofort anhalten müssen. Ich werde meine Antwort aktualisieren, um dies klarer zu machen.
Alex ten Brink
@ammoQ: Nein, das Stopp-Problem ist nicht lösbar, wenn Sie von realen Systemen mit begrenztem Speicher sprechen, da dies den Aufbau eines realen Systems bedeuten würde, das Kombinationen von Zuständen verarbeiten kann. Da die Anzahl der möglichen Registerzustände in den meisten CPUs die Anzahl der Atome im Universum überschreitet, ist dies nicht möglich.
David Thornley
3

Es gibt und in der Tat gibt es Programme im wirklichen Leben, die ständig das Problem der Unterbrechung für andere Probleme lösen. Sie sind Teil des Betriebssystems, auf dem Sie Ihren Computer ausführen. Unentscheidbarkeit ist eine seltsame Behauptung, die nur besagt, dass es kein solches Programm gibt, das für ALLE anderen Programme funktioniert.

Eine Person gab zu Recht an, dass der Stopp-Proof das einzige Programm zu sein scheint, für das er nicht gelöst werden kann, da er sich wie ein Spiegel unendlich weiterverfolgt. Dieselbe Person gab auch an, dass es magisch wäre, wenn es eine Stoppmaschine gäbe, weil sie uns schwierige mathematische Probleme erklären würde, indem sie uns im Voraus mitteilt, ob der Algorithmus des Lösers anhalten würde.

In beiden Fällen wird davon ausgegangen, dass die Stoppmaschine nicht verfolgt, da es keinen Beweis dafür gibt, dass sie verfolgt. In Wirklichkeit wird jedoch das Programm, auf dem es ausgeführt wird, mit der angegebenen Eingabe verfolgt / ausgeführt.

Zumindest der logische Beweis ist einfach. Wenn es nicht mindestens den ersten Schritt nachverfolgen müsste, bräuchte es nicht die Eingabe zusammen mit dem Programm, auf dem es ausgeführt wird. Um die Informationen nutzen zu können, muss mindestens der erste Schritt nachverfolgt werden, bevor analysiert werden kann, wohin dieser Pfad führt.

Bei den in der oberen Antwort genannten schwierigen mathematischen Problemen kann man nicht schnell vorspulen, um die Antwort herauszufinden. Dies bedeutet, dass das Halteproblem so lange nachverfolgt werden muss, bis ein Muster erkennbar ist.

Das einzige praktische Argument für das Problem des Anhaltens ist, dass eine anhaltene Maschine das Ergebnis eines optimierten Problemlösers nicht schneller ermitteln kann, als der Problemlöser es beenden kann.

Es ist schwieriger, einen formellen Beweis für diese Argumentation zu liefern, und obwohl ich glaube, dass ich es könnte, wird der Versuch, es jemandem von einer Akademie zu erklären, dazu führen, dass sie einen Affen wie Wutanfall werfen und vom Kronleuchter schwingen. Es ist am besten, sich nicht mit diesen Leuten zu streiten.

Terrence Kwasha
quelle
1

Hier ist die Antwort: Ja, schon 1967 von http://www.isp.uni-luebeck.de/kps07/files/papers/kirner.pdf

Dass das Stopp-Problem zumindest theoretisch für Systeme mit endlichen Zuständen gelöst werden kann, wurde bereits 1967 von Minsky [4] argumentiert: „... Jede Maschine mit endlichen Zuständen wird, wenn sie sich selbst überlassen bleibt, irgendwann in eine vollkommene Periodizität fallen sich wiederholendes Muster. Die Dauer dieses sich wiederholenden Musters darf die Anzahl der internen Zustände der Maschine nicht überschreiten ... “

(Und wenn Sie sich an endliche Turingmaschinen halten, können Sie ein Orakel bauen.)

Natürlich ist eine andere Frage, wie lange dies dauert

daven11
quelle
0

Gibt es eine Untergruppe von Programmen, die bestimmt werden können, wenn sie anhalten?

Ja.

Ist es für die meisten Programme gut genug?

Definiere "most".

Kann ich eine Reihe von Sprachkonstrukten erstellen, mit denen ich die Haltbarkeit eines Programms bestimmen kann?

Ja.

gibt es so etwas wie fast vollständig, was gut genug ist?

Definieren Sie "fast".

Viele Leute schreiben Python, ohne es zu benutzen while Anweisung oder Rekursion.

Viele Leute schreiben Java nur mit der forAnweisung simple Iteratoren oder Zählern, von denen trivial bewiesen werden kann, dass sie terminieren. und sie schreiben ohne Rekursion.

Es ist ziemlich leicht zu vermeiden whileund Rekursion.


Können Sie für ein bestimmtes Programm, in dem alle Eingaben beschränkt sind, bestimmen, ob das Programm anhält?

Nein.

Wenn ja, wie lauten die Einschränkungen der Sprache und wie lauten die Grenzen des Eingabesatzes?

Äh. Das Problem des Anhaltens bedeutet, dass das Programm niemals Dinge über Programme bestimmen kann, die so komplex sind wie es selbst. Sie können eine der zahlreichen Einschränkungen hinzufügen, um das Problem des Anhaltens zu überwinden.

Der Standardansatz für das Stopp-Problem besteht darin, Beweise zuzulassen, die eine etwas "umfangreichere" Menge mathematischer Formalismen verwenden, als sie in der Programmiersprache verfügbar sind.

Es ist einfacher, das Proofsystem zu erweitern, als die Sprache einzuschränken. Jede Einschränkung führt zu Argumenten für den einen Algorithmus, der aufgrund der Einschränkung schwierig auszudrücken ist.

Die maximale Menge dieser Konstrukte würde eine Sprache bestimmen, die angehalten werden kann oder nicht. Gibt es eine Studie darüber?

Ja. Es heißt "Gruppentheorie". Eine Reihe von Werten, die unter einer Reihe von Operationen geschlossen wurden. Ziemlich gut verstandenes Zeug.

S.Lott
quelle
"fast" ist das, was ich frage. Gibt es eine endliche Klasse von Problemen, für die ein Programm zum Stillstand gebracht werden kann, und wie begrenzt ist das Problem? Zum Beispiel hält die Anweisung if (i <10) dann print (i) für alle i an. Wenn ich die Domäne von i auf 32-Bit-Ganzzahlen einschränke, wird sie ebenfalls angehalten.
Daven11
Denken Sie daran , eine forSchleife ist eine while - Schleife, und die Menschen oft komplizierte Dinge in der Bedingung Begriff als nur setzen x < 42.
Billy ONeal
@ Billyoneal: Guter Punkt. In Python ist eine forSchleife sehr, sehr stark darauf beschränkt, einen Iterator durchzuarbeiten. Eine allgemeinere forSchleife in Java kann jedoch zusätzliche Bedingungen enthalten, die die einfache Verwendung eines Iterators ungültig machen.
S.Lott
"Gibt es eine endliche Klasse von Problemen, für die ein Programm zum Stillstand gebracht werden kann?" Die Antwort bleibt ja. "Wie begrenzt ist das Problem?" Äh. Endlich ist endlich. Wenn Sie aufhören, reelle Zahlen zu approximieren und sich an natürliche Zahlen halten, die unter allen mathematischen Operationen geschlossen sind, dann machen Sie eine gewöhnliche Gruppentheorie. Modulararithmetik. Nichts Besonderes. Es ist nicht klar, was Sie fragen. Fragen Sie sich, was eine modulare Arithmetik ist?
S.Lott
@ S.Lott Ich meine Zahlen wie in einer Maschine dargestellt, nicht Zahlen im abstrakten Sinne. Stellen Sie sich Zahlen also als feste Anzahl von Bits vor. Diese Zahlen haben etwas andere Regeln als die ganzen Zahlen und die reellen Zahlen. Hoffe das macht Sinn.
Daven11