¿Estado y tiempo de transmisión de la lógica y el flujo del programa?

Question

Preguntándome si alguna vez sería útil indexar cada estado posible de una aplicación usando algunas teclas de referencia ...

Es decir, digamos que tenemos un programa que comienza, que tiene tantos resultados posibles, digamos 8.

pero si cada resultado se logra a través de pasar por muchos más estados lógicos, y entre cada rama se considera un estado y se asigna a una clave.

Podría tomar mucha memoria en programas grandes, pero si pudiéramos acceder a una clave directamente (la clave podría basarse en el tiempo o la profundidad de la lógica), podríamos atravesar instantáneamente cualquiera de las situaciones posibles sin tener que comenzar todo el proceso otra vez con datos nuevos.

Piense en ello como un árbol donde los nodos sin hijos son resultados finales, y cada rama entre un nodo y sus padres o hijos es un 'estado', cada uno con una clave diferente. Entonces, mientras que solo hay 8 hojas, o los resultados finales del proceso, podría haber muchos "estados" dependiendo de la profundidad de la lógica en el árbol antes de quedarse sin hijos.

Quizás para simulaciones, pero tomaría una tonelada de memoria.

Answer 1

Ryan, la respuesta es definitivamente SÍ.

Contrariamente a la primera respuesta, el problema de la detención no prueba nada. De hecho, Ryan, lo que estás sugiriendo prueba que el problema de detención incorrecto no se aplica a las computadoras digitales reales, y he usado este ejemplo como una prueba de ello antes.

En un sistema digital determinista (es decir, un programa que se ejecuta en hardware digital real), el número de estados posibles es finito y, por lo tanto, todos los estados posibles son enumerables.

La cantidad exacta de memoria requerida para el hash sería:

(2) * (tamaño del estado del programa) * (número de estados iniciales)

El estado inicial sería su clave hash, y el estado final sería el valor hash, y luego tendría un par clave / valor para cada estado inicial.

Para un sistema operativo, el " Tamaño del estado del programa " es 2 ^ (el total de gigabits de memoria en todos los dispositivos del sistema). Obviamente, un programa tan grande, de propósito general, requeriría una cantidad poco práctica de memoria para el hash, y no sería útil de todos modos, ya que el sistema es auto-referenciado / irreduciblemente complejo (es decir, la próxima entrada del usuario depende de la salida del sistema anterior). p>

Explicación :

Esto es muy útil, porque si indexas cada estado inicial posible y lo asocias con el estado de terminación, ¡llevarías efectivamente el tiempo de ejecución de CUALQUIER PROGRAMA a cero! Por cero, me refiero a un tiempo de ejecución O (1) muy rápido: el tiempo que lleva buscar el estado de terminación (si termina).

Ejecutar un programa, comenzando por cada uno de todos los estados posibles, proporcionará una especie de mapa de estado que muestra los ciclos. Por lo tanto, el problema de la detención se resuelve, porque solo hay tres posibilidades (en realidad, cuatro colapsadas a tres) dado cualquier posible estado inicial:

1. El programa volverá a entrar en un estado encontrado anteriormente (desde el estado inicial), antes de agotar todos los estados posibles y, por lo tanto, lógicamente se interrumpirá por siempre.
2. El programa alcanza un estado identificado como " terminando " antes de que tenga la oportunidad de volver a entrar en un estado encontrado anteriormente o agotar todos los estados posibles (desde el estado inicial).

3. o 4. El programa más simple se iniciará desde un estado inicial, ingresará todos los estados posibles una sola vez, y luego no tendrá más remedio que (3) detener o (4) volver a ingresar un estado encontrado anteriormente y realizar un ciclo para siempre .

   para (int i = 0; true; i ++); // alcanzaré el valor máximo, volveré a cero, en cuyo punto habrá vuelto a entrar en el estado inicial

Entonces, básicamente, tu índice podría describirse así:

• Para cada estado inicial, hay exactamente uno o cero estados de terminación.

En otras palabras, para cada estado inicial, el programa alcanza un estado de terminación o vuelve a entrar en un estado ya encontrado desde el estado inicial y realiza ciclos infinitos.

Por lo tanto, para cualquier programa que se ejecute en hardware digital determinista , es absolutamente posible (pero a menudo no es práctico ) determinar todos sus estados y si se detiene o se repite para siempre.

• La practicidad depende únicamente de la cantidad de estados iniciales válidos que tenga (que puede reducir drásticamente con restricciones de entrada), y de cuán factible es tomarse el tiempo para ejecutar el programa para cada uno de ellos. hasta la terminación y almacenar el estado resultante en la tabla hash.

Además de forzar el tiempo de ejecución de cualquier programa en una operación O (1), otros usos del estado de captura incluyen la función de guardar el estado en los emuladores de la consola de juegos y la función de hibernación de las computadoras (aunque no es una restauración perfecta del estado, ya que la memoria del sistema debe usarse para el código que restaura el estado y es posible que alguna memoria nunca se almacene (por ejemplo, memoria GPU)).

Lo que esto prueba es que cualquier programa puede ser representado por una tabla hash. Cualquier programa puede ser representado por un mapa de transición de estado inicial a final. ¡Todos los programas se pueden simplificar a una gran función con una huella de memoria masiva!

Answer 2

Esto no sería posible resolver para un programa general. El problema de detención demuestra que es imposible determinar si un programa se detendrá. El problema de determinar si un estado dado es posible es reducible al problema de detención, por lo que tampoco puede resolverse.

Answer 3

Creo que este enfoque sería totalmente intratable para, bueno, cualquier cosa.

Como problema de búsqueda, es demasiado grande. Si suponemos que cada estado puede conducir a 10 resultados (aunque creo que este número es realmente bajo), entonces para mirar solo 20 pasos adelante, ahora tenemos que hacer un seguimiento de 200 mil millones de posibilidades.

Y recuerda que cada paso en un bucle cuenta como un punto de bifurcación. Entonces, si tenemos un código que se ve así:

for (int i=0; i < 100; i++)
    some_function();

Entonces el número de estados posibles es (número de ramas dentro de alguna_función) ^ 100

Answer 4

Si bien Josh tiene razón al decir que no puede responder a la versión más liberal de este problema debido a su ambigüedad, puede responder si coloca algunas limitaciones en su escenario. Existe una gran diferencia entre el estado de su programa y el estado de las entidades comerciales, por ejemplo.

Por ejemplo, supongamos que tiene una aplicación orientada al flujo de trabajo definida por un DFA (Máquina de estado). De hecho, podría asociar un punto dado en ese DFA con un ID de algún tipo.

Entonces sí, es manejable pero no sin restricciones.

Answer 5

Esto se hace en el nivel de función; es una técnica llamada memoración .

Answer 6

Investiga las estructuras kripke y la lógica modal. Este es un enfoque adoptado en los programas de modelado. Olvidé cuáles son los sistemas clásicos que utilizan este enfoque.