Ver el código de «Regla 30»

{{otros usos|Regla del 30|para=la fórmula usada en incendios forestales|este=los autómatas celulares binarios unidimensionales|otro=}}
[[Archivo:Textile cone.JPG|thumb|Una concha de ''[[Conus textile]]'' similar en apariencia a la Regla 30.<ref>{{cita web|url=https://www.maths.nottingham.ac.uk/personal/sc/pdfs/Seashells09.pdf|título=The Geometry and Pigmentation of Seashells|autor=Stephen Coombes|fecha=Febrero de 2009|obra=www.maths.nottingham.ac.uk|editorial=[[University of Nottingham]]}}</ref>]]

La '''Regla 30''' es un [[autómata celular]] [[Sistema binario|binario]] unidimensional presentado por [[Stephen Wolfram]] en 1983.<ref>{{cite journal|author =  Wolfram, S.|title =  Statistical mechanics of cellular automata|journal =  Rev. Mod. Phys.|volume =  55|pages =  601–644|year =  1983|doi =  10.1103/RevModPhys.55.601}}</ref> Wolfram la describió como su "regla favorita de todos los tiempos"<ref>[https://web.archive.org/web/20070928111114/http://www.stephenwolfram.com/publications/talks/ycombinatorschool/ Donde Starting a Long-Term Company], S. Wolfram, 2005.</ref> y da detalles en su libro 'A New Kind of Science'. Según el esquema de clasificación de Wolfram, la regla 30 es una regla de Clase III, que muestra un comportamiento [[periodicidad|aperiódico]] y [[caos|caótico]].

Esta regla es de particular interés porque genera patrones [[Teoría de la complejidad computacional|complejos]] aparentemente [[aleatorio]]s a partir de reglas simples y bien definidas. Por este motivo, Wolfram creía que la Regla 30 y los autómatas celulares en general, son la clave por entender de que forma las reglas simples pueden generar estructuras y comportamientos complejos en la naturaleza. Por ejemplo, un patrón similar al generado por la Regla 30 aparece en la concha de los [[caracol marino|caracoles marinos]] de la especie [[Conus textile]]. La Regla 30 también se ha usado para generar nombres aleatorios en el programa [[Mathematica]] del propio Wolfram, y en [[criptografía]].<ref>{{cite conference|author = Wolfram, S.|title = Cryptography with cellular automata|date = 1985|booktitle = Proceedings of Advances in Cryptology - CRYPTO '85|pages = 429|publisher = Lecture Notes in Computer Science 218, Springer-Verlag|url = http://www.springerlink.com/content/6lc1m67ec2ek0nk3/}} Véase también {{cite conference|author = Meier, Willi; Staffelbach, Othmar|title = Analysis of pseudo random sequences generated by cellular automata|booktitle = Advances in Cryptology: Proc. Workshop donde the Theory and Application of Cryptographic Techniques, EUROCRYPT '91|date = 1991|pages = 186|publisher = Lecture Notes in Computer Science 547, Springer-Verlag|url = http://www.springerlink.com/content/8cwan65384nphd0u/}}</ref>

La Regla 30 se denomina así porque 30 es el [[código Wolfram]] más pequeño que describe su conjunto de reglas. La [[imagen especular]], el complemento y el complemento especular de la Regla 30 tienen códigos Wolfram 86, 135 y 149 respectivamente.
== Conjunto de reglas ==
En todos los autómatas celulares elementales de Wolfram, se considera una matriz unidimensional infinita de células autómatas celulares con sólo dos estados, con cada célula en algún estado inicial. A intervalos de tiempo discretos, cada celda cambia de estado espontáneamente en función de su estado actual y el estado de sus dos vecinas. Para la Regla 30, el conjunto de reglas que gobierna el siguiente estado del autómata es:

{| class="wikitable" align=center style="text-align:center"
|-
! Patrón actual !! 111 !! 110 !! 101 !! 100 !! 011 !! 010 !! 001 !! 000
|-
! Nuevo estado para celda central
| 0 || 0 || 0 || 1 || 1 || 1 || 1 || 0
|}

La fórmula correspondiente es [celda_izquierda XOR (celda_central O celda_derecha)]. Se llama Regla 30 porque en [[Sistema binario|binario]], ''00011110<sub>2</sub>'' = 30.

El siguiente diagrama muestra el patrón creado, con celdas coloreadas según el estado anterior de su vecindario. Los colores más oscuros representan "1" y los colores más claros representan "0". El tiempo aumenta por el eje vertical:

[[Archivo:Cellular Automata running Wolfram-rule-30.svg|526px|sinmarco|centro]]

== Estructura y propiedades ==
El siguiente patrón surge de un estado inicial en el que una sola celda con el estado 1 (que se muestra en negro) está rodeada por celdas con el estado 0 (blanco):

<center>
[[File:Rule30-256-rows.png|1022px|frameless]]<br />
'''Autómata celular regla 30'''
</center>

Aquí, el eje vertical representa el tiempo y cualquier sección transversal horizontal de la imagen representa el estado de todas las celdas de la matriz en un punto específico de la evolución del patrón. Varios motivos están presentes en esta estructura, como la frecuente aparición de triángulos blancos y un patrón de rayas bien definido en el lado izquierdo; sin embargo, la estructura en su conjunto no tiene un patrón discernible. El número de células negras en la generación <math>n</math> viene dada por la secuencia

:1, 3, 3, 6, 4, 9, 5, 12, 7, 12, 11, 14, 12, 19, 13, 22, 15, 19, ... {{OEIS|id=A070952}}

y es aproximadamente <math>n</math>.

== Caos ==
Wolfram basó su clasificación de la Regla 30 como caótica basándose principalmente en su apariencia visual,{{cita requerida}} y más tarde se demostró que cumplía con definiciones más rigurosas de caos propuestas por Robert L. Devaney y Knudson. En particular, de acuerdo con los criterios de Devaney, la Regla 30 muestra una [[Efecto mariposa|dependencia sensible de las condiciones iniciales]] (dos configuraciones iniciales que difieren solo en un pequeño número de celdas divergen rápidamente), sus configuraciones periódicas son densas en el espacio de todas las configuraciones, según la [[Espacio de Cantor|topología de Cantor]] en el espacio de configuraciones (hay una configuración periódica con cualquier patrón finito de células), y se mezcla (para dos patrones finitos de celdas cualesquiera, hay una configuración que contiene un patrón que eventualmente conduce a una configuración que contiene el otro patrón). Según los criterios de Knudson, muestra una dependencia sensible y hay una órbita densa (una configuración inicial que eventualmente muestra cualquier patrón finito de células). Ambas caracterizaciones del comportamiento caótico de la regla se derivan de una propiedad más simple y fácil de verificar de la Regla 30: se deja ''permutativa'', lo que significa que si dos configuraciones {{mvar|C}} y {{mvar|D}} difieren en el estado de una sola celda en la posición {{mvar|i}}, luego de un solo paso, las nuevas configuraciones diferirán en la celda {{math|''i'' + 1}}.<ref>{{Cite journal
 | last1 = Cattaneo | first1 = Gianpiero
 | last2 = Finelli | first2 = Michele
 | last3 = Margara | first3 = Luciano
 | doi = 10.1016/S0304-3975(98)00345-4
 | mr = 1774395
 | issue = 1–2
 | journal = Theoretical Computer Science
 | pages = 219–241
 | title = Investigating topological chaos by elementary cellular automata dynamics
 | volume = 244
 | year = 2000}}</ref>

== Aplicaciones ==
=== Generación de números aleatorios ===
Como se desprende de la imagen de arriba, la Regla 30 genera una aparente aleatoriedad a pesar de la falta de cualquier cosa que pueda considerarse razonablemente como entrada aleatoria. Stephen Wolfram propuso usar su columna central como un [[generador de números pseudoaleatorios]] (PRNG); pasa muchas pruebas estándar de aleatoriedad, y Wolfram usó previamente esta regla en el producto de Mathematica para crear números enteros aleatorios.<ref>{{Citation|last=Lex Fridman|title=MIT AGI: Computational Universe (Stephen Wolfram)|date=2018-03-02|url=https://www.youtube.com/watch?v=P7kX7BuHSFI&t=1860|accessdate=2018-03-07}}</ref>

Sipper y Tomassini han demostrado que, como [[generador de números aleatorios]], la Regla 30 presenta un comportamiento deficiente en una [[Prueba χ²|prueba de chi cuadrado]] cuando se aplica a todas las columnas de la regla en comparación con otros generadores celulares basados en autómatas.<ref>{{cite journal|author1=Sipper, Moshe |author2=Tomassini, Marco |title=Generating parallel random number generators by cellular programming|journal=International Journal of Modern Physics C|volume=7|issue=2|pages=181–190|year=1996|doi=10.1142/S012918319600017X|bibcode = 1996IJMPC...7..181S }}</ref> Los autores también expresaron su preocupación de que "los resultados relativamente bajos obtenidos por la regla 30 CA pueden deberse al hecho de que consideramos N secuencias aleatorias generadas en paralelo, en lugar de la única considerada por Wolfram".<ref>Page 6 of {{cite journal|author1=Sipper, Moshe |author2=Tomassini, Marco |title=Generating parallel random number generators by cellular programming|journal=International Journal of Modern Physics C|volume=7|issue=2|pages=181–190|year=1996|doi=10.1142/S012918319600017X|bibcode = 1996IJMPC...7..181S }}</ref>

=== Decoración ===
[[File:Cmglee_Cambridge_North_cladding_detail.jpg|thumb|250px|Detalle del revestimiento de la estación de tren de Cambridge North]]
La estación de tren de Cambridge North está decorada con paneles arquitectónicos que muestran la evolución de la Regla 30 (o, de manera equivalente, bajo la inversión de blanco y negro, Regla 135).<ref>{{citation|url=http://blog.stephenwolfram.com/2017/06/oh-my-gosh-its-covered-in-rule-30s/|title=Oh My Gosh, It's Covered in Rule 30s!|last=Wolfram|first=Stephen|date=2017-06-01|work=Stephen Wolfram's blog}}</ref> El arquitecto describió el diseño como inspirado en el [[Juego de la vida]] de Conway, un autómata celular diferente estudiado por el matemático de Cambridge [[John Horton Conway]], pero en realidad no se basa en éste.<ref>{{citation|url=http://aperiodical.com/2017/05/right-answer-for-the-wrong-reason-cellular-automaton-on-the-new-cambridge-north-station/|title=Right answer for the wrong reason: cellular automaton on the new Cambridge North station|first=Christian|last=Lawson-Perfect|date=2017-05-23|work=The Aperiodical}}</ref><ref>{{Cite news|url=https://qz.com/1001946/a-uk-train-stations-tribute-to-a-famous-mathematician-got-everything-right-except-his-math/|title=A UK train station's tribute to a famous mathematician got everything right except his math|last=Purtill|first=Corinne|work=Quartz|access-date=2017-06-12|language=en-US}}</ref>

== Véase también ==
* [[Autómata celular]]
* [[Juego de la vida]]
* [[Regla 184]]
* [[Regla 90]]

== Referencias ==
{{listaref}}
* Wolfram, Stephen, 1985, ''[http://www.stephenwolfram.com/publications/articles/ca/85-cryptography/1/text.html Cryptography with Cellular Automata] {{Wayback|url=http://www.stephenwolfram.com/publications/articles/ca/85-cryptography/1/text.html |date=20130101073609 }}'', CRYPTO'85.

== Enlaces externos ==
En inglés:
{{Commons category}}
*{{MathWorld | title = Rule 30 | urlname = Rule30}}
*{{cite web|title=Announcing the Rule 30 Prizes|date=2019-10-01|website=Stephen Wolfram Writings|url=https://writings.stephenwolfram.com/2019/10/announcing-the-rule-30-prizes/}}
*[http://atlas.wolfram.com/01/01/30/ Rule 30 in Wolfram's atlas of cellular automata]
*[http://psoup.math.wisc.edu/archive/recipe32.html Rule 30: Wolfram's Pseudo-random Bit Generator] {{Wayback|url=http://psoup.math.wisc.edu/archive/recipe32.html |date=20190911113353 }}. Recipe 32 at [[David Griffeath]]'s Primordial Soup Kitchen.
*[https://web.archive.org/web/20130808012847/http://www.iwriteiam.nl/Rule30.html Repeating Rule 30 patterns]. A list of patterns that, when repeated to fill the cells of a Rule 30 automaton, repeat themselves after finitely many time steps. Frans Faase, 2003. Archived from the [http://www.iwriteiam.nl/Rule30.html Original] on 2013-08-08
*[http://olivier.sc.free.fr/logosc/cubisme/pavages.html Paving Mosaic Fractal]. Basic introduction to the pattern of Rule 30 from the perspective of a LOGO software expert Olivier Schmidt-Chevalier.
*[http://www.ted.com/talks/stephen_wolfram_computing_a_theory_of_everything.html TED Talk from February 2010] {{Wayback|url=http://www.ted.com/talks/stephen_wolfram_computing_a_theory_of_everything.html |date=20120516145452 }}. Stephen Wolfram speaks about computing a theory of everything where he talks about rule 30 among other things.

{{Control de autoridades}}
[[Categoría:Matemática recreativa]]
[[Categoría:Introducciones de 1983]]
[[Categoría:Autómata celular]]