Autómatas celulares reversibles: definición, propiedades y aplicaciones

[ES]En este trabajo nos centraremos en los autómatas celulares (ACs) reversibles. Estos ACs se ca-racterizan por el hecho de que cada configuración tiene un único predecesor. Por tanto, dada cualquier configuración, podemos determinar su evolución hacia atrás en el tiempo. Fundamentalmente, los ACs reversibles son muy útiles para modelar sistemas dinámicos que son reversibles en el tiempo, en particular, sistemas que evolucionan de acuerdo con las leyes de la mecánica clásica. En el primer capítulo daremos la definición matemática de AC, estudiaremos la topología del espacio de configuraciones y probaremos el teorema de Curtis-Hedlund-Lyndon que caracteriza a los ACs. En el segundo capítulo veremos la definición de AC reversible y estudiaremos varias propiedades relacionadas con la inyectividad y la epiyetividad para simplificar la condición de reversibilidad. En el tercer capítulo veremos el teorema más conocido sobre los ACs, el teorema del Jardín del Edén, relacionado con ACs que tiene configuraciones sin predecesores. Dedicaremos el cuarto capítulo a un estudio más detallado de los ACs unidimensionales. Primero veremos que es posible simplificar la reversibilidad de un AC a su inyectividad sobre configuraciones periódicas y posteriormente usaremos gráficos de Bruijn para estudiar a los ACs. En el quinto capítulo trataremos los ACs particionados, los cuales resultan un método simple de construir ACs reversibles, y mostraremos que los ACs reversibles unidimensionales son Turing completos. En el sexto y último capítulo discutiremos las posibles aplicaciones de los ACs reversibles.
[EN]In this work we will focus on reversible cellular automata (RCA). RCA are characterized by the fact that every configuration has a single predecessor. Therefore, given any configuration, we can determine its evolution backwards in time. Crucially, RCA are very useful for modeling dynamical systems which are reversible in time, in particular, systems that evolve according to the laws of classical mechanics. In the first chapter we will give the mathematical definition of CA, we will study the topology of the configuration space and we will prove the Curtis-Hedlund-Lyndon theorem that characterizes CA. In the second chapter we will see the defini-tion of RCA and we will study various properties relating to injectivity and surjectivity in order to simplify the reversibility condition. In the third chapter we will see the best known theorem about CA, the Garden of Eden theorem, relating to CA which have configurations without pre-decessors. We will dedicate the fourth chapter to a more detailed study of one-dimensional CA. First we will see that it is possible to simplify the reversibility of CA to their injectivity over periodic configurations and then we will use de Bruijn graphs to study these CA. In the fifth chapter we will discuss partitioned CA, which are a simple method of constructing RCA, and we will show that one-dimensional RCA are Turing complete. In the sixth and final chapter we will discuss possible applications of RCA.