Autómata celular reversible

Un autómata celular reversible unidimensional en nou estats. En cada pas, cada cèlula copia la forma de la seua esquerra i el color de la seua dreta.

Un autómata celular reversible, és un autómata celular en el que cada configuració té un predecessor únic. És una cuadrícula regular de celes, cada una de les quals conté un estat dibuixat a partir d'un conjunt finit d'estats. Esta cuadrícula té una regla per a actualisar totes les celes simultàneament en funció dels estats dels seus veïns, de modo que l'estat anterior de qualsevol cela abans d'una actualisació es pot determinar únicament a partir dels estats actualisats de totes les celes.

Autómata Finito

Un autómata finit, és una màquina abstracta que canvia d'estat depenent de l'entrada que reba, i la seua eixida, algunes voltes, pot estar formada per una atra cadena. Els autómates finitos són utilisats, generalment, per a reconéixer llenguages regulars, és dir, una paraula es podrà considerar vàlida, només si pertany a un llenguage determinat. Estos són utilisats per a modelar el comportament de dispositius mecànics o de sistemes naturals, sistemes el comportament actual dels quals depén del passat.

Un autómata finit (AF) es definix com una tupla

AF = (Q,,,Q0,F)

A on:

1. Q = {q0,q1,...,qn}, el conjunt (finito) dels estats interns de l'unitat de control.
2. Un alfabet Σ, cridat alfabet d'entrada o alfabet de cinta. Totes les cadenes que processa AF pertanyen a Σ∗.
3. La funció δ de transició de l'autómata

δ : Q×Σ → Q (q,s)

δ → δ(q,s)

1. Q0∈ Q, estat inicial.
2. F ⊆ Q, conjunt d'estats finales o d'acceptació. F deu ser distint de ∅; és dir, deu haver per lo manco un estat d'acceptació.

L'autómata rep una cadena d'entrada M. Quan l'autómata rep el primer símbol de M est es troba en l'estat inicial o Q0. La funció de transició δ, també cridada dinàmica de l'autómata, és la llista d'instruccions que utilisa AF per a processar totes les entrades. Depenent de l'entrada, l'autómata canvia d'estat segons la funció de transició. Una volta l'autómata haja escanejat un dels símbols este no pot retornar a est o sobreescribirlo, quan l'autómata rep l'últim dels símbols este finalisara el procés i depenent si el llenguage de la cadena pertany al llenguage reconegut per l'autómata, este es detindrà en un estat d'acceptació o rebuig.

Si per als estats p,q existix x ∈ *, tal que δ(p,x)→q, es diu que q és alcanzable des de p. AF és conexo si existix un estat q existix un x ∈ * tal que  δ(Q0,x)= q. Es diu que p i q són fortament conexos si p és alcanzable des de q i viceversa, AF és fortament conexo si per a cada parell d'estats de AF són fortament conexos.

Existixen 2 tipos d'autómates finitos, els determinista i els no determinista els quals seran definits a continuació.

Autómata finit determinista

Un autómata finit determinista (AFD) té per a cada estat q i per a cada sımbolo s ∈ Σ, la funció de transició δ(q,s) sempre està definida i és un únic estat. Açò implica que qualsevol cadena d'entrada es processa completament i de manera única.

Autómata finit no determinista

Un autómata finit no determinista (AFN) es diferencia d'un AFD per la possibilitat de que una entrada es puga processar de vàries formes o que hi haja processaments abortats.

Un AFN pot ser definit com una tupla, que a excepció de la funció de transició ∆, el restant de components tenen el mateix significat que en un autómata finit.

AFN = (Q,,∆,Q0,F)

La funció ∆ de transició de l'autómata ∆ està definida com :

∆: Q×Σ → ℘(Q)

(q,s) 7→ ∆(q,s) = {Q_i1,Q_i2,...,Q_ik}

a on ℘(Q) és el conjunt de subconjunt de Q.

Si ben açò implicaria que solament els autómates determinista poden ser reversibles, degut a que solament estos poden tindre en els seus estats una relació un a un en els seus successors.

Màquina de Turing

La màquina de Turing, presentada per Alan Turing en 1936, és el model matemàtic d'un dispositiu que es comporta com un autómata finit i que dispon d'una cinta de llongitut infinita en la que es poden llegir, escriure o borrar símbols.

Existixen atres versions en vàries cintes, determinista o no, etc., pero totes són equivalents (respecte als llenguages que accepten).

Un de les teoremes més importants sobre les màquines de Turing és que poden simular el comportament d'una computadora (almagasenament i unitat de control). Per això, si un problema no pot ser resolt per una d'estes màquines, llavors tampoc pot ser resolt per una computadora (problema indecidible, NP).La notació de les màquines de Turing és senzilla i exacta, per lo que és més cómodo treballar en elles a l'hora d'estudiar qué problemes són decidibles (P) i quins indecidibles (NP).

Pel moment la relació d'inclusió entre P i NP està per demostrar, encara que sí sabem que

P⊆NP

Ademés, direm que els llenguages acceptats pels Autómates Finitos (Determinista o no, en o sense transicions-ε, en o sense pila...) poden ser acceptats també per alguna màquina de Turing.

Definició de la Màquina de Turing

Cridem Màquina de Turing (o MT) a

M=(Q,Σ,T,δ,q0,B,F)

a on

• Q és el conjunt finit d'estats que denotarem per

q0,q1,q2,...

• Σ és l'alfabet, que és el conjunt finit de símbols d'entrada.
• Τ és el conjunt de símbols de cinta, L'alfabet és un subconjunt de Τ.
• q₀ és l'estat inicial, és l'estat en el que es troba inicialment la MT.
• B és un element de Σ, és el símbol en blanc. Es troba en totes les caselles de la cinta que no tenen un símbol d'entrada.
• F és el conjunt d'estats finals.
• δ és la funció de transicions.

L'expressió

δ(q,X)=(p,I,D)

indica que en l'estat q, si el cap de la MT senyala al símbol de cinta X, llavors la MT escriu el símbol de cinta I en la casella actual (canvia X per I ) i mou el cap una casella cap a D (D pot ser dreta, R; o esquerra, L) i passa a l'estat p.

La cinta de la MT està formada per infinites caselles. Inicialment, la paraula d'entrada (una concatenació de símbols de l'alfabet) es troba escrita en caselles consecutives de la cinta i el cap senyala al primer símbol de la paraula. Totes les atres caselles (cap a l'esquerra i la dreta) contenen el símbol en blanc.

Llenguage d'una Màquina de Turing

El llenguage d'una Màquina de Turing

M=(Q,Σ,T,δ,q0,B,F)

és

L(M):={w∈Σ∗ : q0w⊢∗ αpβ,p∈F,α,β∈T∗}

És dir, les w de Σ^* tals que la màquina de Turing alcança un estat d'acceptació.

Autómates Celulars

Els Autómates Celulars sorgixen en la necessitat del matemàtic hongarés John von Neumann, que intentava modelar una màquina que fora capaç de autorreplicarse aplegant a un model matemàtic sobre una ret rectangular.

El model inicial va ser interpretat en els seus principis com un conjunt de cèlules que creixen, es reproduïxen i moren a mida que passa el temps, a esta similitut se li deu el nom d'Autómata Celular.

Un Autómata Celular és un model matemàtic per a un sistema dinàmic compost per un conjunt de celes o cèlules que adquirixen distints estats o valors; Estos estats són alterats d'un instant a un atre en unitats de temps discretes, és dir que es pot quantificar en valors sancers. d'esta manera este conjunt de cèlules conseguixen una evolució segons una determinada expressió matemàtica, que és sensible als estats de les cèlules veïnes, la qual es coneix com a regla de transició local.

L'aspecte fonamental d'estos autómates són la seua capacitat de conseguir una série de propietats que sorgixen de la pròpia dinàmica local a través del pas del temps i no des d'un inici, depenent esta d'única i exclusivament la configuració inicial del sistema.

Elements d'un Autómata Celular

La definició d'un Autómata Celular requerix mencionar els seus elements bàsics:

• Arregle Regular:

Ya siga un pla de 2 dimensions o un espai-dimensional, est és l'espai d'evolucions, i cada divisió homogénea d'apany és cridada cèlula.

• Conjunt d'Estats:

És finit, i cada element o cèlula de l'apany pren un valor d'este conjunt d'estats. També es denomina alfabet.Pot ser expressat en valors o colors.

• Configuració Inicial:

Consistix en assignar un estat a cada una de les cèlules de l'espai d'evolució inicial del sistema.

• Veïnats:

Definix el conjunt contigu de cèlules i posició relativa respecte a cada una d'elles. A cada veïnat diferent correspon un element del conjunt d'estats.

• Funció Local:

És la regla d'evolució que determina el comportament de l'Autómata Celular. Es conforma d'una cèlula central i els seus veïnats.Definix cóm deu canviar d'estat cada cèlula, depenent dels estats anteriors dels seus veïnats. Pot ser una expressió algebraica o un grup d'equacions.

Tipos de Veïnats

Per als Autómates Celulars, el concepte de veïnat és indispensable, ya que sense ell, la funció de transició o funció d'evolució carix de sentit, posat  que esta depén de l'estat de les cèlules veïnes. Dos tipos de veïnats més comunament utilisades són:

• Veïnat de Moore:

Es definix com el conjunt de les huit celes que rodegen una cela central en un enreixat quadrat.

• Veïnat de Von Neumann:

Es definix com el conjunt de les quatre celes que rodegen ortogonalmente a una cela central en un enreixat quadrat bidimensional.

Aplicacions

Els Autómates Celulars tenen una complexitat prou elevada depenent directament de les regles plantejades per a la seua evolució. En ser estos sistemes dinàmics, són prou rellevants en l'estudi i representació d'estos mateixos, com lo poden ser la propagació de malalties en estar en contacte en els teus veïns, la regulació del trànsit en la teua ciutat, el comportament de distintes espècies dins d'una reacció química, i inclusivament a visualisar com és el comportament i la velocitat a la que s'escampa un rumor. Un eixemple clar i conciso sobre el funcionament i capacitat de processament d'un Autómata Celular, és “El Joc de la Vida” que en solament un parell de regles conseguix crear una cantitat immensa de possibilitats com a configuracions que sense importar el pas del temps de queden sense cap canvi, algunes atres que tenen cicles, és dir, a partir d'una série de passos (periodo) des d'una configuració inicial, tornen a aplegar a esta mateixa configuració inicial i este cicle continua, este sistema és tan interessant que múltiples matemàtics ho han analisat i varen terminar demostrant que este sistema té tanta capacitat expressiva com qualsevol computador, qualsevol càlcul que este puga fer, el joc de la vida ho pot representar en configuracions inicials adequades, ya que este (teòricament parlant) és equivalent a una màquina universal de turing, és dir, tot lo que es pot computar algorítmicamente es pot computar en el joc de la vida.

La regla 30 (Rule 30) és una regla d'un AC unidimensional introduït en el 83 per Stephen Wolfram, lo interessant de Rule 30 és que produïx patrons aleatoris a partir d'unes regles molt ben definides, el seu us principal és el de generar números de manera aleatòria i es va propondre com un possible sifrat per a la criptografia.

El joc de la vida

Vore també: Joc de la vida

Va ser dissenyat pel matemàtic britànic John Horton Conway en 1970 i publicat per primera volta en la revista Scientific American. El joc es va tornar en centre d'estudi per la comunitat científica, ya que és equivalent a una Màquina universal de Turing, és dir, que tot lo que es pot computar algorítmicamente es pot computar en el Joc de la vida.

El joc es basa en un Autómata celular simple en una cuadrícula de dos dimensions a on les cèlules poden tindre dos estats possibles: viva o morta, que es poden representar en booleanos com  1 o 0. La funció d'evolució està donada per les següents regles:

• Per a una cèlula morta en exactament tres cèlules veïnes vives, el seu estat passa de morta a viva per a la següent tanda, representant que la cèlula ha “naixcut”.
• Una cèlula viva en 2 o 3 cèlules veïnes vives seguix viva, en un atre cas mor.

El joc va escomençar com un desafiu matemàtic i en connotacions significatives en l'àmbit de les ciències de la computació, pero pronte va passar a ser l'eix central de la comunitat científica per la cantitat de patrons i desenrolls o “evolucions” que tenien uns sistemes depenent única i exclusivament de la configuració inicial d'este Autómata Celular.

La versatilitat de la qual disponen estos autómates nos permet considerar l'estudi de molts sistemes dinàmics en la vida tant natural com a quotidiana del planeta i de la humanitat, per a trobar solucions rellevants a problemes actuals, o simplement per a ajudar-nos a comprendre una miqueta més el món que nos rodeja. Un cas particular interessant per a l'estudi de sistemes basats en termodinàmica general i física de partícules és el concepte de invertibilidad, a lo que associarem una classe particular d'Autómates cridats Autómates Celulars Invertibles.