javascript - que - ¿Es posible enumerar programas de computadora?

programa javascript

Question

Supongamos que tiene que escribir un programa que pruebe todos los programas en busca de uno que complete una tarea específica. Por ejemplo, considere esta función de JavaScript:

function find_truth(){
    for(n=0;;++n){
        try {
            var fn = Function(string(n));
            if (fn() == 42)
                return fn;
        } catch() {
            continue;
        }
    }
}

Siempre que la cadena (n) devuelva la cadena n posible ("a", "b", "c", ... "aa", "ab" ...), este programa eventualmente generará una función que se evalúa como 42 . El problema con este método es que está enumerando cadenas que podrían o no podrían ser un programa válido. Mi pregunta es: ¿es posible enumerar programas ellos mismos? ¿Cómo?

Answer 1

Ciertamente, es posible enumerar todos los programas en un idioma dado que son sintácticamente válidos (y en un lenguaje tipado estáticamente, incluso solo aquellos que escriben el tipo): simplemente podría enumerar todas las cadenas como propuso, trate de incluir cada uno en un analizador. El lenguaje y luego rechazar los que no se pueden analizar. Entonces, si esa es tu definición de un programa válido, entonces sí, es posible.

Sin embargo, no es cierto que su programa necesariamente genere una función que finalmente devuelva 42, incluso si reemplaza la string con una función que solo devuelve programas sintácticamente válidos. Si una función devuelta contiene un bucle infinito, se ejecutará para siempre y, por lo tanto, su programa nunca podrá probar otra función. Por lo tanto, es posible que nunca llegue a una función que devuelve 42.

Para evitar este problema, podría decir que la función de string(n) solo debe producir código que sea sintácticamente válido y que no contenga un bucle infinito (aunque aún pueda devolver todas las funciones). Eso, sin embargo, no es posible porque implicaría decidir el problema de la detención (que, por supuesto, es indecidible).

Answer 2

Como se ha señalado, puede convertir de manera trivial un programa "generar todas las cadenas" en un "generar todos los programas válidos en el idioma X" conectando un analizador / compilador para el idioma X. Generalmente, si puede escribir un programa que tome el texto como entrada y devuelve verdadero / falso indicando si el texto representa un programa válido, entonces puede usarlo como un filtro en el programa "generar todas las cadenas".

También puede diseñar un lenguaje de programación en el que cada cadena de caracteres sea un programa válido (el perl viene a la mente).

Probablemente, lo más interesante es que, dada la gramática formal de un idioma, podría usarlo para generar programas en el idioma en lugar de analizarlos. Solo necesita hacer un recorrido de la gramática en primer lugar para estar seguro de que se alcanzará cada programa de duración finita en un tiempo determinado (si hace un recorrido en primer lugar de profundidad, se quedará impresionado al explorar todos los programas que consisten únicamente en un variable cuyo nombre es una secuencia cada vez más larga de ''A''s, o algo así.

Sin embargo, la mayoría de las gramáticas utilizadas para analizar lenguajes de programación no funcionarían directamente para esto; por lo general son un poco demasiado permisivos. Por ejemplo, una gramática puede definir identificadores como cualquier cosa que coincida con una expresión regular [_A-Za-z][0-9_A-Za-z]* , que permite nombres de variable de longitud ilimitada, pero muchas implementaciones de lenguaje en realidad se atragantarán con programas con variable nombres que son gigabytes de largo. Pero, en principio, puede averiguar todo este tipo de errores y escribir una enumerable gramática que cubra exactamente todos los programas válidos en algún idioma de interés.

Así que eso te permite enumerar todos los programas. Sin embargo, eso no es suficiente para permitirle ejecutar su programa find_truth y encontrar un programa que devuelva 42 , ya que se quedará atascado evaluando infinitamente el primer programa que contenga un bucle infinito.

¡Pero todavía es posible hacer esto! Solo tiene que elegir un orden en el que examinar todas las posibilidades para que finalmente se alcance todo en un tiempo determinado. Tienes dos "dimensiones" infinitas para buscar; la enumeración de todos los programas, y la profundidad de la evaluación de cada programa. Puedes asegurarte de cubrir todas las bases haciendo algo como la siguiente estrategia:

1. Ejecutar todos los programas de longitud hasta 1 para hasta 1 paso
2. Ejecute todos los programas de longitud hasta 2 para hasta 2 pasos
3. Ejecute todos los programas de longitud hasta 3 para hasta 3 pasos
4. ...

Y así. Esto garantiza que, independientemente de la duración del programa y la cantidad de "pasos" necesarios, eventualmente los ejecutará sin necesidad de haber realizado una cantidad infinita de trabajo "primero" (siempre que exista un programa con el resultado deseado).

Si tiene disponible un almacenamiento ilimitado, puede evitar repetir el trabajo entre estas fases (almacena todos los programas de longitud N que no han terminado en N pasos, junto con su estado, y luego en la siguiente ronda ejecuta los nuevos programas a N + 1 pasos, y ejecute todos los programas "pendientes" para un paso más cada uno). La definición de "paso" no importa mucho, siempre y cuando no admita bucles infinitos. Algún número finito de bytecodes, o instrucciones de la CPU, o incluso segundos; necesitarías una implementación suspendible del lenguaje, por supuesto.

Answer 3

Es imposible. El problema es que algunos programas pueden tardar mucho tiempo en terminar de computar. Y algunos programas pueden estar atrapados en un bucle infinito. Idealmente, le gustaría abortar la ejecución de los programas que están atascados en bucles infinitos, y mantener solo los programas de larga duración. Podría implementar un temporizador, pero ¿qué pasaría si tuviera un programa que durara más que el temporizador, pero aún así respondiera la respuesta correcta?

En general, la única manera de ver si un programa de computadora terminará es ejecutarlo y verlo, con el riesgo de ingresar un bucle infinito. Por supuesto, podría implementar algunas heurísticas para reconocer formas comunes de bucles infinitos, pero en general es imposible. Esto se conoce como el problema de la detención .

EDITAR:

Me doy cuenta de que solo respondo parcialmente tu pregunta. Preguntas si es posible enumerar programas ellos mismos. Esto es ciertamente posible. Ya tienes una forma de generar todas las cadenas posibles en orden. Entonces puedes ver qué cadenas se analizan correctamente como un programa javascript y simplemente mantenerlas.

Answer 4

Sí, hay formas en que esto es posible. Hace unos meses hice un pequeño proyecto experimental para hacer algo así, que funciona razonablemente bien considerando lo que está haciendo. Le asigna un tipo y algunas pruebas para aprobar, y busca una función adecuada que pase las pruebas. Nunca realizo el trabajo para madurar, pero se puede ver que en realidad genera funciones que pasan las pruebas en el caso de los ejemplos. Requerir el tipo era un componente esencial para la practicidad de esta búsqueda, ya que reducía drásticamente la cantidad de programas que debían probarse.

Es importante tener una comprensión firme de la teoría aquí antes de hacer afirmaciones sobre lo que es y lo que no es posible; hay muchos que saltarán al problema de la detención y le dirán que es imposible, cuando la verdad es un poco más matizada. que eso.

• Puede generar fácilmente todos los programas válidos sintácticamente en un idioma determinado. De manera ingenua, puede generar todas las cadenas y filtrar las que se analizan / mecanografían; Pero hay mejores maneras .
• Si el lenguaje no está completo, por ejemplo, el cálculo lambda de tipo simple, o incluso algo muy poderoso como Agda, puede enumerar todos los programas que generan 42, y dado cualquier programa puede decidir "esto genera 42" o "esto sí No generar 42 ". (El lenguaje que utilicé en mi proyecto experimental está en esta clase). La tensión aquí es que en cualquier lenguaje, habrá algunas funciones computables que no se pueden escribir.
• Incluso si el idioma se ha completado, aún puede enumerar todos los programas que eventualmente generen 42 (haga esto ejecutándolos en paralelo e informando el éxito a medida que terminen).

Lo que no puede hacer con un lenguaje completo es decidir que un programa definitivamente no generará 42; podría funcionar para siempre y no podrá saber si finalmente tendrá éxito hasta que lo logre. Sin embargo, hay algunos programas que puedes decir que tendrán un bucle infinito, pero no todos. Entonces, si tiene una tabla de programas, puede esperar que su programa de enumerador en el caso de un lenguaje completo que no sea de Turing sea así:

Program |  P1  |  P2  |  P3  |  P4  |  P5  |  P6  |  P7  | ...
42?     | No   | No   | No   | Yes  | No   | No   | No   | ...

Mientras que en un lenguaje completo, su salida (en un momento dado) sería así:

Program |  P1  |  P2  |  P3  |  P4  |  P5  |  P6    |  P7  | ...
42?     | No   | No   | Loop | Yes  | No   | Dunno  | No   | ...

Y más tarde, Dunno podría convertirse en un Sí o un No, o podría permanecer en el silencio para siempre, usted simplemente no lo sabe.

Todo esto es muy teórico, y generar programas en un lenguaje completo para buscar los que hacen algo es bastante difícil y lleva mucho tiempo. Ciertamente no quieres hacerlo uno por uno, porque el espacio es muy grande; Probablemente quieras usar un algoritmo de búsqueda genética o algo así.

Otro punto sutil en la teoría: hablar de programas que "generan 42" falta algunos detalles importantes. Generalmente cuando hablamos de generar programas, queremos que genere una función determinada, no solo una salida específica. Y esto es cuando las cosas que podrías querer hacer se vuelven más imposibles. Si tiene un espacio infinito de entradas posibles, por ejemplo, ingrese un solo número,

• En general, no se puede saber si un programa calcula una función determinada. No puede verificar cada entrada manualmente porque el infinito es demasiado para verificar. No puede buscar pruebas de que su función hace lo correcto, porque para cualquier función computable f , para cualquier sistema de axioma A , hay programas que se computan f de tal manera que A no tiene pruebas de que computen f .
• No se puede saber si un programa va a dar algún tipo de respuesta para cada entrada posible. Puede funcionar para los primeros 400,000,000 de ellos pero un bucle infinito en los 400,000,001st.
• De manera similar, no puede saber si dos programas computan la misma función (es decir, las mismas entradas -> las mismas salidas).

Ahí lo tienen, una dosis diaria de fenomenología de la teoría de decidibilidad.

Si está interesado en hacerlo de verdad, examine los algoritmos genéticos y establezca tiempos de espera en las funciones que intenta y / o use un lenguaje decidible (no completo de Turing).

Answer 5

Suponiendo que estoy interpretando correctamente su frase "¿es posible enumerar los programas ellos mismos?" Entonces sí puedes enumerar programas. Esto es esencialmente un problema de programación genética. Ver :

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

Aquí los programas se crean, ejecutan y evalúan (con un valor de aptitud resultante, donde el valor óptimo = 42 ), al igual que con los algoritmos genéticos, así que sí, esto proporcionaría su enumeración. Además, a lo largo de varias generaciones, puede hacer que evolucione su programa para producir 42 .