Ver el código de «Autómata celular de bloque»

[[Archivo:Margolus_block_neighborhood.svg|miniaturadeimagen|240x240px|La vecindad de Margolus  para un autómata celular de bloque bidimensional. La partición de las células se alternan entre el conjunto de  bloques 2 {{Math|2 &times; 2}} {{Math|2 &times; 2}} indicado por las líneas azules sólidas, y el conjunto de bloques indicado por líneas rojas discontinuas.]]
Un '''autómata celular de bloque''' o fraccionado es una  clase especial de [[autómata celular]] en qué la rejilla de células está dividida entre bloques que no se solapan (con particiones diferentes en pasos de tiempo diferente) y la regla de transición está aplicada a un bloque entero en lugar de a una célula sola. El autómata celular de bloque es útil para simulaciones de cantidades físicas, porque es sencillo elegir reglas de transición que obedezcan restricciones físicas como [[Autómata celular reversible|reversibilidad]] y [[leyes de conservación]].<ref name="schiff">{{Obra citada|título=Cellular Automata: A Discrete View of the World|apellidos=Schiff|nombre=Joel L.|editorial=Wiley|capítulo=4.2.1 Partitioning Cellular Automata|páginas=115–116|year=2008}}</ref>

== Definición ==
Un autómata celular de bloque consta de los componentes siguientes:<ref name="schiff">{{Obra citada|título=Cellular Automata: A Discrete View of the World|apellidos=Schiff|nombre=Joel L.|editorial=Wiley|capítulo=4.2.1 Partitioning Cellular Automata|páginas=115–116|year=2008}}</ref><ref name="tm">{{Obra citada|título=Cellular Automata Machines: A New Environment for Modeling|apellidos=Toffoli|nombre=Tommaso|enlaceautor=Tommaso Toffoli|editorial=MIT Press|capítulo=II.12 The Margolus neighborhood|páginas=119–138|apellidos2=Margolus|nombre2=Norman|enlaceautor2=Norman Margolus|year=1987}}</ref>

* Un [[Red (grupo)|enrejado]] regular de células
* Un [[conjunto finito]] de los estados que cada célula puede estar en
* Una partición de las celdas en un [[teselado]] uniforme en el que cada mosaico de la partición tiene el mismo tamaño y forma
* Una regla para cambiar la partición después de que cada vez paso
* Una regla de transición, una función que toma como entrada una asignación de estados para las celdas en un único mosaico y produce como salida otra asignación de estados para las mismas celdas.

En cada paso de tiempo, la regla de transición se aplica simultáneamente y sincrónicamente a todos los mosaicos en la partición. Luego, la partición se desplaza y la misma operación se repite en el siguiente paso de tiempo, y así sucesivamente. De esta manera, como con cualquier autómata celular, el patrón de estados celulares cambia con el tiempo para realizar algún cálculo o simulación no trivial.

== Vecindad ==
El esquema de partición más simple es probablemente la '''vecindad de Margolus''', nombrado después de que [[Norman Margolus]], quién fue el primero en estudiar autómata celular de bloque utilizando esta estructura de vecindad. En la vecindad de Margolus, el enrejado está dividido a bloques de 2 células (o {{Math|2 &times; 2 &times; 2}} × 2 cuadrada en dos dimensiones, o 2 {{Math|2 &times; 2 &times; 2}} 2 {{Math|2 &times; 2}} {{Math|2}} cubos en tres dimensiones, etc.) cuáles están cambiados por una célula (a lo largo de cada dimensión) encima alternar pasos de tiempo.<ref name="schiff">{{Obra citada|título=Cellular Automata: A Discrete View of the World|apellidos=Schiff|nombre=Joel L.|editorial=Wiley|capítulo=4.2.1 Partitioning Cellular Automata|páginas=115–116|year=2008}}</ref><ref name="tm">{{Obra citada|título=Cellular Automata Machines: A New Environment for Modeling|apellidos=Toffoli|nombre=Tommaso|enlaceautor=Tommaso Toffoli|editorial=MIT Press|capítulo=II.12 The Margolus neighborhood|páginas=119–138|apellidos2=Margolus|nombre2=Norman|enlaceautor2=Norman Margolus|year=1987}}</ref><ref name="m84">{{Obra citada|título=Physics-like models of computation|apellidos=Margolus|nombre=N.|enlaceautor=Norman Margolus|pub-periódica=Physica D|volumen=10|páginas=81–95|bibcode=1984PhyD...10...81M|DOI=10.1016/0167-2789(84)90252-5|year=1984}}. Reprinted in {{Obra citada|título=Theory and Applications of Cellular Automata|editorial=World Scientific|serie=Advanced series on complex systems|volumen=1|páginas=232–246|editor=Wolfram|nombre-editor=Stephen|enlace-editor=Stephen Wolfram|year=1986}}</ref>

Una técnica estrechamente relacionada debido a K. Morita y M. Harao consiste en particionar cada célula a un número finito de partes, cada parte que es dedicado a algún vecino.<ref>{{Obra citada|título=Computation universality of 1 dimensional reversible (injective) cellular automata|apellidos=Morita|nombre=K.|pub-periódica=Transactions Institute of Electronics, Information and Communication Engineers, E|volumen=72|páginas=758–762|apellidos2=Harao|nombre2=M.|year=1989}}</ref> La evolución procede por intercambiar las partes correspondientes entre vecinos y entonces  aplicando en cada célula una transformación puramente local <math>F</math> que  depende sólo en el estado de la célula (y no en los estados de sus vecinos). Con tal esquema de construcción, el autómata celular es garantizado para ser reversible si la transformación local <math>F</math> es una [[Función biyectiva|biyeción]]. Esta técnica puede ser vista como autómata celular de bloque en un enrejado más bien de células, formados por las partes de cada célula más grande; los bloques de este enrejado más bien se alternan entre los conjuntos de partes dentro de una célula grande sola y los conjuntos de partes en vecinos de células que partes de participación con cada otro.

== Véase también ==

* [[Secuencia de mondadientes]], un patrón fractal que puede ser emulado por autómata celular  con la vecindad de Margolus

== Referencias ==
{{Listaref|30em}}

== Enlaces externos ==

* [http://www.cise.ufl.edu/~skoehler/critters/index.html Critters Simulacro], Seth Koehler, Univ. de Florida
{{Control de autoridades}}
[[Categoría:Autómata celular]]
[[Categoría:Wikipedia:Páginas con traducciones sin revisar]]