¿Cómo puedo probar que la función de evolución de Game of Life es continua?

El Juego de la Vida de Conway es un autómata celular, pero también un sistema dinámico discreto. En todos los papeles, libros, notas que he leído sobre él, nunca nunca nunca se demuestra que su función de evolución es continua. Traté de mostrarlo yo mismo, pensando que era trivial, pero resulta ser más desafiante de lo que pensaba. Esto es lo que hice hasta ahora:

Dado que trabajamos en una cuadrícula ortogonal infinita, denoto el espacio con el que trabajamos como S Z 2 , dónde S = { 0 , 1 } con 0 de pie para una celda muerta y 1 por uno vivo. Por lo tanto un punto X ∈ S Z 2 sería un infinito 2 − secuencia dimensional de ceros y unos.

A continuación, definí una distancia en este espacio, diciendo d ( X , y ) = 0 si X = y y de otra manera d ( X , y ) = 2 − k dónde k es el mayor entero tal que X [ − k , k ] 2 = y [ − k , k ] 2 es decir, dos puntos X , y están cerca si están de acuerdo en un cuadrado { − k , … , k } 2 . Ya logré demostrar que S Z 2 es un espacio métrico compacto.

Donde ahora estoy atascado, es que no tengo ni idea de cómo aplicar la definición de continuidad en Game of Life. Aquí está la definición: Let ( X , d ) Sea un espacio métrico. Un mapa F : X ↦ X se llama continuo si para todo X ∈ X y ϵ > 0 existe un d > 0 tal que:

d ( X , y ) < d ⟹ d ( F ( X ) , F ( y ) ) < ϵ

Y sé que la función de evolución es continua. Según un famoso teorema de Hedlund, un mapa F : S Z 2 ↦ S Z 2 es un autómata celular si y solo si el mapa es continuo y conmuta con el mapa de desplazamiento σ .

Si tiene algún consejo, idea o sugerencia ... ¡sería muy apreciado! Tengo mucha curiosidad por saber cómo llegar allí ahora, ¡Gracias!

Podría ser más fácil usar la definición de continuidad en términos de preimágenes de conjuntos abiertos. Luego puede usar el hecho de que los conjuntos de cilindros dan una base de conjuntos abiertos , donde un conjunto de cilindros asociado a un parche finito puntiagudo dado es el conjunto de todos los elementos en el espacio que tienen ese parche finito en el origen. Debido a que el juego de la vida se define en términos de reglas locales, esencialmente obtienes continuidad automáticamente desde esta perspectiva.
¡Gracias, usar la definición de continuidad en términos de conjuntos y la noción de conjuntos de cilindros ayudó mucho! Entendí la idea de la prueba y encontré una versión de una prueba en las notas de una conferencia en línea, publicaré el enlace para marcar esta pregunta como 'resuelta'. @DanRust gracias por la ayuda!

Respuestas (2)

Dejar norte = { − 1 , 0 , 1 } 2 denote la vecindad de la celda en el origen y, para cualquier conjunto S ⊂ Z 2 de coordenadas de celda, sume Minkowski

S + norte = { ( i + a , j + b ) : ( i , j ) ∈ S , ( a , b ) ∈ norte }
denote la vecindad combinada de todas las celdas en S . Entonces
X S + norte = y S + norte ⟹ F ( X ) S = F ( y ) S .

Dado que, en particular, [ − k , k ] 2 + norte = [ − k − 1 , k + 1 ] 2 , resulta que

X [ − k − 1 , k + 1 ] 2 = y [ − k − 1 , k + 1 ] 2 ⟹ F ( X ) [ − k , k ] 2 = F ( y ) [ − k , k ] 2 ,
y así que
d ( X , y ) ≤ 2 − k − 1 ⟹ d ( F ( X ) , F ( y ) ) ≤ 2 − k .
Por lo tanto, para cualquier ϵ > 0 ,
d ( X , y ) < ϵ 2 ⟹ d ( F ( X ) , F ( y ) ) < ϵ .

Tenga en cuenta que esta prueba no depende de la regla de evolución específica del Juego de la vida de Conway de ninguna manera, excepto por el hecho de que la evolución de cada celda está determinada únicamente por los estados de las celdas en su vecindad. La misma prueba se aplica a cualquier otro autómata celular determinista definido en la vecindad de Moore de 3 × 3 celdas, y puede generalizarse directamente a cualquier autómata celular determinista definido en cualquier vecindad finita.

Parecía que el ϵ − d De hecho, la definición no era el mejor enfoque, según el comentario de Dan, encontré estas notas de clase donde dan una respuesta completa a mi pregunta.

Si alguien más lo necesitará en el futur, aquí está el enlace. El teorema que responde a esta pregunta se puede encontrar en la página 106 . Estas notas de clase fueron extremadamente útiles ya que definen todo y es la primera vez que veo una reseña sobre autómatas celulares donde combinan topología y dinámica simbólica para describir Game of Life y CA en general.

¿Cómo puedo probar que la función de evolución de Game of Life es continua?
RespuestasAquíPolítica de privacidad1y, 0v