Autómata celular reversible
Un autómata finito determinista (AFD) tiene para cada estado q y para cada sımbolo s ∈ Σ, la función de transición δ(q,s) siempre está definida y es un único estado.
Si bien esto implicaría que solo los autómatas deterministas pueden ser reversibles, debido a que solo estos pueden tener en sus estados una relación uno a uno con sus sucesores.
Existen otras versiones con varias cintas, deterministas o no, etc., pero todas son equivalentes (respecto a los lenguajes que aceptan).
Por el momento la relación de inclusión entre P y NP está por demostrar, aunque sí sabemos que
Llamamos Máquina de Turing (ó MT) a M=(Q,Σ,T,δ,q0,B,F) donde q0,q1,q2,...
Todas las otras casillas (hacia la izquierda y la derecha) contienen el símbolo en blanco.
Los Autómatas Celulares surgen con la necesidad del matemático húngaro John von Neumann, que intentaba modelar una máquina que fuera capaz de autorreplicarse llegando a un modelo matemático sobre una red rectangular.
Un Autómata Celular es un modelo matemático para un sistema dinámico compuesto por un conjunto de celdas o células que adquieren distintos estados o valores; Estos estados son alterados de un instante a otro en unidades de tiempo discretas, es decir que se puede cuantificar con valores enteros.
Es la regla de evolución que determina el comportamiento del Autómata Celular.
Los Autómatas Celulares tienen una complejidad bastante elevada dependiendo directamente de las reglas planteadas para su evolución.
Al ser estos sistemas dinámicos, son bastante relevantes en el estudio y representación de estos mismos, como lo pueden ser la propagación de enfermedades al estar en contacto con tus vecinos, la regulación del tránsito en tu ciudad, el comportamiento de distintas especies dentro de una reacción química, e inclusive a visualizar como es el comportamiento y la velocidad a la que se esparce un rumor.
Véase también: Juego de la vida Fue diseñado por el matemático británico John Horton Conway en 1970 y publicado por primera vez en la revista Scientific American.
El juego se basa en un Autómata celular simple con una cuadrícula de dos dimensiones donde las células pueden tener dos estados posibles: viva o muerta, que se pueden representar con booleanos como 1 o 0.
La versatilidad de la cual disponen estos autómatas nos permite considerar el estudio de muchos sistemas dinámicos en la vida tanto natural como cotidiana del planeta y de la humanidad, para encontrar soluciones relevantes a problemas actuales, o simplemente para ayudarnos a comprender un poco más el mundo que nos rodea.
Típicamente, tal autómata usa más de una partición en bloques, y rota entre las mismas.
Para que un autómata celular de bloque sea reversible, es necesario y suficiente que la transformación aplicada a los bloques individuales en cada paso del autómata sea reversible.
El método de Morita puede simular las configuraciones finitas de cualquier autómata irreversible en el que hay un estado "inactivo" o "muerto", de modo que si una celda y todos sus vecinos están inactivos, la celda permanece inactiva en el siguiente paso.
Un autómata celular unidimensional encontrado por Patt (1971) usa un vecindario que consta de cuatro celdas contiguas.
