Regla 90
En l'estudi matemàtic dels autómates celulars, la regla 90 és un autómata celular elemental basat en l'o exclusiu o funció. Consistix en una matriu unidimensional de celes, cada una de les quals pot contindre un valor 0 o 1. En cada pas temporal, tots els valors se substituïxen simultàneament pel XOR dels seus dos valors veïns.[1] Martin, Odlyzko i Wolfram (1984) ho criden «l'autómata celular no trivial més simple»,[2] i es descriu àmpliament en el llibre de Stephen Wolfram de 2002 A New Kind of Science.[3]
Quan es partix d'una única cèlula viva, la regla 90 té un diagrama espai-temporal en forma de triàngul de Sierpiński. El comportament de qualsevol atra configuració pot explicar-se com una superposició de còpies d'este patró, combinades per mig de la funció exclusiva. Qualsevol configuració en només finitamente moltes cèlules distintes de zero es convertix en un replicador que eventualment ompli la matriu en còpies de sí mateixa. Quan la regla 90 s'inicia a partir d'una configuració inicial aleatòria, la seua configuració seguix sent aleatòria en cada pas temporal. El seu diagrama espai-temporal forma moltes «finestres» triangulars de diferents tamanys, patrons que es formen quan una fila consecutiva de celes es convertix simultàneament en zero i llavors les celes en valor 1 es mouen gradualment cap a esta fila des d'abdós extrems.
Alguns dels primers estudis sobre la regla 90 es varen realisar en relació en un problema no resolt de la teoria de números, la conjectura de Gilbreath, sobre les diferències de número primo consecutius. Esta regla també està relacionada en la teoria de números d'una atra forma, a través de la seqüència de Gould. Esta seqüència conta el número de cèlules distintes de zero en cada pas de temps despuix d'iniciar la regla 90 en una sola cèlula viva. Els seus valors són potències de dos, en exponents iguals al número de dígits distints de zero en la representació binaria del número de pas. Atres aplicacions de la Regla 90 han inclós el disseny de tapissos.
Cada configuració de la Regla 90 té exactament quatre predecessores, atres configuracions que formen la configuració donada despuix d'un sol pas. Per lo tant, a diferència de molts atres autómates celulars com el Jugue de la Vida de Conway, la Regla 90 no té Jardí del Edén, una configuració sense predecessors. Proporciona un eixemple d'autómata celular que és sobreyectiva (cada configuració té un predecessor) pero no inyectivo (té conjunts de més d'una configuració en el mateix successor). Del teorema del Jardí del Edén es deduïx que la regla 90 és localment inyectiva (totes les configuracions en el mateix successor varien en un número infinit de celes).
Descripció
[editar | editar còdic]Regles
[editar | editar còdic]
La regla 90 és un autómata celular elemental. Açò significa que consistix en una matriu unidimensional de celes, cada una de les quals conté un únic valor binario, 0 o 1. Una assignació de valors a totes les celes es denomina configuració. Una assignació de valors a totes les celes es denomina configuració. l'autómata rep una configuració inicial i va passant per atres configuracions en una seqüència de passos temporals discrets. En cada pas, totes les celes s'actualisen simultàneament. Una regla preestablida determina el nou valor de cada cela en funció del seu valor anterior i dels valors de les seues dos celes veïnes. Totes les celes obedixen la mateixa regla, que pot presentar-se com una fòrmula o com una taula de regles que especifica el nou valor per a cada combinació possible de valors veïns.[1]
En el cas de la regla 90, el nou valor de cada cela és l'o exclusiu dels dos valors veïns. Equivalentement, el següent estat d'este autómata en particular es rig per la següent taula de regles:[1]
| Patró actual | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| Nou estat per a la cèlula central | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
Nom
[editar | editar còdic]El nom de la regla 90 procedix de la notació binaria-decimal de Stephen Wolfram per a regles d'autómates celulars unidimensionals. Per a calcular la notació de la regla, concatene els nous estats de la taula de regles en un únic número binario i convertixca el número en decimal: 010110102 = 9010.[1] La regla 90 també s'ha denominat autómata de Sierpiński, per la característica forma de triàngul de Sierpiński que genera,[4] i autómata celular de Martin-Odlyzko-Wolfram per les primeres investigacions d'Olivier Martin, Andrew M. Odlyzko i Stephen Wolfram (1984) sobre este autómata.[5]
Propietats
[editar | editar còdic]Aditividad, superposició i descomposició
[editar | editar còdic]Una configuració de la regla 90 pot dividir-se en dos subconjunts de celes que no interactuen entre sí. Un d'estos dos subconjunts està format per les celes en posicions pares en passos de temps pares i les celes en posicions impars en passos de temps impars. L'atre subconjunt està format per les cèlules en posicions pares en passos de temps impars i les cèlules en posicions impars en passos de temps pares. Cada u d'estos dos subconjunts pot vore's com un autómata celular en només la seua mitat de celes.[6] La regla per a l'autómata dins de cada u d'estos subconjunts és equivalent (llevat per un desplaçament de mija cela per pas de temps) a un atre autómata celular elemental, la Regla 102, en la que el nou estat de cada cela és l'exclusiu o del seu antic estat i el seu veí dret. És dir, el comportament de la Regla 90 és essencialment el mateix que el de dos còpies intercaladas de la Regla 102.[7]
Les regles 90 i 102 es denominen autómates celulars aditius. Açò significa que, si dos estats inicials es combinen calculant l'o exclusiva de cada u dels seus estats, les seues configuracions posteriors es combinaran de la mateixa manera. En térmens més generals, es pot dividir qualsevol configuració de la regla 90 en dos subconjunts en celes distintes de zero, fer evolucionar els dos subconjunts per separat i calcular cada configuració successiva de l'autómata original com l'o exclusiva de les configuracions en els mateixos passos temporals dels dos subconjunts.[2]
Arbres atrofiados i clars triangulars
[editar | editar còdic]
L'autómata de la Regla 90 (en la seua forma equivalent en un dels dos subconjunts independents de celes alternes) es va investigar a principis dels anys 70, en un intent d'obtindre informació adicional sobre la conjectura de Gilbreath sobre les diferències de número primo consecutius. En el triàngul de números generats a partir dels cosins aplicant repetidament l'operador de diferència cap a davant, sembla que la majoria dels valors són 0 o 2. En concret, la conjectura de Gilbreath afirma que els valors situats més a l'esquerra de cada fila d'este triàngul són tots 0 o 2. Quan una subsecuencia contigua de valors en una fila del triàngul són tots 0 o 2, llavors es pot utilisar la regla 90 per a determinar la subsecuencia corresponent en la fila següent. Miller (1970) va explicar la regla per mig d'una metàfora del creiximent d'un arbre en un bosc, titulant el seu artícul sobre el tema «Boscs periòdics d'arbres atrofiados». En esta metàfora, un arbre comença a créixer en cada posició de la configuració inicial el valor de la qual és 1, i este bosc d'arbres creix llavors simultàneament, fins a una nova altura sobre el sol en cada pas temporal. Cada cela distinta de zero en cada pas temporal representa una posició ocupada per una branca creixent de l'arbre. En cada pas successiu, una branca pot créixer cap a una de les dos celes situades a la seua esquerra i dreta només quan no hi haja una atra branca competint per la mateixa cela. Un bosc d'arbres que creix segons estes regles té exactament el mateix comportament que la regla 90.[8]
A partir de qualsevol configuració inicial de la Regla 90, es pot formar un bosc matemàtic, un grafo acíclic dirigit en el que cada vèrtiç té com a màxim una aresta eixint, els arbres de la qual són els mateixos que els arbres de la metàfora de Miller. El bosc té un vèrtiç per cada parell (x,i) tal que la cela x és distinta de zero en el temps i. Els vèrtiços en el temps 0 no tenen arestes eixints; cada u forma la raïl d'un arbre en el bosc. Per a cada vèrtiç (x,i) en i distint de zero, la seua aresta eixint es dirigix a (x ± 1, i - 1), l'únic veí distint de zero de x en el pas de temps i - 1. Miller va observar que estos boscs desenrollen «clars» triangulars, regions del diagrama espai-temporal sense celes no nules delimitades per una vora inferior pla i costats diagonals. Un clar d'este tipo es forma quan una seqüència consecutiva de celes es fa zero simultàneament en un pas de temps, i llavors (en la metàfora de l'arbre) les branques creixen cap a dins, tornant a cobrir finalment les celes de la seqüència.[8]
En condicions inicials aleatòries, els llímits entre els arbres formats d'esta manera es desplacen seguint un patró aparentment aleatori, i en freqüència els arbres moren per complet. No obstant, gràcies a la teoria dels registres de desplaçament, ell i uns atres varen ser capaços de trobar condicions inicials en les que tots els arbres permaneixen vius per a sempre, el patró de creiximent es repetix periòdicament i es pot garantisar que tots els clars permaneixen llimitats en tamany.[8][9] Miller va utilisar estos patrons repetitius per a formar els dissenys dels tapissos. Alguns dels tapissos de Miller representen arbres físics; uns atres visualisen l'autómata de la Regla 90 per mig de patrons abstractes de triànguls.[8]
Triàngul de Sierpinski
[editar | editar còdic]El diagrama espai-temporal de la regla 90 és un gràfic en el que la fila i registra la configuració de l'autómata en el pas i. Quan l'estat inicial té una única cela distinta de zero, este diagrama té l'apariència del triàngul de Sierpiński, un fractal format per la combinació de triànguls en triànguls més grans. Les regles 18, 22, 26, 82, 146, 154, 210 i 218 també generen triànguls de Sierpinski a partir d'una única cela, no obstant no totes elles es creen de forma completament idèntica. Una forma d'explicar esta estructura utilisa el fet de que, en la regla 90, cada cela és l'o exclusiva de les seues dos veïnes. Com açò és equivalent a la suma en mòdul 2, es genera la versió en mòdul 2 del triàngul de Pascal. El diagrama té un 1 sempre que el triàngul de Pascal té un número impar, i un 0 sempre que el triàngul de Pascal té un número par. Esta és una versió discreta del triàngul de Sierpiński.[1][10]
El número de cèlules vives en cada fila d'este patró és una potència de dos. En la fila i-ésima, és igual a 2k, a on k és el número de dígits distints de zero en la representació binaria del número i. La seqüència d'estos números de cèlules vives,
1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 4, 4, 8, 8, 16, 4, 8, 8, 16, 16, 16, 32, … (seqüència A001316 en l'OEIS)
Es coneix com seqüència de Gould. L'única cèlula viva de la configuració inicial és un patró en dent de serra. Açò significa que en alguns passos temporals el número de cèlules vives creix de forma arbitrària, mentres que en uns atres torna a ser de només dos cèlules vives, en una freqüència infinita. La taxa de creiximent d'este patró té una forma característica d'ona creixent en dent de serra que pot utilisar-se per a reconéixer processos físics que es comporten de forma similar a la Regla 90.[4]
El triàngul de Sierpiński també es produïx de forma més sotil en l'evolució de qualsevol configuració de la Regla 90. En qualsevol pas de temps i en l'evolució de la Regla, l'estat de qualsevol cela pot calcular-se com l'exclusiu o d'un subconjunt de les celes de la configuració inicial. Eixe subconjunt té la mateixa forma que la fila i-ésima del triàngul de Sierpiński.[11]
Replicació
[editar | editar còdic]En el triàngul de Sierpiński, per a qualsevol número entero i, les files numerades per múltiples de 2i tenen celes no nules separades a lo manco 2i unitats. Per lo tant, per la propietat aditiva de la Regla 90, si una configuració inicial consistix en un patró finito P de celes no nules en esgambi menor que 2i, llavors en passos que són múltiples de 2i, la configuració consistirà en còpies de P espayades a lo manco 2i unitats d'inici a inici. Este espayat és lo suficientment ampli com per a evitar que les còpies interferixquen entre sí. El número de còpies és el mateix que el número de celes distintes de zero en la fila corresponent del triàngul de Sierpiński. Aixina, en esta regla, cada patró és un replicador: genera múltiples còpies de sí mateixa que s'estenen per la configuració, omplint finalment tota la matriu. Atres regles, com el constructor universal de Von Neumann, l'autómata celular de Codd i els bucles de Langton, també tenen replicadores que funcionen duent i copiant una seqüència d'instruccions per a construir-se a sí mateixos. En canvi, la replicació en la regla 90 és trivial i automàtica.[12]
Predecessors i Jardins del Edén
[editar | editar còdic]En la regla 90, en un entramat unidimensional infinit, cada configuració té exactament quatre configuracions predecessores. Açò es deu a que, en una predecessora, dos celes consecutives qualssevol poden tindre qualsevol combinació d'estats, pero una volta elegits els estats d'eixes dos celes, només hi ha una elecció coherent per als estats de les celes restants. Per lo tant, no hi ha Jardí del Edén en la Regla 90, una configuració sense predecessors. La configuració de la Regla 90 que consistix en una única cela distinta de zero (en totes les demés celes iguals a zero) no té predecessors que tinguen un número finito de no zeros. No obstant, esta configuració no és un Jardí del Edén perque té predecessors en infinits nonzeros.[13]
El fet de que cada configuració tinga un predecessor pot resumir-se dient que la regla 90 és suryectiva. La funció que assigna cada configuració a la seua successora és, matemàticament, una funció suryectiva. La regla 90 tampoc és inyectiva. En una regla inyectiva, cada dos configuracions diferents tenen successors diferents, pero la regla 90 té parells de configuracions en el mateix successor. La regla 90 és un eixemple d'autómata celular suryectivo pero no inyectivo. El teorema del Jardí del Edén de Moore i Myhill implica que tot autómata celular inyectivo deu ser suryectivo, pero este eixemple mostra que ho contrarie no és cert.[13][14]
Ya que cada configuració només té un número llimitat de predecessores, l'evolució de la regla 90 preserva l'entropía de qualsevol configuració. En particular, si se selecciona una configuració inicial infinita elegint l'estat de cada cela independentment a l'encert, en cada u dels dos estats en la mateixa provabilitat de ser seleccionat, llavors cada configuració posterior pot ser descrita exactament per la mateixa distribució de provabilitat.[2]
Referències
[editar | editar còdic]- ↑ 1,0 1,1 1,2 1,3 1,4 «Statistical Mechanics of Cellular Automata (1983)». web.archive.org. Consultat el 2025-02-03.
- ↑ 2,0 2,1 2,2 «Algebraic Properties of Cellular Automata (1984)». web.archive.org. Consultat el 2025-02-03.
- ↑ «Stephen Wolfram: A New Kind of Science | Online—Table of Contents» (en en). www.wolframscience.com. Consultat el 2025-02-03.
- ↑ 4,0 4,1 Physical Review I.doi:10.1103/PhysRevE.70.032101.
- ↑ Linear Algebra and Its Applications.doi:10.1016/j.laa.2005.09.002.
- ↑ Institut de Ciències, Universitat Autònoma de Pobla..
- ↑ Hokkaido Mathematical Journal.doi:10.14492/hokmj/1416837570.
- ↑ 8,0 8,1 8,2 8,3 Philosophical Transactions of the Royal Society of London, Séries A, Mathematical and Physical Sciences.doi:10.1098/rsta.1970.0003.
- ↑ Philosophical Transactions of the Royal Society of London, Séries A, Mathematical and Physical Sciences.doi:10.1098/rsta.1970.0004.
- ↑ Wikipedia.Consultat el 2025-02-04.
- ↑ Information Sciences.doi:10.1016/0020-0255(93)90030-P.
- ↑ Journal of the ACM.doi:10.1145/321495.321509.
- ↑ 13,0 13,1 Proceedings of the American Mathematical Society.doi:10.1090/S0002-9939-1975-0386350-1.
- ↑ Complex Systems.
- Este artícul conté una traducció derivada de «Regla 90» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.