Creo firmemente que, dadas las reglas de Conway Juego de la vida y una configuración inicial - no es decidible por una Máquina de Turing si un patrón dado emergerá, y mucho menos como un patrón estable, ya sea estático, en movimiento y/o en rotación.
¿Cómo se puede demostrar esto?
Supongo que este tipo de incomputabilidad iría mucho más allá de la "simple" imprevisibilidad de los sistemas no lineales.
El juego de la vida de Conway puede simular una máquina de Turing universal lo que significa que es efectivamente indecidible por reducción a partir del problema de detención.
Puedes programar esta máquina de Turing en el juego de la Vida para que construya algún patrón cuando se detenga que no se produzca mientras esté en marcha. Entonces el patrón se construirá si y sólo si la máquina de Turing se detiene.
¿Es ésta la lección que hay que aprender? ¿La posible aparición de un patrón en un autómata celular con un patrón inicial dado es indecidible si el autómata es lo suficientemente complejo como para poder simular una máquina de Turing universal?
¡+1 por conocer la referencia original! Recuerdo haber leído sobre la completitud de Turing de la Vida, pero no podía recordar o encontrar un enlace para donde fue originalmente declarado y / o demostrado . Gracias, Alex. Ahora, a la caza de un enlace a una versión en línea de estos procedimientos de los días cavernícolas-ARPAnet de la informática ... Hazme saber si sabes dónde encontrarlo. Probablemente exista en algún lugar de la celulosa.
Lamentablemente, no lo tengo en formato electrónico, así que tal vez puedas publicar el enlace aquí si tu caza tiene éxito.
Un enlace está aquí dx.doi.org/10.1145/800290.811303 pero se necesita una suscripción para obtener el texto completo. ¿Cómo de completa es esta prueba? Tengo la impresión de que las pruebas completas de la universalidad de la vida no aparecieron hasta mucho antes de 1974.
Esta podría ser una forma de empezar a probarlo:
El Juego de la Vida de Conway es Turing completo Es posible simular una máquina de Turing universal dentro del Juego de la Vida.
Decidir si una máquina de Turing se detendrá o continuará infinitamente para una entrada es la "Problema de la parada" . No es posible tener un algoritmo general que decida el Problema de Parada para todas las entradas posibles de una máquina de Turing simulada en el Juego de la Vida.
Por lo tanto, el problema de detención también es indecidible para entradas arbitrarias en subconjuntos particulares de patrones iniciales en el Juego de la Vida: específicamente aquellos que implementan una simulación de la máquina de Turing.
De ahí a poder decir que no hay ningún patrón general o algoritmo para decidir el resultado final de la ejecución de la Vida de Conway en cualquier patrón arbitrario, debería haber un pequeño paso, salvo que se simule realmente la ejecución de la Vida de Conway en ese patrón arbitrario concreto.
Por lo tanto, no existe un algoritmo general para decidir el resultado final de la Vida sobre un patrón inicial o para decidir el patrón de parada sobre un patrón inicial, excepto para ejecutar realmente la simulación.
Y puesto que no hay ningún atajo para simular la Vida de Conway en un patrón, no hay ninguna forma algorítmica de predecir el resultado de la Vida en un patrón inicial, por lo que no es posible decidir el problema de detención de la Vida.
Lo que me cuesta ver son los pasos intermedios de mi pregunta original: Dado que el Juego de la Vida de Conway es Turing completo, ¿cómo se deduce que no se puede decidir la aparición de un patrón determinado? (¡Dos o tres pasos intermedios serían bienvenidos!) ¿O es todo obvio?
@Hans-Stricker, no hay ningún paso intermedio adicional. $$ $$ La vida de Conway es equivalente a una máquina de Turing ya que es completa de Turing, por lo que el Problema de Parada se aplica igualmente a cualquier patrón de la Vida de Conway. La única manera de decidir un problema de detención es ejecutando realmente la simulación: no hay atajos para simular un sistema completo de Turing. Prácticamente no hay un paso intermedio entre mostrar que un sistema es Turing completo y poder deducir que el Problema de Halting es indecidible para él, como dice Peter Shor en su respuesta y comentarios.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
1 votos
Probablemente sea cierto, pero no está claro cómo demostrarlo y por qué (puede requerir un esfuerzo considerable).
1 votos
¿Por qué "por qué"? Sería un caso claro, porque el futuro -por ejemplo, de la evolución- no puede preverse en principio.
2 votos
@Hans: El nombre "vida" no significa realmente que sea una simulación de la vida real. Ciertamente hay problemas algorítmicos indecidibles que están más cerca de la evolución real que el juego de Conway.
0 votos
Pero supongo que no habrá problemas algorítmicos indecidibles que sean considerablemente más sencillo que el juego de Conway.
0 votos
Pero tal vez pueda darme una pista, ¿dónde se han respondido ya preguntas comparables?
0 votos
Problema de detención, por ejemplo. Consideremos una secuencia de sustituciones $u_i\to v_i$ , donde $u_i, v_i$ son palabras. Empieza con una palabra $w$ . Pregunta: ¿una determinada letra $f$ aparecen en cualquier palabra obtenida tras una serie de sustituciones. Se necesitan muy pocas reglas de sustitución (tres, creo, tal vez incluso 2) para conseguir la indecidibilidad.
0 votos
@Peter: Yo también he visto esto. Pero no me ha dado ninguna pista para responder a mi pregunta. (Véase mi comentario a la respuesta de sleepless in beantown).
0 votos
@Steve: Ahora entiendo lo que has querido decir: El juego de Conway es sólo una más problema indecidible, no más relevante para la "vida" que el problema de Halting. Puede que tengas razón. De todos modos: El juego de Conway se refiere a la formación de patrones en un sentido muy comprensible.
1 votos
@Hans: Sí, eso es lo que quería decir. El problema de Halting también tiene que ver con la formación de patrones, sólo que los patrones son unidimensionales. Creo que la popularidad del juego de Convay se debe a su nombre y no a su simplicidad. Si llamaras a la máquina de Turing "máquina de la vida y/o de la muerte", también sería mucho más popular :)
0 votos
@Steve: Yo habría adivinado que los patrones del problema de Halting son 0-dimensionales: "Stop y/o go".
1 votos
@Hans: Depende de la interpretación. Si $f$ es el estado de detención, entonces el problema es donde $f$ aparecerá alguna vez. Así que $f$ es el patrón. Puedes ver las palabras como intervalos multicolores. Un movimiento es una recolocación de un determinado subintervalo pequeño de acuerdo con una colección finita de reglas, y el problema es si un determinado color o combinación de colores aparecerá alguna vez. Siempre se puede suponer que sólo hay dos colores. Eso es la "vida" de una dimensión.
0 votos
@Steve: Gracias, eso es esclarecedor. Tengo que pensar en el Problema de la Parada.
0 votos
¿Cuál es la conexión con los sistemas integrables?
0 votos
@Mariano: integrable = solucionable = computable = decidible. Si encuentras esta etiqueta inapropiada, por favor, siéntete libre de eliminarla.
0 votos
Hmm. "Sistemas integrables" tiene un significado técnico bastante diferente. Volver a etiquetar...