Lösen Sie teilweise das Halteproblem für brainf ***

Um das Halteproblem zu lösen, erhalten Sie eine Beschreibung eines Programms und müssen bestimmen, ob es jemals beendet wird oder nicht. Sie können dies niemals für alle Programme tun. Doch für Programme wie (in brainf *** ):

>

Es wird offensichtlich aufhören und für Programme wie:

+[]

Das wird es offensichtlich nicht. Ihre Herausforderung besteht darin, das Stoppproblem für so viele Programme wie möglich zu "lösen". Diese Programme verwenden .oder nicht ,und haben keine Eingabe oder Ausgabe. Sie erhalten eine Beschreibung des Programms und müssen entweder "Halts", "Stoppt nicht" oder "Unbekannt" ausgeben. Wenn Ihr Programm "Halts" oder "Stoppt nicht" ausgibt, haben Sie das Eingabeprogramm gelöst. Hier sind einige Anforderungen.

1. Es muss mindestens unendlich viele Programme lösen.
2. Für jedes Programm, das es löst, muss seine Lösung korrekt sein.
3. Sie können nur 1 der 3 oben genannten Optionen ausgeben.
4. Sie können davon ausgehen, dass der laufende Computer über unendlich viel Zeit und Speicher verfügt, sodass XKCD 1266 nicht funktioniert (das Band ist unbegrenzt).
5. Keine externen Ressourcen.
6. Möglicherweise verwenden Sie keine Programmiersprache, die das Stoppproblem tatsächlich lösen kann .

Möglicherweise haben Sie ein Nebenprogramm ohne Code, das eine Zeichenfolge verwendet, die ein Programm ist, und auf Wunsch eine Art abstrakten Syntaxbaum daraus generiert. Beachten Sie, dass dies an sich keine wirkliche Punktzahl ist, sondern wie festgestellt werden kann, ob ein Programm ein anderes schlägt.

1. Wenn Programm A eine unendliche Anzahl von Programmen löst, die B nicht löst, B jedoch nur endliche oder keine Programme löst, die A löst, gewinnt A automatisch.
2. Andernfalls gewinnt das Programm mit den wenigsten Zeichen. Zählen Sie keine Leerzeichen oder Kommentare, also verschleiern Sie Ihren Code nicht.

Tipp: Timer funktionieren nicht. Sie sehen, für jede Zeit T und gegebene Maschine gibt es ein N, so dass alle Programme, die länger als diese sind, mehr als T Zeit benötigen müssen. Dies bedeutet, dass ein Timer nur die Lösung einer endlichen Anzahl von Programmen erreichen kann, und wie Sie oben sehen können, hilft das Lösen einer endlichen Anzahl von Programmen nicht.

Python, ungolfed Spaghetti-Code

Ach je.

def will_it_halt(instructions):
    tape_length = 1
    LOOP_BOUND = 1000
    registry = [0] * tape_length
    pos = 0

    jumpbacks = []
    reached_states = set()

    pos_instructions = 0
    while True:
        letter = instructions[pos_instructions]
        if letter == "+":
            registry[pos] = (registry[pos] + 1) % 256
        elif letter == "-":
            registry[pos] = (registry[pos] - 1) % 256
        elif letter == ">":
            pos += 1
            if pos >= tape_length:
                registry += [0]*tape_length
                tape_length = len(registry)
        elif letter == "<":
            pos -= 1
            if pos <= 0:
                registry = [0]*tape_length+registry
                tape_length = len(registry)
                pos += tape_length
        elif letter == "[":
            if registry[pos] == 0:
                nests = 1
                while nests:
                    pos_instructions += 1
                    if instructions[pos_instructions] == "[": nests += 1
                    elif instructions[pos_instructions] == "]": nests -= 1

                if jumpbacks == []:
                    reached_states.clear()

            else:
                jumpbacks.append(pos_instructions-1)

        elif letter == "]":
            stripped_registry = [str(x) for x in registry if x != 0]
            translated_pos = pos - (len(registry) - len(stripped_registry))
            state = (translated_pos, pos_instructions, ".".join(stripped_registry))
            if state in reached_states: return "Does not halt"
            elif len(reached_states) > LOOP_BOUND: return "Unknown"
            else:
                reached_states.add(state)
                pos_instructions = jumpbacks.pop()
        pos_instructions += 1
        if pos_instructions >= len(instructions): break
    return "Halts"

Ziemlich brutale Lösung für das Problem: Führen Sie einfach den bf-Code aus. Wir nehmen an, dass die Bandlänge beliebig lang ist und dass einzelne Zellen bei 256 gewickelt werden. Am Ende jeder Schleife speichern wir den Zustand des Bandes mit einem Satz. Zustände haben die Form (unsere Position auf dem Band, unsere Position auf den Anweisungen, wie das Band aussieht, wenn führende Nullen entfernt werden).

Wenn wir denselben Status zweimal speichern, befinden wir uns irgendwo in einer Endlosschleife, sodass das Programm nicht angehalten wird. Wenn wir über 1.000 Staaten speichern, reduzieren Sie Verluste und geben Sie Unbekanntes zurück. Sobald wir eine Schleife verlassen, prüfen wir, ob wir uns nicht in größeren Schleifen befinden. Wenn nicht, sehen wir nie wieder einen der vorherigen Zustände (zumindest wird die Anweisungsposition immer anders sein!), Damit wir die Menge der Zustände löschen können.

Dies sollte jedes BF-Programm genau bestimmen, dessen Schleifen nicht länger als 1.000 Iterationen sind, sowie viele Programme, die einen Zustand vor 1.000 Iterationen in einer Schleife wiederholen. Nicht alle von ihnen: Etwas wie "{1 Million + ist hier} [-]> + [+ -]" wiederholt schließlich einen Zustand, aber die [-] Schleife durchläuft zuerst 1.000 Iterationen.

Einige Beispiele:

>+>->+>-

Keine Schleifen, so dass es das Ende erreicht und anhält.

+[+]

Die Schleife endet nach 256 Iterationen, erreicht also das Ende und wird angehalten.

+[+-]

Wiederholt schließlich den Zustand (0,5, "1"), damit er nicht anhält.

+[->+]

Dies wiederholt keine Zustände, aber die Schleife endet nie, daher sollte "unbekannt" ausgegeben werden. Aber das Programm betrügt hier irgendwie. Anstatt die Position auf dem Band zu speichern, wird ein Versatz zwischen der ursprünglichen und der entfernten Registrierung hinzugefügt. Wenn eine Schleife das Band nur um einige Leerzeichen übersetzt, wird es unbegrenzt weiter übersetzt (wie ein Rettungsflugzeug), sodass wir sagen können, dass es nicht anhält.

+[>+]

Übersetzt nicht, wiederholt keine Zustände, druckt unbekannt.

+++++++++++[-]

Dies hört zwar auf, würde aber "unbekannt" ausgeben, wenn LOOP_BOUND 10 wäre.

Es gibt verschiedene Möglichkeiten, dies intelligenter zu gestalten. Sie können LOOP_BOUND natürlich erhöhen, um die Anzahl der Unbekannten zu verringern. Sie könnten verschachtelte Schleifen intelligenter handhaben. Sie könnten wahrscheinlich etwas Besonderes mit BB-Zahlen und der Größe von Schleifen tun, um besser zu erkennen, ob etwas anhalten sollte, aber ich bin weder bei CS noch bei Python gut genug, um dies noch zu tun.

GolfScript (23 Zeichen, unendlich richtige Antworten)

'[]'&!
# 0 if there are brackets, so Unknown
# 1 if there are no brackets, so no looping, so definitely halts
'UnknownHalts'7/=

Awk

Eine kleine Leistungserweiterung aus den beiden Beispielen. Wenn ein Programm überhaupt keine Schleifen enthält, also keine Entscheidungen, ist es offensichtlich immer noch entschlossen anzuhalten. Da wir von der Gültigkeit des Programms ausgehen, gehen wir auch davon aus, dass die Klammern ausgeglichen sind und daher nur nach der einen oder anderen Klammer suchen müssen.

BEGIN{RS=""}
!/\[/{print "Halts"; exit}
END{print "Unknown"}

Für das zweite muss zuerst geprüft werden, ob die Schleife überhaupt ausgeführt wird, daher müssen wir den geradlinigen Code simulieren, der der Schleife vorausgeht. Wenn dann die Schleife zu derselben Zelle zurückkehrt (dh die Anzahl von >s ist gleich der Anzahl von <s innerhalb der Schleife) und in dieser Zelle keine In- oder Decs ausführt (dh für jedes positionsausgeglichene Präfix des ausgeglichenen Schleifenkörper, es gibt keine Instanzen von +oder -vor dem nächsten <oder >, dann ist die Zelle unverändert). Die Implementierung dieses Teils kann mehr Zeit in Anspruch nehmen. Oh, warte, bis der erste Teil der Überprüfung, ob die Schleife überhaupt läuft, können wir dieselbe Idee übernehmen und das Pre-Loop-Programm nach ausgeglichenen Suffixen durchsuchen und darauf bestehen, dass es ein +oder -(unsymmetrisch) gibt.

Haskell

Hier ist eine wirklich einfache Beispielantwort. Fühlen Sie sich frei, es in Ihre Antworten aufzunehmen (da es eine gute Idee ist, mehrere Tests in eine Antwort aufzunehmen.)

main=do
    p<-getLine
    if take 3 p == "+[]"
        then putStr "Does not halt"
        else putStr "Unknown"

Es sieht im Grunde, ob es am Anfang eine Schleife gibt. Wenn diese exakte Schleife am Anfang nicht auftritt, gibt sie einfach auf. Es funktioniert nicht einmal für ++[]. Es löst jedoch unendlich viele Programme und ist immer korrekt, wenn es gelöst wird.