algorithm - Detectando un bucle infinito en el programa brainfuck

interpreter infinite-loop

Question

Escribí un simple intérprete de brainfuck en lenguaje de script MATLAB. Se alimenta con programas de bf aleatorios para ejecutar (como parte de un proyecto de algoritmo genético). El problema que enfrento es que el programa tiene un ciclo infinito en un número considerable de casos y, por lo tanto, la GA se atasca en el punto.
Entonces, necesito un mecanismo para detectar bucles infinitos y evitar ejecutar ese código en bf.
Un caso obvio (trivial) es cuando tengo

[]

Puedo detectar esto y negarme a ejecutar ese programa.
Para los casos no triviales, descubrí que la idea básica es: determinar cómo una iteración del ciclo cambia la celda actual. Si el cambio es negativo, finalmente llegaremos a 0, por lo que es un ciclo finito. De lo contrario, si el cambio no es negativo, es un ciclo infinito.
Implementar esto es fácil para el caso de un bucle único, pero con bucles anidados se vuelve muy complicado. Por ejemplo, (en lo que sigue (1) se refiere a los contenidos de la celda 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

y por lo tanto el código se ejecuta y sigue. Sin embargo, una comprobación ingenua del número de + y -''s realizado en la celda 1, diría que el número de -''s es más, por lo que no detectaría el ciclo infinito.
¿Puede alguien pensar en un buen algoritmo para detectar bucles infinitos, dado el agrupamiento arbitrario de un número arbitrario de bucles en bf?

EDITAR: Sé que el problema de la detención es insoluble en general, pero no estaba seguro de si no existían excepciones de casos especiales. Por ejemplo, quizás Matlab funcione como una máquina Super Turing capaz de determinar la interrupción del programa bf. Puede que esté terriblemente mal, pero si es así, me gustaría saber exactamente cómo y por qué.

SEGUNDA EDICIÓN: He escrito lo que pretendo ser un detector de bucle infinito. Probablemente se pierda algunos casos extremos (o con menor probabilidad, de alguna manera escapa a las garras del Sr. Turing), pero parece funcionar para mí a partir de ahora. En forma de pseudocódigo, aquí va:

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

Answer 1

Alan Turing quisiera hablar con usted.

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

Answer 2

Cuando utilicé la programación genética lineal, acabo de utilizar un límite superior para la cantidad de instrucciones que se permitió hacer a un solo programa durante su vida útil. Creo que esto es sensato de dos maneras: en realidad no puedo resolver el problema de detención, y los programas que tardan demasiado en computarse no son dignos de obtener más tiempo de todos modos.

Answer 3

Como ya se mencionó, este es el problema de la detención. Pero en su caso podría haber una solución: el problema de la detención es considerar la máquina de Turing, que tiene memoria ilimitada.

En caso de que sepa que tiene un límite superior de memoria (p. Ej., Sabe que no usa más de 10 celdas de memoria), puede ejecutar su programa y detenerlo. La idea es que el espacio de cálculo limite el tiempo de cálculo (ya que no se puede escribir más de una celda en un paso). Después de ejecutar tantos pasos como pueda tener diferentes configuraciones de memoria, puede romper. Por ejemplo, si tiene 3 celdas, con 256 condiciones, puede tener como máximo 3 ^ 256 estados diferentes, por lo que puede detenerse después de ejecutar esos muchos pasos. Pero tenga cuidado, hay celdas implícitas, como el puntero de instrucción y los registros. Lo haces aún más corto, si guardas todas las configuraciones de estado y tan pronto como detectas una, que ya tenías, tienes un ciclo de infite. Este enfoque definitivamente es mucho mejor en el tiempo de ejecución, pero por lo tanto necesita mucho más espacio (aquí podría ser adecuado ajustar las configuraciones).

Answer 4

El bucle infinito no se puede detectar, pero puede detectar si el programa tarda demasiado.

Implemente un tiempo de espera incrementando un contador cada vez que ejecuta un comando (por ejemplo, < , > , + , - ). Cuando el contador llega a un número grande, que usted establece por observación, puede decir que lleva mucho tiempo ejecutar su programa. Para su propósito, "muy largo" e infinito es una aproximación lo suficientemente buena.

Answer 5

Estado en bf es una única matriz de caracteres.

Si yo fuera tú, tomaría un hash del estado del intérprete bf en cada "]" (o una vez en rand (1, 100) "]" s *) y afirmaría que el conjunto de hash es único.

La segunda (o más) vez que veo un cierto hash, guardo todo el estado a un lado.

La tercera (o más) vez que veo un determinado hash, comparo el estado completo con el guardado y si hay una coincidencia, salgo.

En cada comando de entrada (''.'', IIRC) reinicié mis estados guardados y la lista de hashes.

Una optimización es solo hash la parte del estado que se tocó.

No he resuelto el problema de detención: estoy detectando bucles infinitos mientras ejecuto el programa.

* El rand es hacer que la verificación sea independiente del período de bucle

Answer 6

Fuera de mi cabeza (y podría estar equivocado), creo que sería un poco difícil detectar si un programa tiene o no un bucle infinito sin ejecutar realmente el programa.

Como la ejecución condicional de partes del programa depende del estado de ejecución del programa, será difícil conocer el estado particular del programa sin ejecutar realmente el programa.

Si no requiere que se ejecute un programa con un bucle infinito, puede intentar tener un contador de "instrucciones ejecutadas" y solo ejecutar un número finito de instrucciones. De esta manera, si un programa tiene un bucle infinito, el intérprete puede terminar el programa que está atrapado en un bucle infinito.

Answer 7

Digamos que escribiste un programa que podría detectar si este programa se ejecutaría en un ciclo infinito. Digamos por simplicidad que este programa fue escrito en brainfuck para analizar programas brainfuck (aunque esto no es una precondición de la siguiente prueba, porque cualquier lenguaje puede emular brainfuck y brainfuck puede emular cualquier lenguaje).

Ahora digamos que extiende el programa de verificación para hacer un nuevo programa. Este nuevo programa sale inmediatamente cuando su entrada se repite indefinidamente, y se repite siempre cuando su entrada sale en algún punto.

Si ingresa este nuevo programa en sí mismo, ¿cuáles serán los resultados?

Si este programa gira para siempre cuando se ejecuta, entonces, según su propia definición, debe salir inmediatamente cuando se ejecuta consigo mismo como entrada. Y viceversa. El programa de verificación no puede existir, porque su propia existencia implica una contradicción.

Como se mencionó anteriormente, esencialmente está reafirmando el famoso problema de detención: http://en.wikipedia.org/wiki/Halting_problem

Ed. Quiero dejar en claro que la refutación anterior no es mía, pero es esencialmente la famosa refutación que Alan Turing devolvió en 1936.

Answer 8

Este no es el problema de detención, sin embargo, aún no es razonable intentar detectar la detención incluso en una máquina tan limitada como una máquina BF de 1000 células.

Considera este programa:

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

Este programa no se repetirá hasta que haya llenado toda la memoria, que por solo 1000 células tomará aproximadamente 10 ^ 300 años.

Answer 9

Si mal no recuerdo, la prueba del problema de detención fue solo cierta para algunos casos extremos que involucraron auto referencia. Sin embargo, sigue siendo trivial mostrar un ejemplo práctico de por qué no se puede hacer un detector de bucle infinito.

Considera el último teorema de Fermat . Es fácil crear un programa que itere a través de cada número (o en este caso 3 números), y detecta si es un contraejemplo para el teorema. Si es así, se detiene, de lo contrario continúa.

Entonces, si tiene un detector de bucle infinito, debería ser capaz de demostrar este teorema, y ​​muchos otros (tal vez todos los demás, si pueden reducirse a la búsqueda de contraejemplos).

En general, cualquier programa que implique iterar a través de números y detenerse solo bajo alguna condición, requeriría un probador de teorema general para probar si alguna vez se puede cumplir esa condición. Y ese es el caso más simple de bucle que hay.