¿Una versión ruidosa del juego de la vida de Conway admite la computación universal?

30

Citando Wikipedia , "[El juego de la vida de Conway] tiene el poder de una máquina universal de Turing: es decir, cualquier cosa que se pueda calcular algorítmicamente se puede calcular dentro del Juego de la vida de Conway".

¿Se extienden dichos resultados a las versiones ruidosas de Conway's Game of Life? La versión más simple es que después de cada ronda, cada célula viva muere con una pequeña probabilidad y cada célula muerta cobra vida con una pequeña probabilidad (independientemente).ts

Otra posibilidad es considerar la siguiente variante probabilística de la regla del juego en sí.

  • Cualquier célula viva con menos de dos vecinos vivos muere con probabilidad .1t
  • Cualquier célula viva con dos o tres vecinos vivos vive con probabilidad de la próxima generación.1t
  • Cualquier célula viva con más de tres vecinos vivos muere con probabilidad .1t
  • Cualquier célula muerta con exactamente tres vecinos vivos se convierte en una célula viva con probabilidad .1t

Pregunta: ¿Estas versiones ruidosas del Juego de la Vida todavía admiten cálculos universales? Si no, ¿qué se puede decir sobre su "poder computacional"?

La información relacionada sobre el poder computacional de los autómatas celulares y las versiones ruidosas de autómatas celulares también serán muy apreciadas.

(Esta pregunta se desarrolló a partir de esta pregunta sobre MathOverflow. La respuesta de Vincent Beffara sobre MO dio referencias interesantes para resultados relacionados sobre aspectos computacionales de autómatas celulares ruidosos).

Gil Kalai
fuente
2
@vzn 1) no, esta no es la "pregunta real", es una pregunta completamente diferente; La pregunta de Gil es sobre la robustez de un modelo computacional simple al ruido, no sobre el poder de la aleatoriedad; 2) Los TM con una cinta aleatoria no son más poderosos que los TM deterministas, vea esta respuesta: cstheory.stackexchange.com/a/1415/4896
Sasho Nikolov
2
La verdadera pregunta aquí es si las versiones estocásticas / ruidosas del "Juego de la vida" aún admiten la computación. (Si estas versiones admiten cálculos en P, entonces su poder puede llegar hasta BPP). Es posible que el poder computacional de estas versiones estocásticas del juego de la vida sea mucho menor.
Gil Kalai
3
Quizás estoy afirmando lo obvio, pero puede duplicar una configuración suficientes veces para garantizar con alta probabilidad que una versión de la configuración ni siquiera tenga una celda invertida. Mi creencia personal es que podemos hacerlo mucho, mucho mejor, pero al menos es un límite inferior simple.
user834
44
No estoy seguro de que la pregunta esté bien definida. Supongamos que . Me parece que es posible que pueda encontrar una computadora que se ocupe de todos los errores de un bit en el "Juego de la vida", ofreciéndole cómputo tolerante a fallas a menos que obtenga de forma espontánea un gran bloque de errores a la vez. Pero no creo que nada pueda ser robusto contra todos los errores. Por ejemplo, supongamos que los errores crean espontáneamente un adversario malévolo determinado a interrumpir el cálculo. Es posible que pueda mostrar que su cálculo tiene éxito con probabilidad pero falla con probabilidad . ¿Esto cuenta? > 1 - 10 - 9 > 10 - 10000t=109>1109>10-10000
Peter Shor
2
Peter, si tu cálculo tiene éxito con probabilidad 2/3, estoy feliz.
Gil Kalai

Respuestas:

8

Aquí hay algunas referencias "cercanas", por lo que vale. Parecería que el camino a seguir en esta pregunta es reducirlo a una pregunta sobre "máquinas ruidosas de Turing", que han sido estudiadas (algo recientemente) y que aparentemente son el área relevante más cercana de la literatura. La respuesta básica / general / razonable parece ser que si la TM puede resistir / corregir el ruido (como se demuestra en estas referencias), es muy probable que la CA también pueda, dentro de algunos límites / umbrales.

La cuestión de cómo reducir una "CA ruidosa" a una "TM ruidosa" (y viceversa) es más abierta. Puede que no sea difícil, pero no parece haber investigaciones publicadas en el área. Otro problema es que el TM ruidoso es un modelo nuevo y, por lo tanto, puede haber múltiples formas (¿naturales?) De representar un TM ruidoso. Por ejemplo, los siguientes documentos analizan las interrupciones en la función de transición de estado, pero otro modelo natural son las interrupciones en los símbolos de la cinta (¿el último está más conectado a las CA ruidosas?). Puede haber alguna relación entre los dos.

  • Máquina de Turing tolerante a fallas por Ilir Capuni, 2012 (tesis doctoral)

    La máquina de Turing es el modelo universal de computación más estudiado. Esta tesis estudia la cuestión de si existe una máquina de Turing que pueda calcular de manera confiable incluso cuando las violaciones de su función de transición se producen independientemente entre sí con alguna pequeña probabilidad.

    En esta tesis, demostramos la existencia de una máquina de Turing que con un polinomio aéreo puede simular cualquier otra máquina de Turing, incluso cuando está sujeta a fallas del tipo anterior, respondiendo así a la pregunta que estuvo abierta durante 25 años.

  • Una máquina de Turing que resiste ráfagas aisladas de fallas por Ilir Capuni y Peter Gacs, 2012
  • Máquinas ruidosas de Turing por Eugene Asarin y Pieter Collins, 2005
(Otra pregunta: ¿podría haber alguna conexión entre TM ruidosas y máquinas de Turing probabilísticas ?)

vzn
fuente
7

Gil pregunta si el GL está olvidando todo acerca de su configuración inicial en el tiempo independientemente del tamaño, cuando cada celda "desobedece" la función de transición independientemente de otras celdas con una pequeña probabilidad.

Que yo sepa, esto no es conocido por el GL. Sin embargo, es una pregunta muy interesante. Si puede soportar el ruido, debería preservar su universalidad.

Una breve descripción del estado del arte es la siguiente.

  1. La regla de Toom puede salvar un poco para siempre las fallas que ocurren independientemente entre sí con una pequeña probabilidad.
  2. Se creía ampliamente (la conjetura de las tasas positivas) que todas las 1 CA oscuras son ergódicas hasta que P. Gacs construyó su CA multiescala que puede simular cualquier otra CA con sobrecarga moderada incluso cuando se somete al ruido mencionado anteriormente.
  3. La pregunta si la regla G (acs) K (urdiumov) L (evin) puede ahorrar un poco para siempre en presencia del ruido anterior aún está abierta. El Parque Kihong , un estudiante de Gacs, demostró que no será así cuando el ruido sea parcial.
  4. Cuando se publicó el trabajo en 2, M. Blum preguntó si una TM puede continuar con su cálculo si en cada paso, la transición no se realiza de acuerdo con la función de transición con alguna pequeña probabilidad independientemente de otros pasos, suponiendo que la información almacenada en la cinta lejos de la cabeza no se descompone. I. Capuni (otro estudiante de Gacs) dio una respuesta positiva en 2012.
usuario8719
fuente
"Si no es ergódico, preservará su universalidad" ... ¿tiene alguna evidencia de esta afirmación? ¿Es este un teorema? ¿Dónde se prueba? Creo que el trabajo de Gacs muestra que esto es cierto en al menos un caso, pero no veo cómo eso demuestra que vale para el juego de la vida de Conway.
Peter Shor
Gracias por señalarlo. No es un teorema sino una pregunta abierta interesante. No ser ergódico parece demasiado poco para pedir una declaración tan fuerte.
user8719
3

Para empezar, tenga en cuenta que la investigación en Game of Life de Conway aún está en curso y los desarrollos futuros pueden presentar una solución mucho menos complicada.

Ahora entonces. Curiosamente, este es un tema que en realidad está tan en línea con la biología y la física cuántica como con la informática tradicional. La pregunta en la raíz del asunto es si algún dispositivo puede resistir efectivamente alteraciones aleatorias a su estado. La respuesta simple y llana es que es imposible hacer una máquina que sea perfectamenteresistente a tales cambios aleatorios. Por supuesto, esto es cierto de la misma manera que la mecánica cuántica podría causar eventos aparentemente imposibles. Lo que impide que estos eventos ocurran (lo que lleva a la mayoría de las personas a declararlos estrictamente imposibles) es la probabilidad increíblemente pequeña de que tal evento tenga lugar. Una probabilidad tan pequeña por la diferencia a gran escala entre el nivel cuántico y el nivel humano. Es igualmente posible hacer una máquina de estados que sea resistente a pequeños grados de cambio aleatorio simplemente haciéndola tan grande y redundante que cualquier "cambio" observado sea efectivamente cero, pero se supone que este no es el objetivo. Suponiendo que esto se puede lograr de la misma manera que los animales y las plantas son resistentes a la radiación o al daño físico.

La pregunta entonces puede no ser cómo evitar que las perturbaciones de bajo nivel causen demasiado daño, sino cómo recuperarse de la mayor cantidad de daño posible. Aquí es donde la biología se vuelve relevante. Los animales y las plantas en realidad tienen esta misma capacidad a nivel celular. (Tenga en cuenta: estoy hablando de las células en el sentido biológico en esta respuesta) Ahora, en el juego de la vida de Conway, la noción de construir un dispositivo informático a escala de células individuales es atractivo (después de todo, hace que tales creaciones sean mucho más pequeñas y más eficientes), pero si bien podemos construir computadoras que se reproducen por sí mismas ( ver Géminis ), esto ignora el hecho de que el objeto constructor en sí mismo puede dañarse por las perturbaciones.

Otra forma, más resistente, que puedo ver para resolver esto es construir computadoras a partir de partes redundantes auto reproductivas (piense en células biológicas) que realizan sus operaciones, se reproducen y son reemplazadas.

En este punto podemos ver otro paralelo interesante del mundo real. Estas perturbaciones de bajo nivel son similares a los efectos de la radiación. Esto es más apreciable cuando considera el tipo de daño que se puede hacer a sus autómatas celulares. Es fácil desencadenar la falla en cascada o la "muerte" de una célula en el Juego de la vida de Conway, de forma muy similar a lo que sucede con muchas células expuestas a la radiación. Pero existe la posibilidad de mutación en el peor de los casos, creando una célula "cancerosa" que continúa reproduciendo copias defectuosas de sí mismo que no ayudan en el proceso computacional o producen resultados incorrectos.

Como he dicho, es imposible construir un sistema que sea completamente infalible, solo puede hacer que sea menos probable que una falla comprometa todo el sistema. Por supuesto, la pregunta fundamental aquí es realmente "son simulaciones probabilísticas en sí mismas Turing completo" que ya se ha decidido que es cierto . Hubiera respondido esa pregunta fundamental inicialmente, salvo que no fue lo que usted preguntó.

Hawkwing
fuente
¡Guauu! ¡Gracias por el voto en coche! En cualquier caso, he revisado mi publicación, agregando información y fuentes. Lo siento, no tuve tiempo de hacerlo cuando publiqué esto por primera vez. Podría modificar esta respuesta aún más para que se ajuste a los estándares de la comunidad, si no fuera por el hecho de que no se dio ninguna razón para el voto negativo.
Hawkwing
55
Como no votante, no veo cómo esto responde la pregunta de Gil. Usted aborda la cuestión de si "cualquier dispositivo puede resistir efectivamente alteraciones aleatorias de su estado", que no es lo que Gil preguntó.
András Salamon
Gracias (sin sarcasmo esta vez) por el comentario, András Salamon. Yo mismo lo consideraría útil, pero todavía soy un nuevo usuario en este sitio de desbordamiento. De todos modos, lo siento, mi respuesta parece fuera de tema. Tal vez abordé la pregunta más libremente de lo que pretendía, pero siento que mi respuesta responde a la pregunta original respondiendo una pregunta similar y luego trazando paralelos entre los dos. ¿Es esto quizás demasiado indirecto una forma de responder?
Hawkwing
0

Me recuerda a xkcd 505: A Bunch of Rocks .

Cualquier computadora del mundo real está sujeta a algún nivel de ruido. La simulación de una computadora universal en el universo infinito ideal de Conway's Life tendrá un tiempo medio entre fallas dependiendo de los detalles de ingeniería de su diseño. Calculará de manera confiable durante un período cuantificable probabilísticamente, de manera no confiable para un período de acumulación de errores, y luego no en absoluto .

Esperaría que una lógica difusa o un modelo de superposición cuántica demuestre claramente qué confiabilidad se debe esperar de una construcción en particular. Es posible que desee simular los resultados esperados de varios componentes, en lugar de iterar sobre todas sus celdas, en cualquier grado que puedan aislarse entre sí. Uno podría ser capaz de cuantificar la interferencia esperada de los componentes que fallan. Un algoritmo genético debería ser la mejor manera de desarrollar componentes de falla- {tolerar, resistir, corregir} con MTBF tan grandes como se desee para una distribución de ruido dada.

usuario130144
fuente
(votación misteriosa aquí) Una respuesta cuantitativa sería muy especulativa. No puede haber una respuesta más precisa que "sí, condicionalmente" sin una amplia experimentación en alguna implementación elegida de un UTM. Una computadora normal en un entorno de alta radiación sigue siendo prácticamente una UTM, aunque solo sea brevemente.
user130144