Resolver parcialmente el problema de detención para brainf ***

Para resolver el problema de detención , se le da una descripción de un programa y debe determinar si terminará o no. Nunca puede hacer esto para todos los programas. Sin embargo, para programas como (en brainf *** ):

>

Obviamente se detendrá, y para programas como:

+[]

Obviamente no lo hará. Su desafío es "resolver" el problema de detención para tantos programas como sea posible. Estos programas no usarán .o ,, y no tendrán entrada ni salida. Se le dará una descripción del programa y deberá mostrar "Paradas", "No se detiene" o "Desconocido". Cuando su programa emite "Se detiene" o "No se detiene", ha resuelto el programa de entrada. Aquí hay algunos requisitos.

1. Debe resolver al menos una cantidad infinita de programas.
2. Para cada programa que resuelve, su solución debe ser correcta.
3. Solo puede generar 1 de las 3 opciones anteriores.
4. Puede suponer que la computadora en ejecución tiene tiempo y memoria infinitos, por lo que XKCD 1266 no funcionaría (la cinta es ilimitada).
5. Sin recursos externos.
6. No puede usar un lenguaje de programación que realmente pueda resolver el problema de detención .

Es posible que tenga un programa secundario sin código de golf que tome una cadena que sea un programa y genere algún tipo de árbol de sintaxis abstracta si lo desea. Tenga en cuenta que eso no es realmente una puntuación per se, sino cómo determinar si un programa supera a otro.

1. Si el programa A resuelve un número infinito de programas que B no, pero B solo resuelve programas finitos o ninguno que A resuelve, A gana automáticamente.
2. De lo contrario, el programa con la menor cantidad de caracteres gana. No cuente los espacios en blanco ni los comentarios, así que no ofusque su código.

Consejo: los temporizadores no funcionarán. Verá, para cualquier momento T y una máquina dada, hay una N, de modo que todos los programas más largos que eso tienen que tomar más de tiempo T. Esto significa que un temporizador solo puede lograr la solución de un número finito de programas y, como puede ver arriba, resolver un número finito de programas no ayuda.

Python, código de espagueti sin golf

Oh querido.

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"

Solución bastante brutal al problema: simplemente ejecute el código bf. Suponemos que la longitud de la cinta es arbitrariamente larga y que las celdas individuales se ajustan a 256. Al final de cada bucle, almacenamos el estado de la cinta con un conjunto. Los estados son de la forma (nuestra posición en la cinta, nuestra posición en las instrucciones, cómo se ve la cinta con los primeros 0 despojados).

Si almacenamos el mismo estado dos veces, entonces estamos en algún lugar en un bucle infinito, por lo que el programa no se detiene. Si almacenamos más de 1,000 estados, reduzcamos las pérdidas y regresemos desconocidos Una vez que dejamos un bucle, verificamos si no estamos en bucles más grandes. Si no, nunca volveremos a ver ninguno de los estados anteriores (¡al menos, la posición de instrucción siempre será diferente!) Para que podamos borrar el conjunto de estados.

Esto debería determinar con precisión cualquier programa BF cuyos bucles no sean más largos que 1,000 iteraciones, así como muchos programas que repiten un estado antes de 1,000 iteraciones en un bucle. Sin embargo, no todos: algo como "{1 millón + 'aquí} [-]> + [+ -]" eventualmente repite un estado, pero el ciclo [-] pasa primero 1,000 iteraciones.

Algunos ejemplos:

>+>->+>-

Sin bucles, por lo que llega al final y se detiene.

+[+]

El bucle termina después de 256 iteraciones, por lo que llega al final y se detiene.

+[+-]

Eventualmente repite el estado (0,5, "1"), por lo que no se detiene.

+[->+]

Esto no repite ningún estado, pero el ciclo nunca termina, por lo que debería imprimir "desconocido". Pero el programa hace trampa aquí. En lugar de almacenar la posición en la cinta, agrega un desplazamiento entre el registro original y el eliminado. Si todo lo que hace un bucle es traducir la cinta por algunos espacios, continuará traduciéndola indefinidamente (como un planeador de vida), por lo que podemos decir que no se detiene.

+[>+]

No traduce, no repite ningún estado, imprime desconocido.

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

Esto se detiene, pero se imprimiría "desconocido" si LOOP_BOUND fuera 10.

Hay un par de maneras de hacer esto más inteligente. Obviamente, podría aumentar LOOP_BOUND para reducir la cantidad de incógnitas. Podría tener un manejo más inteligente de los bucles anidados. Probablemente podría hacer algo elegante con los números BB y el tamaño de los bucles para detectar mejor si algo debería detenerse, pero no soy lo suficientemente bueno en CS ni en Python para poder hacerlo todavía.

GolfScript (23 caracteres, infinitas respuestas correctas)

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

Awk

Una pequeña extensión en el poder de los dos ejemplos. Si un programa no contiene ningún bucle, por lo tanto, no hay decisiones, es obvio que está decidido a detenerse. Como asumimos la validez del programa, también asumimos que los corchetes están equilibrados y, por lo tanto, solo necesitamos buscar uno u otro de los corchetes.

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

Para el segundo, debe verificar primero si el ciclo se ejecuta, por lo que debemos simular el código de línea recta que precede al ciclo. Luego, si el ciclo regresa a la misma celda (es decir, el número de >s es igual al número de <s dentro del ciclo), y no realiza incs o decs en esta celda (es decir, para cualquier prefijo de posición balanceada cuerpo del bucle, no hay instancias de +o -antes del siguiente <o >, entonces la celda no se modifica). Implementar esta parte puede llevarme más tiempo. Ooh, espera, para la primera parte de verificar si el ciclo se ejecuta, podemos tomar esta misma idea y buscar sufijos equilibrados en el programa pre-loop e insistir en que haya un +o -(desequilibrado).

Haskell

Aquí hay una respuesta de ejemplo realmente simple. Siéntase libre de incluirlo en sus respuestas (ya que incluir múltiples pruebas en una respuesta es una buena idea).

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

Básicamente ve si hay un bucle al principio. Si ese ciclo exacto no ocurre al principio, simplemente se da por vencido. Ni siquiera funciona para ++[]. Sin embargo, resuelve un número infinito de programas, y siempre es correcto cuando lo resuelve.