El teorema de Curtis-Hedlund-Lyndon es una caracterización matemática de los autómatas celulares en términos de su dinámica simbólica . Lleva el nombre de Morton L. Curtis , Gustav A. Hedlund y Roger Lyndon ; en su artículo de 1969 que establece el teorema, Hedlund acreditó a Curtis y Lyndon como co-descubridores. [1] Se le ha llamado "uno de los resultados fundamentales de la dinámica simbólica". [2]
El teorema establece que una función de un espacio de desplazamiento a sí misma representa la función de transición de un autómata celular unidimensional si y solo si es continua (con respecto a la topología de Cantor ) y equivariante (con respecto al mapa de desplazamiento). De manera más general, afirma que los morfismos entre dos espacios de cambio (es decir, asignaciones continuas que se conmutan con el cambio) son exactamente aquellas asignaciones que pueden definirse uniformemente mediante una regla local.
La versión del teorema en el artículo de Hedlund se aplicó solo a autómatas finitos unidimensionales, pero Richardson (1972) publicó poco después una generalización a celosías enteras de mayor dimensión , [3] y se puede generalizar aún más de celosías a grupos discretos . Una consecuencia importante del teorema es que, para los autómatas celulares reversibles , la dinámica inversa del autómata también puede ser descrita por un autómata celular.
Definiciones
Un alfabeto es cualquier conjunto finito de símbolos, que puede considerarse como los estados de las células en un autómata celular . Una configuración es una secuencia bi-infinita de símbolos del alfabeto:
- ..., x -2 , x -1 , x 0 , x 1 , x 2 , ... .
Una posición en una configuración es un número entero , el índice de uno de los símbolos de la secuencia; las posiciones pueden considerarse como las células de un autómata celular. Un patrón es un conjunto finito de posiciones y una asignación de símbolos a cada una de estas posiciones.
El espacio de turno es el conjunto de todas las configuraciones posibles sobre un alfabeto dado. Se le puede dar la estructura de un espacio topológico de acuerdo con la topología de Cantor , en el que los conjuntos abiertos fundamentales son los conjuntos de configuraciones que coinciden con cualquier patrón único y los conjuntos abiertos son uniones arbitrarias de conjuntos abiertos fundamentales. En esta topología, una función f de configuraciones a configuraciones es continua si, para cualquier patrón fijo p que define un conjunto abierto fundamental P , el conjunto f −1 ( P ) de configuraciones mapeadas por f en P puede describirse por sí mismo mediante a (posiblemente infinito) conjunto S de los patrones, con la propiedad de que una configuración pertenece a f -1 ( P ) si y sólo si coincide con un patrón en S .
El mapa de cambios es una función continua particular s en el espacio de cambios que transforma una configuración x en una nueva configuración y en la que cada símbolo se desplaza una posición desde su posición anterior: es decir, para cada entero i , y i = x i - 1 . Una función f es equivariante bajo el mapa de cambios si la transformación en las configuraciones descritas por f conmuta con el mapa de cambios; es decir, para cada configuración x , debe darse el caso de que f ( s ( x )) = s ( f ( x )) . Intuitivamente, esto significa que cada posición de la configuración se actualiza mediante f utilizando la misma regla que todas las demás posiciones.
Un autómata celular se define mediante una regla para calcular el nuevo valor de cada posición en una configuración basada solo en los valores de las celdas en una vecindad finita fija previa que rodea la posición, con todas las posiciones de la configuración actualizándose simultáneamente en función de la misma. actualizar la regla. Es decir, el nuevo valor de una posición es una función únicamente de los valores de las celdas de su vecindad en lugar de depender de manera más general de un número ilimitado de celdas de la configuración anterior. La función f que usa esta regla para mapear una configuración del autómata celular en su configuración sucesora es necesariamente equivariante con respecto al mapa de cambios, asumiendo que todas las posiciones usan la misma regla de actualización. También es necesariamente continuo en la topología de Cantor: si p es un patrón fijo, que define un conjunto abierto fundamental P , entonces f −1 ( P ) está definido por un conjunto finito de patrones, las asignaciones a las celdas en la vecindad de p que hacer que f produzca p . El teorema de Curtis-Hedlund-Lyndon establece que estas dos propiedades son suficientes para definir los autómatas celulares: toda función equivariante continua es la regla de actualización de un autómata celular.
Prueba
Ceccherini-Silberstein y Coornaert proporcionan la siguiente demostración del teorema de Curtis-Hedlund-Lyndon. [4]
Suponga que f es una función equivariante de desplazamiento continua en el espacio de desplazamiento. Para cada configuración x , sea p el patrón que consiste en el símbolo único que aparece en la posición cero de f ( x ) . Por continuidad de f , debe existir un patrón finito q en x tal que, si las posiciones fuera de q se cambian arbitrariamente pero las posiciones dentro de q se fijan a sus valores en x , entonces el resultado de aplicar f permanece igual en la posición cero . De manera equivalente, debe existir un conjunto abierto fundamental Q x tal que x pertenece a Q x y tal que para cada configuración y en Q x , f ( x ) y f ( y ) tiene el mismo valor en la posición cero. Estos conjuntos abiertos fundamentales Q x (para todas las configuraciones posibles x ) forman una cubierta abierta del espacio de turno. Sin embargo, el espacio de desplazamiento es un espacio compacto : es un producto de espacios topológicos finitos con el alfabeto como sus puntos, por lo que la compacidad se deriva del teorema de Tychonoff . Por compacidad, cada cubierta abierta tiene una subcubierta finita. El conjunto finito de posiciones que aparecen en esta subcubierta finita puede usarse como la vecindad de la posición cero en una descripción de f como una regla de autómata celular.
La misma prueba se aplica de manera más general cuando el conjunto de posiciones enteras se reemplaza por cualquier grupo discreto G , el espacio de configuraciones se reemplaza por el conjunto de funciones de G a un alfabeto finito, y la equivariancia de desplazamiento se reemplaza por equivariancia bajo la acción de G sobre sí mismo. En particular, se aplica a los autómatas celulares definidos en una cuadrícula de números enteros de cualquier dimensión.
Contraejemplo de alfabetos infinitos
Considere el espacio de secuencias bi-infinitas de enteros y defina una función f desde este espacio a sí mismo de acuerdo con la regla de que, si f ( x ) = y , entonces para cada posición i , y i = x i + x i . Esta regla es la misma para cada posición, por lo que es equivariante de desplazamiento. Y se puede demostrar que es continuo de acuerdo con la topología de Cantor: para cada patrón finito p en y , hay un patrón en x con como máximo el doble de posiciones que obliga a f a generar p , que consta de las celdas en p junto con las celdas cuyos valores se copian en p . Sin embargo, a pesar de ser continua y equivariante, f no es una regla de autómata celular, porque el valor de cualquier celda puede depender potencialmente del valor de cualquier otra celda en lugar de depender solo de las celdas en cualquier vecindario finito fijo a priori. [4]
Aplicación a autómatas celulares reversibles
Se dice que un autómata celular es reversible cuando cada configuración del autómata tiene exactamente un predecesor. De ello se sigue, mediante un argumento de compacidad, que la función que asigna cada configuración a su predecesora es en sí misma continua en el espacio de cambio, y claramente también es invariante de cambio. Por lo tanto, según el teorema de Curtis-Hedlund-Lyndon, la dinámica inversa del tiempo del autómata celular puede generarse en sí misma utilizando una regla de autómata celular diferente. [3] Sin embargo, la vecindad de una celda en el autómata inverso puede ser significativamente mayor que la vecindad de la misma celda en el autómata delantero. [5] [6]
Generalización
Se puede generalizar la definición de autómata celular a aquellos mapas que están definidos por reglas para calcular el nuevo valor de cada posición en una configuración basada en los valores de las celdas en una vecindad finita pero variable que rodea la posición. En este caso, como en la definición clásica, la regla local es la misma para todas las celdas, pero la vecindad también es función de la configuración alrededor de la posición.
El contraejemplo dado anteriormente para un mapa continuo y equivariante de desplazamiento que no es un autómata celular clásico, es un ejemplo de un autómata celular generalizado . Cuando el alfabeto es finito, la definición de autómatas celulares generalizados coincide con la definición clásica de autómatas celulares debido a la compacidad del espacio de desplazamiento.
Los autómatas celulares generalizados fueron propuestos por Sobottka & Gonçalves (2016) [7] donde se demostró que corresponden a mapas continuos de desplazamiento-equivariante.
Ver también
Referencias
- ^ Hedlund, Gustav A. (1969), "Endomorfismos y automorfismos de los sistemas dinámicos de cambio", Teoría de sistemas matemáticos , 3 (4): 320–375, doi : 10.1007 / BF01691062.
- ^ Šunić, Zoran (2014), "Autómatas y grupos celulares, por Tullio Ceccherini-Silberstein y Michel Coornaert (reseña del libro)", Boletín de la American Mathematical Society , 51 (2): 361–366, doi : 10.1090 / S0273-0979 -2013-01425-3.
- ^ a b Richardson, Daniel (1972), "Teselaciones con transformaciones locales", Journal of Computer and System Sciences , 6 : 373–388, doi : 10.1016 / S0022-0000 (72) 80009-6 , MR 0319678.
- ^ a b Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010), "Teorema 1.8.1 (teorema de Curtis-Hedlund)", Autómatas y grupos celulares , Monografías de Springer en matemáticas, Springer-Verlag, p. 20, ISBN 978-3-642-14033-4.
- ^ Margenstern, Maurice (2007), Autómatas celulares en espacios hiperbólicos - Tomo I, Volumen 1 , Archivos contemporáneos, p. 134, ISBN 978-2-84703-033-4.
- ^ Kari, Jarkko (2005), "Autómatas celulares reversibles" (PDF) , Desarrollos en la teoría del lenguaje , Lecture Notes in Computer Science, 3572 , Springer-Verlag, págs. 2–23, doi : 10.1007 / 11505877_5.
- ^ Sobottka, Marcelo; Gonçalves, Daniel (2016), Una nota sobre la definición de códigos de bloque deslizante y el Teorema de Curtis-Hedlund-Lyndon , arXiv : 1507.02180 , Bibcode : 2015arXiv150702180S.