Vés al contingut

Regla 30

De la Viquipèdia, l'enciclopèdia lliure

La Regla 30 és un autòmat cel·lular binari unidimensional introduït per Stephen Wolfram el 1983.[1] Wolfram el descriu la seva "regla favorita de tots els temps"[2] i en dona detalls en el seu llibre 'A New Kind of Science'. Emprant l'esquema de classificació de Wolfram, la regla 30 és una regla de Classe III, que mostra un comportament aperiòdic i caòtic. Aquesta regla és de particular interès perquè genera patrons complexos aparentment aleatoris partir de regles simples i ben definides. Per aquest motiu, Wolfram creu que la Regla 30 i els autòmats cel·lulars en general, són la clau per entendre de quina manera regles simples generen estructures i comportament complexes a la natura. Per exemple, un patró semblant al generat per la Regla 30 apareix a la closca dels cargols con de l'espècie Conus Textile. La Regla 30 també s'ha emprat com a generador de nombres aleatoris en el programa Mathematica del mateix Wolfram, i també ha estat proposada com un possible xifrat de flux pel seu ús en criptografia.[3] No obstant això, Sipper i Tomassini han demostrat que, com a generador de nombres aleatoris, la Regla 30 exhibeix un mal comportament en una prova de khi quadrat en comparació amb altres generadors basats en autòmats cel·lular.[4] La Regla 30 s'anomena així perquè 30 és el codi Wolfram més petit que descriu el seu conjunt de regles. La imatge especular, el complement i el complement especular de la Regla 30 tenen codis Wolfram 86, 135 i 149 respectivament.

Referències

[modifica]
  1. Wolfram, S. «Statistical mechanics of cellular automata». Rev. Mod. Phys., vol. 55, 1983, pàg. 601–644. DOI: 10.1103/RevModPhys.55.601.
  2. On Starting a Long-Term Company, S. Wolfram, 2005.
  3. Wolfram, S. (1985). "Cryptography with cellular automata". Proceedings of Advances in Cryptology - CRYPTO '85: 429, Lecture Notes in Computer Science 218, Springer-Verlag [Enllaç no actiu] Vegeu també Meier, Willi; Staffelbach, Othmar (1991). "Analysis of pseudo random sequences generated by cellular automata". Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91: 186, Lecture Notes in Computer Science 547, Springer-Verlag [Enllaç no actiu]
  4. Sipper, Moshe; Tomassini, Marco «Generating parallel random number generators by cellular programming». International Journal of Modern Physics C, vol. 7, 2, 1996, pàg. 181–190. DOI: 10.1142/S012918319600017X.