Autómata celular elemental

Image en les 256 regles d'autómata celular elemental (fer clic o tocar per a ampliar).

En matemàtiques i teoria de computabilidad, un autómata celular elemental és un autómata celular unidimensional a on hi ha dos estats possibles (etiquetages 0 i 1) i la regla per a determinar l'estat d'una cèlula en la pròxima generació depén solament de l'estat actual de la cèlula i els seus dos veïns immediats. Est és un dels models possibles més senzills de computació. No obstant, hi ha un autómata celular elemental (regla 110, definit avall) capaç de computació universal.

El sistema de numeració

Existixen 8 = 2³ configuracions possibles per a una cèlula i els seus dos veïns immediats. La regla que definix l'autómata celular té que especificar l'estat resultant per a cada una d'estes possibilitats, és dir, que hi ha 256 = 2²³ possibles autómates celulars elementals. Stephen Wolfram va propondre un esquema, conegut com el còdic Wolfram, per a assignar a cada regla un número de 0 a 255. Cada configuració actual possible està escrita en orde, 111, 110, ..., 001, 000, i l'estat resultant per a cada una d'estes configuracions està escrit en el mateix orde i interpretat com la representació binaria d'un número entero. Este número es pren com el número de regla de l'autómata. Per eixemple, 110_d=96_d+14_d escrit en binario és 01101110₂. De modo que la regla 110 es definix per mig de la regla de transició:

111	110	101	100	011	010	001	000	Patró actual	P=(L,C,R)
0	1	1	0	1	1	1	0	Estat nou per al centre de la cèlula	N110d=(C+R+CR+LCR)%2

Reflexions i complements

A pesar de que hi ha 256 regles possibles, moltes d'estes són equivalents a les demés a través d'una transformació senzilla de la geometria subjacent. La primera transformació d'este tipo és reflexió a través d'un eix vertical i el resultat d'aplicar esta transformació a una regla donada es denomina regla reflectida. Estes regles exhibiran el mateix comportament fins a la reflexió a través d'un eix vertical, i per lo tant són equivalents en un sentit computacional.

Per eixemple, si la definició de la regla 110 es reflectix a través d'una llínea vertical, s'obté la següent regla (regla 124):

111	110	101	100	011	010	001	000	Patró actual	P=(L,C,R)
0	1	1	1	1	1	0	0	Estat nou per a la cèlula central	N112d+12d=124d=(L+C+LC+LCR)%2

Les regles que són les mateixes que la seua regla reflectida es diuen amphichiral . Dels 256 autómates celulars elementals, 64 són anfíquicos.

La segona transformació d'este tipo consistix en intercanviar les funcions de 0 i 1 en la definició. El resultat d'aplicar esta transformació a una regla donada es diu regla complementària. Per eixemple, si esta transformació s'aplica a la regla 110, obtenim la següent regla:

Patró actual	000	001	010	011	100	101	110	111
Estat nou per a la cèlula central	1	0	0	1	0	0	0	1

I, despuix de reordenar, descobrim que esta és la regla 137:

Patró actual	111	110	101	100	011	010	001	000
Estat nou per a la cèlula central	1	0	0	0	1	0	0	1

Hi ha 16 regles que són les mateixes que les seues regles complementàries.

Finalment, les dos transformacions anteriors poden aplicar-se successivament a una regla per a obtindre la regla complementària reflectida. Per eixemple, la regla complementària reflectida de la regla 110 és la regla 193. Hi ha 16 regles que són iguals a les seues regles complementàries reflectides.

Dels 256 autómates celulars elementals, hi ha 88 que són desiguals baix estes transformacions.