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 . Recibe su nombre en honor a Morton L. Curtis , Gustav A. Hedlund y Roger Lyndon ; en su artículo de 1969 en el que enuncia el teorema, Hedlund atribuyó a Curtis y Lyndon el mérito de ser codescubridores. [1] Se lo ha denominado "uno de los resultados fundamentales en dinámica simbólica". [2]
El teorema establece que una función de un espacio de desplazamiento hacia 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 a la función de desplazamiento). De manera más general, afirma que los morfismos entre dos espacios de desplazamiento cualesquiera (es decir, funciones continuas que conmutan con el desplazamiento) son exactamente aquellas funciones que pueden definirse de manera uniforme mediante una regla local.
La versión del teorema en el artículo de Hedlund se aplicaba sólo a autómatas finitos unidimensionales, pero poco después Richardson (1972) publicó una generalización a redes enteras de dimensiones superiores [3] y puede generalizarse aún más desde redes a grupos discretos . Una consecuencia importante del teorema es que, para autómatas celulares reversibles , la dinámica inversa del autómata también puede ser descrita por un autómata celular.
Un alfabeto es un conjunto finito de símbolos, que pueden considerarse como los estados de las células de un autómata celular . Una configuración es una secuencia bi-infinita de símbolos del alfabeto:
Una posición en una configuración es un número entero , el índice de uno de los símbolos en la secuencia; las posiciones pueden considerarse como las celdas 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 desplazamiento es el conjunto de todas las configuraciones posibles sobre un alfabeto dado. Se le puede dar la estructura de un espacio topológico según la topología de Cantor , en la 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 defina un conjunto abierto fundamental P , el conjunto f −1 ( P ) de configuraciones mapeadas por f en P puede describirse a su vez mediante un conjunto (posiblemente infinito) S de patrones, con la propiedad de que una configuración pertenece a f −1 ( P ) si y solo si coincide con un patrón en S.
El mapa de desplazamiento es una función continua particular s en el espacio de desplazamiento que transforma una configuración x en una nueva configuración y en la que cada símbolo se desplaza una posición respecto de 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 desplazamiento si la transformación en las configuraciones descritas por f conmuta con el mapa de desplazamiento; 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 cualquier otra posición.
Un autómata celular se define por una regla para calcular el nuevo valor de cada posición en una configuración basada únicamente en los valores de las celdas en un vecindario finito fijado previamente que rodea la posición, con todas las posiciones de la configuración actualizándose simultáneamente en función de la misma regla de actualización. Es decir, el nuevo valor de una posición es una función únicamente de los valores de las celdas en su vecindario 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 utiliza esta regla para mapear una configuración del autómata celular en su configuración sucesora es necesariamente equivariante con respecto al mapa de desplazamiento, por el supuesto de que todas las posiciones utilizan la misma regla de actualización. También es necesariamente continua en la topología de Cantor: si p es un patrón fijo, que define un conjunto abierto fundamental P , entonces f −1 ( P ) se define por un conjunto finito de patrones, las asignaciones a celdas en el vecindario de p que hacen que f produzca p . El teorema de Curtis-Hedlund-Lyndon establece que estas dos propiedades son suficientes para definir a los autómatas celulares: cada función equivariante continua es la regla de actualización de un autómata celular.
Ceccherini-Silberstein y Coornaert proporcionan la siguiente prueba del teorema de Curtis-Hedlund-Lyndon. [4]
Supóngase que f es una función continua equivalente a un desplazamiento en el espacio de desplazamientos. 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 pertenezca a Q x y tal que para cada configuración y en Q x , f ( x ) y f ( y ) tengan 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 desplazamientos. Sin embargo, el espacio de desplazamientos es un espacio compacto : es un producto de espacios topológicos finitos con el alfabeto como sus puntos, por lo que la compacidad se deduce del teorema de Tichonoff . Por compacidad, cada cubierta abierta tiene una subcubierta finita. El conjunto finito de posiciones que aparecen en esta subcubierta finita se puede utilizar como 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 desde G hasta un alfabeto finito, y la equivariancia por desplazamiento se reemplaza por la equivariancia bajo la acción de G sobre sí misma. En particular, se aplica a autómatas celulares definidos en una cuadrícula de números enteros de cualquier dimensión.
Consideremos el espacio de secuencias bi-infinitas de números enteros, y definamos una función desde este espacio hacia sí misma según 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 por desplazamiento. Y se puede demostrar que es continua según 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 generar p , que consiste en las celdas en p junto con las celdas cuyos valores se copian en p . Sin embargo, a pesar de ser continua y equivariante, 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 fijado previamente. [4]
Se dice que un autómata celular es reversible cuando cada configuración del autómata tiene exactamente un predecesor. De ello se deduce, 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 desplazamientos, y es claramente también invariante respecto de los desplazamientos. Por lo tanto, mediante el teorema de Curtis-Hedlund-Lyndon, la dinámica invertida en el tiempo del autómata celular puede generarse mediante una regla de autómata celular diferente. [3] Sin embargo, la vecindad de una célula en el autómata inverso puede ser significativamente mayor que la vecindad de la misma célula en el autómata directo. [5] [6]
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 un vecindario finito 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 el vecindario también es una función de la configuración alrededor de la posición.
El contraejemplo dado anteriormente para una función continua y equivalente a un desplazamiento que no es un autómata celular clásico, es un ejemplo de autómata celular generalizado . Cuando el alfabeto es finito, la definición de autómata celular generalizado coincide con la definición clásica de autómata celular debido a la compacidad del espacio de desplazamiento.
Los autómatas celulares generalizados fueron propuestos por Sobottka y Gonçalves (2017) [7] , donde se demostró que corresponden a mapas de desplazamiento continuo equivariantes.
