Erkennen von Endlosschleifen in Gehirnfick Programm

StackOverflow https://stackoverflow.com/questions/367571

Frage

Ich habe eine einfache Gehirnfick Interpreter in MATLAB-Skriptsprache. Es wird zufällig bf Programme eingespeist (als Teil eines genetischen Algorithmus-Projekt) auszuführen. Das Problem, das ich konfrontiert ist, das Programm stellt sich heraus, eine Endlos-Schleife in einer beträchtlichen Anzahl von Fällen zu haben und damit die GA wird an der Stelle fest.
Also, ich brauche einen Mechanismus Endlosschleifen zu erkennen und zu vermeiden, dass Code in bf ausgeführt wird.
Ein offensichtlicher (trivialer) Fall ist, wenn ich 

[]

Ich kann dies erkennen und sich weigern, das Programm laufen zu lassen.
Für die nicht-trivialen Fälle, habe ich herausgefunden, dass die Grundidee ist: zu bestimmen, wie eine Iteration der Schleife der aktuelle Zelle ändert. Wenn die Änderung negativ ist, sind wir schließlich 0 gehen zu erreichen, so ist es eine endliche Schleife. Andernfalls, wenn die Änderung nicht negativ ist, dann ist es eine Endlosschleife.
Die Implementierung dieses ist einfach für den Fall einer einzelnen Schleife, sondern mit verschachtelten Schleifen wird es sehr kompliziert. Zum Beispiel (im folgenden (1) bezieht sich auf Inhalte der Zelle 1, etc.) 

++++ Put 4 in 1st cell (1)
>+++ Put 3 in (2)
<[   While( (1) is non zero)
    --   Decrease (1) by 2
    >[   While( (2) is non zero)
        -    Decrement (2)
        <+   Increment (1) 
    >]   
    (2) would be 0 at this point
    +++  Increase (2) by 3 making (2) = 3
<]   (1) was decreased by 2 and then increased by 3, so net effect is increment

und daher wird der Code weiter und weiter. Eine naive Überprüfung der Anzahl der + 's und -'s auf Zelle 1, jedoch getan, würde sagen, die Zahl der -'s ist, so würde die Endlos-Schleife nicht erkennen.
Kann jemand denken Sie an einen guten Algorithmus Endlosschleifen zu erkennen, beliebige Verschachtelung beliebiger Anzahl von Schleifen in bf gegeben?

EDIT: Ich weiß, dass das Halteproblem im allgemeinen unlösbaren, aber ich war nicht sicher, ob es nicht Sonderfall Ausnahmen noch nicht gab. Wie, vielleicht könnte Matlab Funktion als Super-Turing-Maschine der Lage, das Anhalten des bf-Programms zu bestimmen. Ich könnte schrecklich falsch sein, aber wenn ja, würde Ich mag, genau wissen, wie und warum.

ZWEITE EDIT: Ich habe geschrieben, was ich behaupten Endlosschleife Detektor zu sein. Es fehlt wahrscheinlich einige Grenzfälle (oder weniger wahrscheinlich, irgendwie entkommt Mr. Turings Kupplungen), scheint aber schon jetzt für mich zu arbeiten. In Pseudo-Code Form, hier geht es: 

subroutine bfexec(bfprogram)
begin
    Looping through the bfprogram,
        If(current character is '[')
            Find the corresponding ']'
            Store the code between the two brackets in, say, 'subprog'
            Save the value of the current cell in oldval
            Call bfexec recursively with subprog
            Save the value of the current cell in newval
            If(newval >= oldval)
                Raise an 'infinite loop' error and exit
            EndIf
        /* Do other character's processings */
        EndIf
    EndLoop
end
War es hilfreich?

Lösung

Wenn ich lineare genetische Programmierung verwendet, habe ich nur eine Obergrenze für die Anzahl der Befehle ein einzelnes Programm durfte in seinem Leben tun. Ich denke, dass dies auf zwei Arten sinnvoll ist: Ich kann nicht wirklich das Halteproblem lösen sowieso, und Programme, die zu lange dauern, um es zu berechnen nicht verdient mehr Zeit sowieso immer

.

Andere Tipps

Alan Turing möchte ein Wort mit Ihnen haben.

http://en.wikipedia.org/wiki/Halting_problem

Angenommen, Sie haben ein Programm schreiben, ob dieses Programm in einer Endlosschleife laufen würde erkennen könnte. Lassen Sie sich aus Gründen der Einfachheit sagen, dass dieses Programm in Gehirnfick geschrieben wurde Gehirnfick Programme zu analysieren (obwohl dies keine Voraussetzung für den folgenden Beweis ist, weil jede Sprache Gehirnfick emulieren kann und Gehirnfick jede Sprache emulieren kann).

Lassen Sie uns jetzt sagen Sie das Prüfungsprogramm erweitern, ein neues Programm zu machen. Dieses neue Programm wird sofort beendet, wenn seine Eingangsschleifen auf unbestimmte Zeit, und Schleifen für immer, wenn sein Eingang an einem gewissen Punkt beendet wird.

Wenn Sie den Eingang dieses neue Programm in sich, was die Ergebnisse sein?

Wenn dieses Programm immer Schleifen, wenn laufen, dann durch seine eigene Definition sollte es sofort verlassen, wenn sie mit sich selbst als Eingabe laufen. Und umgekehrt. Das Prüfungsprogramm kann unmöglich existieren, weil ihre Existenz einen Widerspruch bedeutet.

Wie bereits erwähnt wurde, werden Sie Neuformulierung im Wesentlichen die bekannten Halteproblem: http://en.wikipedia.org/wiki/Halting_problem

Ed. Ich möchte klarstellen, dass die oben Widerlegung ist nicht mein eigenes, sondern ist im Wesentlichen die berühmte Widerlegung Alan Turing zurück im Jahre 1936 gab.

Staat in bf ist ein einzelnes Array von Zeichen.

Wenn ich Sie wäre, würde ich auf jeden einen Hash-Wert des bf-Interpreter Zustand nehmen „]“ (oder einmal in rand (1, 100) „]“ s *) und behaupten, dass der Satz von Hashes einzigartig ist.

Das zweite (oder mehr) Mal, dass ich einen bestimmten Hash sehe, speichere ich den ganzen Staat zur Seite.

Die dritte (oder mehr), wenn ich einen bestimmten Hash sehen, vergleiche ich den ganzen Staat auf das gespeicherte man (n) und wenn es eine Übereinstimmung, ich beenden.

Auf jedem Eingabebefehl ( '', IIRC) ich meine gespeicherten Zustände und Liste von Hashes zurückgesetzt.

Eine Optimierung ist es, nur den Teil der staatlichen Hash, die berührt wurde.

Ich habe nicht das Halteproblem gelöst - ich Erkennung Endlosschleifen beim Laufen das Programm

.

* Der Rand ist die Prüfung unabhängig von Schleifenperiode zu machen

Endlosschleife kann nicht erkannt werden, aber man kann erkennen, ob das Programm zu viel Zeit.

Implementieren eines Timeout durch Erhöhen eines Zählers jedes Mal, wenn Sie einen Befehl ausführen (z <, >, +, -). Wenn der Zähler eine große Zahl erreicht, die man durch die Beobachtung eingestellt, kann man sagen, dass es sehr lange dauert, Ihr Programm auszuführen. Für Ihren Zweck, „sehr lange“ und unendlich ist eine gut genug Annäherung.

Wie bereits erwähnt ist dies das Halteproblem. Aber in Ihrem Fall könnte es eine Lösung sein. Das Halteproblem erwägt ist über die Turing-Maschine, die unbegrenzten Speicher

Wenn Sie wissen, dass Sie eine obere Grenze des Speichers (z.B. Sie wissen, dass Sie mehr als 10 Speicherzellen nicht verwenden), können Sie Ihr Programm ausführen und es stoppen. Die Idee ist, dass die Berechnungsraum Grenzen Rechenzeit (wie Sie mehr als eine Zelle in einem Schritt schreiben kippen). Nachdem Sie so viele Schritte ausgeführt, wie Sie verschiedene Speicherkonfigurationen haben können, können Sie brechen. Z.B. wenn Sie 3-Zellen haben, mit 256 Bedingungen, können Sie höchstens 3 ^ 256 verschiedene Zustände haben, und so kann man nach, dass viele Schritte ausführen zu stoppen. Aber Vorsicht, es gibt implizite Zellen, wie die Befehlszeiger und die Register. Sie tun es noch kürzer, wenn Sie jede Zustandskonfiguration speichern und sobald Sie einen erkennen, die Sie bereits, Sie infite Schleife haben. Dieser Ansatz ist auf jeden Fall viel besser in der Laufzeit, aber dafür braucht viel mehr Platz (hier könnte es zweckmäßig sein, die Konfigurationen Hash).

Dies ist nicht das Halteproblem, aber es immer noch nicht vernünftig ist, zu versuchen, auch in einem solchen begrenzten Maschine als 1000 Zelle BF Maschine zu erfassen, zu stoppen.

Betrachten Sie dieses Programm: 

+[->[>]+<[-<]+]

Dieses Programm wird nicht wiederholen, bis sie den gesamten Speicher gefüllt hat, die für nur 1000 Zellen etwa 10 ^ 300 Jahre dauern.

Aus der Spitze von meinem Kopf (und ich könnte falsch sein), würde ich denken, dass es ein wenig wäre schwer zu erkennen, ob ein Programm in eine Endlosschleife hat, ohne tatsächlich die Ausführung des Programms selbst.

Da die bedingte Ausführung von Teilen des Programms auf dem Ausführungszustand des Programms hängt, wird es schwierig sein, den besonderen Status des Programms zu kennen, ohne das Programm tatsächlich ausgeführt wird.

Wenn Sie nicht erfordert , dass ein Programm mit einer Endlosschleife ausgeführt wird, könnten Sie versuchen, ein „Befehle ausgeführt“ Zähler aufweisen und nur eine endliche Anzahl von Befehlen auszuführen. Auf diese Weise, wenn ein Programm eine Endlosschleife hat, kann der Interpreter das Programm beenden, die in einer Endlosschleife stecken.

Wenn ich mich richtig erinnere, das Halteproblem Beweis war nur wahr für einigen Extremfall der Selbst Bezug beteiligt. Allerdings ist es immer noch trivial ein praktisches Beispiel zu zeigen, warum Sie nicht in eine Endlosschleife Detektor machen kann.

Fermats letzter Satz Betrachten. Es ist einfach, ein Programm zu erstellen, die durch jede Zahl (oder in diesem Fall 3 Zahlen) iteriert, und stellt fest, ob es sich um ein Gegenbeispiel zu dem Satz ist. Wenn dies der Fall hält es, sonst geht es weiter.

Wenn Sie also eine Endlosschleife Detektor haben, sollten sie in der Lage sein, diesen Satz zu beweisen, und viele viele andere (vielleicht alle anderen, wenn sie auf der Suche nach Gegenbeispielen reduziert werden kann.)

Im Allgemeinen kann jedes Programm, das durch Zahl iterieren beinhaltet und nur unter einer Bedingung zu stoppen, würde eine allgemeine Theorembeweisers erfordern zu beweisen, wenn diese Bedingung immer erfüllt werden kann. Und das ist der einfachste Fall Looping wird.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top