miniaturadeimagen|Un autómata celular reversible unidimensional con nueve estados. En cada paso, cada célula copia la forma de su izquierda y el color de su derecha. Un autómata celular reversible, es un autómata celular en el que cada configuración tiene un predecesor único. Es una cuadrícula regular de celdas, cada una de las cuales contiene un estado dibujado a partir de un conjunto finito de estados. Esta cuadrícula tiene una regla para actualizar todas las celdas simultáneamente en función de los estados de sus vecinos, de modo que el estado anterior de cualquier celda antes de una actualización se puede determinar únicamente a partir de los estados actualizados de todas las celdas.
Autómata Finito Un autómata finito, es una máquina abstracta que cambia de estado dependiendo de la entrada que reciba, y su salida, algunas veces, puede estar formada por otra cadena. Los autómatas finitos son utilizados, generalmente, para reconocer lenguajes regulares, es decir, una palabra se podrá considerar válida, sólo si pertenece a un lenguaje determinado. Estos son utilizados para modelar el comportamiento de dispositivos mecánicos o de sistemas naturales, sistemas cuyo comportamiento actual depende del pasado.
Un autómata finito (AF) se define como una tupla
AF = (Q,,,Q0,F)
Donde:
Q = {q0,q1,...,qn}, el conjunto (finito) de los estados internos de la unidad de control. Un alfabeto Σ, llamado alfabeto de entrada o alfabeto de cinta. Todas las cadenas que procesa AF pertenecen a Σ∗. La función δ de transición del autómata
δ : Q×Σ → Q (q,s)
δ → δ(q,s)
Q0∈ Q, estado inicial. F ⊆ Q, conjunto de estados finales o de aceptación. F debe ser distinto de ∅; es decir, debe haber por lo menos un estado de aceptación.
El autómata recibe una cadena de entrada M. Cuando el autómata recibe el primer símbolo de M este se encuentra en el estado inicial o Q0. La función de transición δ, también llamada dinámica del autómata, es la lista de instrucciones que utiliza AF para procesar todas las entradas. Dependiendo de la entrada, el autómata cambia de estado según la función de transición. Una vez el autómata haya escaneado uno de los símbolos este no puede retornar a este o sobreescribirlo, cuando el autómata recibe el último de los símbolos este finalizara el proceso y dependiendo si el lenguaje de la cadena pertenece al lenguaje reconocido por el autómata, este se detendrá en un estado de aceptación o rechazo.
Si para los estados p,q existe x ∈ *, tal que δ(p,x)→q, se dice que q es alcanzable desde p. AF es conexo si existe un estado q existe un x ∈ * tal que δ(Q0,x)= q. Se dice que p y q son fuertemente conexos si p es alcanzable desde q y viceversa, AF es fuertemente conexo si para cada par de estados de AF son fuertemente conexos.
Existen 2 tipos de autómatas finitos, los deterministas y los no deterministas los cuales serán definidos a continuación.
Autómata finito determinista 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. Esto implica que cualquier cadena de entrada se procesa completamente y de manera única.
Autómata finito no determinista Un autómata finito no determinista (AFN) se diferencia de un AFD por la posibilidad de que una entrada se pueda procesar de varias formas o que haya procesamientos abortados.
Un AFN puede ser definido como una tupla, que a excepción de la función de transición ∆, el resto de componentes tienen el mismo significado que en un autómata finito.
AFN = (Q,,∆,Q0,F)
La función ∆ de transición del autómata ∆ está definida como :
∆: Q×Σ → ℘(Q)
(q,s) 7→ ∆(q,s) = {Qi1,Qi2,...,Qik}
donde ℘(Q) es el conjunto de subconjunto de Q.
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.
Máquina de Turing La máquina de Turing, presentada por Alan Turing en 1936, es el modelo matemático de un dispositivo que se comporta como un autómata finito y que dispone de una cinta de longitud infinita en la que se pueden leer, escribir o borrar símbolos.
Existen otras versiones con varias cintas, deterministas o no, etc., pero todas son equivalentes (respecto a los lenguajes que aceptan).
Uno de los teoremas más importantes sobre las máquinas de Turing es que pueden simular el comportamiento de una computadora (almacenamiento y unidad de control). Por ello, si un problema no puede ser resuelto por una de estas máquinas, entonces tampoco puede ser resuelto por una computadora (problema indecidible, NP).La notación de las máquinas de Turing es sencilla y exacta, por lo que es más cómodo trabajar con ellas a la hora de estudiar qué problemas son decidibles (P) y cuáles indecidibles (NP).
Por el momento la relación de inclusión entre P y NP está por demostrar, aunque sí sabemos que
P⊆NP
Además, diremos que los lenguajes aceptados por los Autómatas Finitos (Deterministas o no, con o sin transiciones-ε, con o sin pila...) pueden ser aceptados también por alguna máquina de Turing.
Definición de la Máquina de Turing Llamamos Máquina de Turing (ó MT) a
M=(Q,Σ,T,δ,q0,B,F)
donde
Q es el conjunto finito de estados que denotaremos por
q0,q1,q2,...
Σ es el alfabeto, que es el conjunto finito de símbolos de entrada. Τ es el conjunto de símbolos de cinta, El alfabeto es un subconjunto de Τ. q0 es el estado inicial, es el estado en el que se encuentra inicialmente la MT. B es un elemento de Σ, es el símbolo en blanco. Se encuentra en todas las casillas de la cinta que no tienen un símbolo de entrada. F es el conjunto de estados finales. δ es la función de transiciones.
La expresión
δ(q,X)=(p,Y,D)
indica que en el estado q, si la cabeza de la MT señala al símbolo de cinta X, entonces la MT escribe el símbolo de cinta Y en la casilla actual (cambia X por Y ) y mueve la cabeza una casilla hacia D (D puede ser derecha, R; o izquierda, L) y pasa al estado p.
La cinta de la MT está formada por infinitas casillas. Inicialmente, la palabra de entrada (una concatenación de símbolos del alfabeto) se encuentra escrita en casillas consecutivas de la cinta y la cabeza señala al primer símbolo de la palabra. Todas las otras casillas (hacia la izquierda y la derecha) contienen el símbolo en blanco.
Lenguaje de una Máquina de Turing El lenguaje de una Máquina de Turing
M=(Q,Σ,T,δ,q0,B,F)
es
L(M):={w∈Σ∗ : q0w⊢∗ αpβ,p∈F,α,β∈T∗}
Es decir, las w de Σ* tales que la máquina de Turing alcanza un estado de aceptación.
Autómatas Celulares 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.
El modelo inicial fue interpretado en sus principios como un conjunto de células que crecen, se reproducen y mueren a medida que pasa el tiempo, a esta similitud se le debe el nombre de Autómata Celular.
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. de esta manera este conjunto de células logran una evolución según una determinada expresión matemática, que es sensible a los estados de las células vecinas, la cual se conoce como regla de transición local.
El aspecto fundamental de estos autómatas son su capacidad de lograr una serie de propiedades que surgen de la propia dinámica local a través del paso del tiempo y no desde un inicio, dependiendo esta de única y exclusivamente la configuración inicial del sistema.
Elementos de un Autómata Celular La definición de un Autómata Celular requiere mencionar sus elementos básicos:
Arreglo Regular:
Ya sea un plano de 2 dimensiones o un espacio-dimensional, este es el espacio de evoluciones, y cada división homogénea de arreglo es llamada célula.
Conjunto de Estados:
Es finito, y cada elemento o célula del arreglo toma un valor de este conjunto de estados. También se denomina alfabeto.Puede ser expresado en valores o colores.
Configuración Inicial:
Consiste en asignar un estado a cada una de las células del espacio de evolución inicial del sistema.
Vecindades:
Define el conjunto contiguo de células y posición relativa respecto a cada una de ellas. A cada vecindad diferente corresponde un elemento del conjunto de estados.
Función Local:
Es la regla de evolución que determina el comportamiento del Autómata Celular. Se conforma de una célula central y sus vecindades.Define cómo debe cambiar de estado cada célula, dependiendo de los estados anteriores de sus vecindades. Puede ser una expresión algebraica o un grupo de ecuaciones.
Tipos de Vecindades Para los Autómatas Celulares, el concepto de vecindad es indispensable, puesto que sin él, la función de transición o función de evolución carece de sentido, puesto que esta depende del estado de las células vecinas. Dos tipos de vecindades más comúnmente utilizadas son:
Vecindad de Moore:
Se define como el conjunto de las ocho celdas que rodean una celda central en un enrejado cuadrado.
Vecindad de Von Neumann:
Se define como el conjunto de las cuatro celdas que rodean ortogonalmente a una celda central en un enrejado cuadrado bidimensional.
Aplicaciones 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. Un ejemplo claro y conciso sobre el funcionamiento y capacidad de procesamiento de un Autómata Celular, es “El Juego de la Vida” que con solo un par de reglas logra crear una cantidad inmensa de posibilidades como configuraciones que sin importar el paso del tiempo de quedan sin ningún cambio, algunas otras que tienen ciclos, es decir, a partir de una serie de pasos (periodo) desde una configuración inicial, vuelven a llegar a esta misma configuración inicial y este ciclo continúa, este sistema es tan interesante que múltiples matemáticos lo han analizado y terminaron demostrando que este sistema tiene tanta capacidad expresiva como cualquier computador, cualquier cálculo que este pueda hacer, el juego de la vida lo puede representar con configuraciones iniciales adecuadas, ya que este (teóricamente hablando) es equivalente a una máquina universal de turing, es decir, todo lo que se puede computar algorítmicamente se puede computar en el juego de la vida.
La regla 30 (Rule 30) es una regla de un AC unidimensional introducido en el 83 por Stephen Wolfram, lo interesante de Rule 30 es que produce patrones aleatorios a partir de unas reglas muy bien definidas, su uso principal es el de generar números de manera aleatoria y se propuso como un posible cifrado para la criptografía.
El juego de la vida 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 tornó en centro de estudio por la comunidad científica, dado que es equivalente a una Máquina universal de Turing, es decir, que todo lo que se puede computar algorítmicamente se puede computar en el Juego de la vida.