Content deleted Content added
Spectrogram (talk | contribs) vandalism, revert |
m Reverted edit by 2001:8F8:1E6F:132B:54A4:D49B:FBE1:8816 (talk) to last version by Bender the Bot |
||
Line 1:
{{short description|Discrete model studied in computer science}}
{{Use dmy dates|date=July 2020}}
[[File:Gospers glider gun.gif|class=skin-invert-image|frame|right|[[Bill Gosper|Gosper's]] [[Gun (cellular automaton)|Glider Gun]] creating "[[Glider (Conway's Life)|gliders]]" in the cellular automaton [[Conway's Game of Life]]<ref>[[Daniel Dennett]] (1995), ''[[Darwin's Dangerous Idea]]'', Penguin Books, London, {{ISBN|978-0-14-016734-4}}, {{ISBN|0-14-016734-X}}</ref>]]
A '''cellular automaton''' (pl. '''cellular automata''', abbrev. '''CA''') is a discrete [[model of computation]] studied in [[automata theory]]. Cellular automata are also called '''cellular spaces''', '''tessellation automata''', '''homogeneous structures''', '''cellular structures''', '''tessellation structures''', and '''iterative arrays'''.<ref name=reviews>{{Cite journal | url=http://www.stephenwolfram.com/publications/articles/ca/83-statistical/ | author=Wolfram, Stephen | author-link=Stephen Wolfram | title=Statistical Mechanics of Cellular Automata | journal=Reviews of Modern Physics | issue=3 | volume=55 | pages=601–644 | year=1983 | doi=10.1103/RevModPhys.55.601 | bibcode=1983RvMP...55..601W | access-date=28 February 2011 | archive-date=21 September 2013 | archive-url=https://web.archive.org/web/20130921060232/http://www.stephenwolfram.com/publications/articles/ca/83-statistical/ | url-status=dead }}</ref> Cellular automata have found application in various areas, including [[physics]], [[theoretical biology]] and [[microstructure]] modeling.
A cellular automaton consists of a regular grid of ''cells'', each in one of a finite number of ''[[State (computer science)|states]]'', such as ''on'' and ''off'' (in contrast to a [[coupled map lattice]]). The grid can be in any finite number of dimensions. For each cell, a set of cells called its ''neighborhood'' is defined relative to the specified cell. An initial state (time ''t'' = 0) is selected by assigning a state for each cell. A new ''generation'' is created (advancing ''t'' by 1), according to some fixed ''rule'' (generally, a mathematical function)<ref>{{cite book|title=Cellular Automata Machines: A New Environment for Modeling|first1=Tommaso|last1=Toffoli|first2=Norman|last2=Margolus|publisher=MIT Press|year=1987|isbn=9780262200608|page=27|url=https://books.google.com/books?id=HBlJzrBKUTEC&pg=PA27}}</ref> that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood. Typically, the rule for updating the state of cells is the same for each cell and does not change over time, and is applied to the whole grid simultaneously,<ref>{{cite book | author=Schiff, Joel L. | title=Cellular Automata: A Discrete View of the World | year=2011 | publisher=Wiley & Sons, Inc | isbn=9781118030639 | ref=schiff|page=40|url=https://books.google.com/books?id=uXJC2C2sRbIC&pg=PA40}}</ref> though exceptions are known, such as the [[stochastic cellular automaton]] and [[asynchronous cellular automaton]].
The concept was originally discovered in the 1940s by [[Stanislaw Ulam]] and [[John von Neumann]] while they were contemporaries at [[Los Alamos National Laboratory]]. While studied by some throughout the 1950s and 1960s, it was not until the 1970s and [[Conway's Game of Life]], a two-dimensional cellular automaton, that interest in the subject expanded beyond academia. In the 1980s, [[Stephen Wolfram]] engaged in a systematic study of one-dimensional cellular automata, or what he calls [[elementary cellular automaton|elementary cellular automata]]; his research assistant [[Matthew Cook]] showed that [[Rule 110|one of these rules]] is [[Turing-complete]].
The primary classifications of cellular automata, as outlined by Wolfram, are numbered one to four. They are, in order, automata in which patterns generally stabilize into [[homogeneity]], automata in which patterns evolve into mostly stable or oscillating structures, automata in which patterns evolve in a seemingly chaotic fashion, and automata in which patterns become extremely complex and may last for a long time, with stable local structures. This last class is thought to be [[computationally universal]], or capable of simulating a [[Turing machine]]. Special types of cellular automata are ''[[Reversible cellular automaton|reversible]]'', where only a single configuration leads directly to a subsequent one, and ''totalistic'', in which the future value of individual cells only depends on the total value of a group of neighboring cells. Cellular automata can simulate a variety of real-world systems, including biological and chemical ones.
==Overview==
{{multiple image|align=right
|image1=CA-Moore.svg|caption1=The red cells are the [[Moore neighborhood]] for the blue cell.
|image2=CA-von-Neumann.svg|caption2=The red cells are the [[von Neumann neighborhood]] for the blue cell. The range-2 "cross neighborhood" includes the pink cells as well.
}}
One way to simulate a two-dimensional cellular automaton is with an infinite sheet of [[graph paper]] along with a set of rules for the cells to follow. Each square is called a "cell" and each cell has two possible states, black or white. The ''neighborhood'' of a cell is the nearby, usually adjacent, cells. The two most common types of neighborhoods are the ''[[von Neumann neighborhood]]'' and the ''[[Moore neighborhood]]''.<ref name=kier-seybold-cheng-15>{{Harvnb|Kier, Seybold, Cheng|2005|p=15|ref=kier-seybold-cheng}}</ref> The former, named after the founding cellular automaton theorist, consists of the four [[orthogonal]]ly adjacent cells.<ref name=kier-seybold-cheng-15/> The latter includes the von Neumann neighborhood as well as the four diagonally adjacent cells.<ref name=kier-seybold-cheng-15/> For such a cell and its Moore neighborhood, there are 512 (= 2<sup>9</sup>) possible patterns. For each of the 512 possible patterns, the rule table would state whether the center cell will be black or white on the next time interval. [[Conway's Game of Life]] is a popular version of this model. Another common neighborhood type is the ''extended von Neumann neighborhood'', which includes the two closest cells in each orthogonal direction, for a total of eight.<ref name=kier-seybold-cheng-15/> The general equation for the total number of automata possible is ''k''<sup>''k''<sup>''s''</sup></sup>, where ''k'' is the number of possible states for a cell, and ''s'' is the number of neighboring cells (including the cell to be calculated itself) used to determine the cell's next state.<ref name=bialynick-9>{{Harvnb|Bialynicki-Birula, Bialynicka-Birula|2004|p=9|ref=bialynick}}</ref> Thus, in the two-dimensional system with a Moore neighborhood, the total number of automata possible would be 2<sup>2<sup>9</sup></sup>, or {{val|1.34|e=154}}.
It is usually assumed that every cell in the universe starts in the same state, except for a finite number of cells in other states
[[
Cellular automata are often simulated on a finite grid rather than an infinite one.
==History==
[[Stanislaw Ulam]], while working at the [[Los Alamos National Laboratory]] in the 1940s, studied the growth of crystals, using a simple [[Lattice model (physics)|lattice network]] as his model.<ref name=pickover>{{cite book | author=Pickover, Clifford A. | title=The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics | url=https://archive.org/details/mathbookfrompyth00pick | url-access=limited | page=[https://archive.org/details/mathbookfrompyth00pick/page/n410 406] | year=2009| publisher=Sterling Publishing Company, Inc | isbn=978-1402757969}}</ref> At the same time, [[John von Neumann]], Ulam's colleague at Los Alamos, was working on the problem of [[self-replicating system]]s.<ref name=schiff-1>{{Harvnb|Schiff|2011|p=1|ref=schiff}}</ref> Von Neumann's initial design was founded upon the notion of one robot building another robot. This design is known as the kinematic model.<ref>John von Neumann, "The general and logical theory of automata," in [[Lloyd A. Jeffress|L.A. Jeffress]], ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951, pp. 1–31.</ref><ref>{{cite journal | last1 = Kemeny | first1 = John G. | year = 1955 | title = Man viewed as a machine | journal = Sci. Am. | volume = 192 | issue = 4| pages = 58–67 | doi=10.1038/scientificamerican0455-58| bibcode = 1955SciAm.192d..58K}}; ''Sci. Am.'' 1955; 192:6 (errata).</ref> As he developed this design, von Neumann came to realize the great difficulty of building a self-replicating robot, and of the great cost in providing the robot with a "sea of parts" from which to build its replicant. Neumann wrote a paper entitled "The general and logical theory of automata" for the [[Lloyd A. Jeffress#The Hixon Symposium|Hixon Symposium]] in 1948.<ref name=schiff-1/> Ulam was the one who suggested using a ''discrete'' system for creating a reductionist model of self-replication.<ref name=schiff-3>{{Harvnb|Schiff|2011|p=3|ref=schiff}}</ref><ref name=ilachinski-xxix>{{Harvnb|Ilachinski|2001|p=xxix|ref=ilachinski}}</ref> [[Nils Aall Barricelli]] performed many of the earliest explorations of these models of [[artificial life]].
[[File:Vonneumann-john r.jpg|thumb|[[John von Neumann]], [[Los Alamos National Laboratory|Los Alamos]] ID badge]]
Ulam and von Neumann created a method for calculating liquid motion in the late 1950s. The driving concept of the method was to consider a liquid as a group of discrete units and calculate the motion of each based on its neighbors' behaviors.<ref name=bialynick-8>{{Harvnb|Bialynicki-Birula, Bialynicka-Birula|2004|p=8|ref=bialynick}}</ref> Thus was born the first system of cellular automata. Like Ulam's lattice network, [[Von Neumann cellular automata|von Neumann's cellular automata]] are two-dimensional, with his self-replicator implemented algorithmically. The result was a [[Von Neumann universal constructor|universal copier and constructor]] working within a cellular automaton with a small neighborhood (only those cells that touch are neighbors; for von Neumann's cellular automata, only [[orthogonal]] cells), and with 29 states per cell.<ref name=wolfram-876>{{Harvnb|Wolfram|2002|p=876|ref=wolfram}}</ref> Von Neumann gave an [[constructive proof|existence proof]] that a particular pattern would make endless copies of itself within the given cellular universe by designing a 200,000 cell configuration that could do so.<ref name=wolfram-876/> This design is known as the [[tessellation]] model, and is called a [[von Neumann universal constructor]].<ref name=TSRA>{{harvnb|von Neumann|1966}}</ref>
Also in the 1940s, [[Norbert Wiener]] and [[Arturo Rosenblueth]] developed a model of excitable media with some of the characteristics of a cellular automaton.<ref name="Wiener-Rosenblueth">{{cite journal | last1 = Wiener | first1 = N. | last2 = Rosenblueth | first2 = A. | year = 1946 | title = The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle | journal = Arch. Inst. Cardiol. México | volume = 16 | issue = 3| pages = 205–65 | pmid = 20245817 }}</ref> Their specific motivation was the mathematical description of impulse conduction in cardiac systems. However their model is not a cellular automaton because the medium in which signals propagate is continuous, and wave fronts are curves.<ref name="Wiener-Rosenblueth"/><ref name="reshodko">{{Cite journal|last1=Letichevskii|first1=A. A. |last2= Reshodko|first2=L. V.|title=N. Wiener's theory of the activity of excitable media |journal=Cybernetics|volume=8|issue=5 |year=1974|pages=856–864|doi=10.1007/bf01068458|s2cid=121306408 }}</ref> A true cellular automaton model of excitable media was developed and studied by J. M. Greenberg and S. P. Hastings in 1978; see [[Greenberg-Hastings cellular automaton]]. The original work of Wiener and Rosenblueth contains many insights and continues to be cited in modern research publications on [[cardiac arrhythmia]] and excitable systems.<ref>{{cite journal | doi = 10.1038/355349a0 | last1 = Davidenko | first1 = J. M. | last2 = Pertsov | first2 = A. V. | last3 = Salomonsz | first3 = R. | last4 = Baxter | first4 = W. | last5 = Jalife | first5 = J. | year = 1992 | title = Stationary and drifting spiral waves of excitation in isolated cardiac muscle | journal = Nature | volume = 355 | issue = 6358| pages = 349–351 | pmid = 1731248 |bibcode = 1992Natur.355..349D | s2cid = 4348759 }}</ref>
In the 1960s, cellular automata were studied as a particular type of [[dynamical system]] and the connection with the mathematical field of [[symbolic dynamics]] was established for the first time. In 1969, [[Gustav A. Hedlund]] compiled many results following this point of view<ref>{{cite journal | doi = 10.1007/BF01691062 | last1 = Hedlund | first1 = G. A. | author-link = Gustav A. Hedlund | year = 1969 | title = Endomorphisms and automorphisms of the shift dynamical system | journal = Math. Systems Theory | volume = 3 | issue = 4| pages = 320–3751 | s2cid = 21803927 }}</ref> in what is still considered as a seminal paper for the mathematical study of cellular automata. The most fundamental result is the characterization in the [[Curtis–Hedlund–Lyndon theorem]] of the set of global rules of cellular automata as the set of [[continuous function|continuous]] [[endomorphisms]] of [[shift space]]s.
In 1969, German computer pioneer [[Konrad Zuse]] published his book ''[[Calculating Space]]'', proposing that the physical laws of the universe are discrete by nature, and that the entire universe is the output of a deterministic computation on a single cellular automaton; "Zuse's Theory" became the foundation of the field of study called ''[[digital physics]]''.<ref name=schiff-182>{{Harvnb|Schiff|2011|p=182|ref=schiff}}</ref>
Also in 1969 computer scientist [[Alvy Ray Smith]] completed a Stanford PhD dissertation on Cellular Automata Theory, the first mathematical treatment of CA as a general class of computers. Many papers came from this dissertation: He showed the equivalence of neighborhoods of various shapes, how to reduce a Moore to a von Neumann neighborhood or how to reduce any neighborhood to a von Neumann neighborhood.<ref>{{cite web|last=Smith|first=Alvy Ray|title=Cellular Automata Complexity Trade-Offs|url=http://alvyray.com/Papers/CA/TradeOff.pdf}}</ref> He [[mathematical proof|proved]] that two-dimensional CA are computation universal, introduced 1-dimensional CA, and showed that they too are computation universal, even with simple neighborhoods.<ref>{{cite web|last=Smith|first=Alvy Ray|title=Simple Computation-Universal Cellular Spaces|url=http://alvyray.com/Papers/CA/UniversalCA_1D.pdf}}</ref> He showed how to subsume the complex von Neumann proof of construction universality (and hence self-reproducing machines) into a consequence of computation universality in a 1-dimensional CA.<ref>{{cite web|last=Smith|first=Alvy Ray|title=Simple Nontrivial Self-Reproducing Machines|url=http://alvyray.com/Papers/CA/alife2_optimized.pdf}}</ref> Intended as the introduction to the German edition of von Neumann's book on CA, he wrote a survey of the field with dozens of references to papers, by many authors in many countries over a decade or so of work, often overlooked by modern CA researchers.<ref>{{cite web|last=Smith|first=Alvy Ray|title=Introduction to and Survey of Cellular Automata or Polyautomata Theory|url=http://alvyray.com/Papers/CA/PolyCA76.pdf}}</ref>
In the 1970s a two-state, two-dimensional cellular automaton named [[Conway's Game of Life|Game of Life]] became widely known, particularly among the early computing community. Invented by [[John Horton Conway|John Conway]] and popularized by [[Martin Gardner]] in a ''[[Scientific American]]'' article,<ref>{{cite journal | last1 = Gardner | first1 =Martin | year = 1970 | title = Mathematical Games: The fantastic combinations of John Conway's new solitaire game "life" | url = http://www.ibiblio.org/lifepatterns/october1970.html | journal = Scientific American | volume =223 | issue = 4 | pages = 120–123 | doi =10.1038/scientificamerican1070-120 }}</ref> its rules are as follows:
# Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
# Any live cell with two or three live neighbours lives on to the next generation.
# Any live cell with more than three live neighbours dies, as if by overpopulation.
# Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
Despite its simplicity, the system achieves an impressive diversity of behavior, fluctuating between apparent [[randomness]] and order. One of the most apparent features of the Game of Life is the frequent occurrence of ''gliders'', arrangements of cells that essentially move themselves across the grid. It is possible to arrange the automaton so that the gliders interact to perform computations, and after much effort it has been shown that the Game of Life can emulate a [[universal Turing machine]].<ref>Paul Chapman. Life universal computer. http://www.igblan.free-online.co.uk/igblan/ca/ {{Webarchive|url=https://web.archive.org/web/20090906014935/http://www.igblan.free-online.co.uk/igblan/ca/ |date=6 September 2009 }} November 2002</ref> It was viewed as a largely recreational topic, and little follow-up work was done outside of investigating the particularities of the Game of Life and a few related rules in the early 1970s.<ref name=Wainwright-16>{{Harvnb|Wainwright|2010|p=16}}</ref>
[[Stephen Wolfram]] independently began working on cellular automata in mid-1981 after considering how complex patterns seemed formed in nature in violation of the [[second law of thermodynamics]].<ref name=wolfram-880/> His investigations were initially spurred by a desire to model systems such as the [[neural network (biology)|neural networks]] found in brains.<ref name=wolfram-880/> He published his first paper in ''[[Reviews of Modern Physics]]'' investigating ''[[elementary cellular automaton|elementary cellular automata]]'' ([[Rule 30]] in particular) in June 1983.<ref name=reviews/><ref name=wolfram-880>{{Harvnb|Wolfram|2002|p=880|ref=wolfram}}</ref> The unexpected complexity of the behavior of these simple rules led Wolfram to suspect that complexity in nature may be due to similar mechanisms.<ref name=wolfram-880/> His investigations, however, led him to realize that cellular automata were poor at modelling neural networks.<ref name=wolfram-880/> Additionally, during this period Wolfram formulated the concepts of intrinsic [[randomness]] and [[computational irreducibility]],<ref name=wolfram-881>{{Harvnb|Wolfram|2002|p=881|ref=wolfram}}</ref> and suggested that [[rule 110]] may be [[Turing-complete|universal]]—a fact proved later by Wolfram's research assistant [[Matthew Cook]] in the 1990s.<ref>{{cite journal | author=Mitchell, Melanie | author-link=Melanie Mitchell | title=Is the Universe a Universal Computer? | journal=[[Science (magazine)|Science]] | date=4 October 2002 | volume=298 | issue=5591 | pages=65–68 | doi=10.1126/science.1075073| s2cid=122484855 }}</ref>
==Classification==
Wolfram, in ''[[A New Kind of Science]]'' and several papers dating from the mid-1980s, defined four classes into which cellular automata and several other simple computational models can be divided depending on their behavior. While earlier studies in cellular automata tended to try to identify types of patterns for specific rules, Wolfram's classification was the first attempt to classify the rules themselves. In order of complexity the classes are:
*Class 1: Nearly all initial patterns evolve quickly into a stable, homogeneous state. Any randomness in the initial pattern disappears.<ref name=ilachinski-12>{{Harvnb|Ilachinsky|2001|p=12|ref=ilachinski}}</ref>
*Class 2: Nearly all initial patterns evolve quickly into stable or oscillating structures. Some of the randomness in the initial pattern may filter out, but some remains. Local changes to the initial pattern tend to remain local.<ref name=ilachinski-12/>
*Class 3: Nearly all initial patterns evolve in a pseudo-random or chaotic manner. Any stable structures that appear are quickly destroyed by the surrounding noise. Local changes to the initial pattern tend to spread indefinitely.<ref name=ilachinski-12/>
*Class 4: Nearly all initial patterns evolve into structures that interact in complex and interesting ways, with the formation of local structures that are able to survive for long periods of time.<ref name=ilachinski-13>{{Harvnb|Ilachinsky|2001|p=13|ref=ilachinski}}</ref> Class 2 type stable or oscillating structures may be the eventual outcome, but the number of steps required to reach this state may be very large, even when the initial pattern is relatively simple. Local changes to the initial pattern may spread indefinitely. Wolfram has [[conjecture]]d that many class 4 cellular automata, if not all, are capable of [[Turing completeness|universal computation]]. This has been proven for Rule 110 and Conway's Game of Life.
These definitions are qualitative in nature and there is some room for interpretation. According to Wolfram, "...with almost any general classification scheme there are inevitably cases which get assigned to one class by one definition and another class by another definition. And so it is with cellular automata: there are occasionally rules...that show some features of one class and some of another."<ref name=wolfram-231>{{Harvnb|Wolfram|2002|p=231|ref=wolfram}}</ref> Wolfram's classification has been empirically matched to a clustering of the compressed lengths of the outputs of cellular automata.<ref>{{cite journal|last=Zenil|first=Hector|title=Compression-based investigation of the dynamical properties of cellular automata and other systems|journal=Complex Systems|year=2010|volume=19|issue=1|pages=1–28|url=http://www.complex-systems.com/pdf/19-1-1.pdf|doi=10.25088/ComplexSystems.19.1.1|arxiv=0910.4042 |s2cid=15364755}}</ref>
There have been several attempts to classify cellular automata in formally rigorous classes, inspired by Wolfram's classification. For instance, Culik and Yu proposed three well-defined classes (and a fourth one for the automata not matching any of these), which are sometimes called Culik–Yu classes; membership in these proved [[Undecidable problem|undecidable]].<ref name="DelormeMazoyer1998">{{cite book|editor1=M. Delorme |editor2=J. Mazoyer |title=Cellular automata: a parallel model|chapter-url=https://books.google.com/books?id=dGs87s5Pft0C&pg=PA239|year=1998|publisher=Springer|isbn=978-0-7923-5493-2|page=239|chapter=Topological chaos and CA|author1=G. Cattaneo |author2=E. Formenti |author3=L. Margara }}</ref><ref name="Voorhees1996">{{cite book|author=Burton H. Voorhees|title=Computational analysis of one-dimensional cellular automata|url=https://books.google.com/books?id=WcZTQHPrG68C&pg=PA8|year=1996|publisher=World Scientific|isbn=978-981-02-2221-5|page=8}}</ref><ref name="Garzon1995">{{cite book|author=Max Garzon|title=Models of massive parallelism: analysis of cellular automata and neural networks |url=https://archive.org/details/modelsmassivepar00garz|url-access=limited| year=1995 | publisher=Springer | isbn=978-3-540-56149-1 | page=[https://archive.org/details/modelsmassivepar00garz/page/n159 149]}}</ref>
Wolfram's class 2 can be partitioned into two subgroups of stable (fixed-point) and oscillating (periodic) rules.<ref name=li-packard>{{cite journal | url=http://www.complex-systems.com/pdf/04-3-3.pdf | author1=Li, Wentian | author-link1=Wentian Li | author2=Packard, Norman | title=The structure of the elementary cellular automata rule space | journal=Complex Systems | pages=281–297 | volume=4 | year=1990 | access-date=25 January 2013}}</ref>
The idea that there are 4 classes of dynamical system came originally from Nobel-prize winning chemist [[Ilya Prigogine]] who identified these 4 classes of thermodynamical systems: (1) systems in thermodynamic equilibrium, (2) spatially/temporally uniform systems, (3) chaotic systems, and (4) complex far-from-equilibrium systems with dissipative structures (see figure 1 in the 1974 paper of Nicolis, Prigogine's student).<ref name=nicolis>{{cite journal | url=http://www.complex-systems.com/pdf/04-3-3.pdf | author1=Nicolis | title=Dissipative Structures, Catastrophes, and Pattern Formation: A Bifurcation Analysis | journal=PNAS | pages=2748–2751 | volume=71 | number=7 | year=1974 | access-date=25 March 2017 | doi = 10.1073/pnas.71.7.2748| pmid=16592170 | pmc=388547 | bibcode=1974PNAS...71.2748N | doi-access=free }}</ref>
===Reversible===
{{main|Reversible cellular automaton}}
A cellular automaton is ''reversible'' if, for every current configuration of the cellular automaton, there is exactly one past configuration ([[preimage]]).<ref name=kari-379>{{Harvnb|Kari, Jarrko|1991|p=379|ref=gutowitz}}</ref> If one thinks of a cellular automaton as a function mapping configurations to configurations, reversibility implies that this function is [[bijective]].<ref name=kari-379/> If a cellular automaton is reversible, its time-reversed behavior can also be described as a cellular automaton; this fact is a consequence of the [[Curtis–Hedlund–Lyndon theorem]], a topological characterization of cellular automata.<ref>{{Cite journal|first=D.|last=Richardson|title=Tessellations with local transformations|journal=J. Comput. Syst. Sci.|volume=6|year=1972|pages=373–388|issue=5|doi=10.1016/S0022-0000(72)80009-6|doi-access=free}}</ref><ref>{{Cite book|title=Cellular Automata in Hyperbolic Spaces – Tome I, Volume 1|first=Maurice|last=Margenstern|publisher=Archives contemporaines|year=2007|isbn=978-2-84703-033-4|page=134|url=https://books.google.com/books?id=wGjX1PpFqjAC&pg=PA134}}</ref> For cellular automata in which not every configuration has a preimage, the configurations without preimages are called ''[[Garden of Eden (cellular automaton)|Garden of Eden]]'' patterns.<ref name=schiff-103>{{Harvnb|Schiff|2011|p=103|ref=schiff}}</ref>
For one-dimensional cellular automata there are known algorithms for deciding whether a rule is reversible or irreversible.<ref>{{cite journal | last1 = Amoroso | first1 = Serafino | last2 = Patt | first2 = Yale N. | year = 1972 | title = Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures | journal = J. Comput. Syst. Sci. | volume = 6 | issue = 5| pages = 448–464 | doi=10.1016/s0022-0000(72)80013-8| doi-access = free }}</ref><ref>{{Cite journal|journal=Complex Systems|volume=5|year=1991|pages=19–30|title=De Bruijn Graphs and Linear Cellular Automata|first=Klaus|last=Sutner|url=http://www.complex-systems.com/pdf/05-1-3.pdf}}</ref> However, for cellular automata of two or more dimensions reversibility is [[undecidable problem|undecidable]]; that is, there is no algorithm that takes as input an automaton rule and is guaranteed to determine correctly whether the automaton is reversible. The proof by [[Jarkko Kari]] is related to the tiling problem by [[Wang tile]]s.<ref>{{Cite journal|first=Jarkko|last=Kari|author-link=Jarkko Kari|title=Reversibility of 2D cellular automata is undecidable|journal=Physica D|volume=45|issue=1–3|year=1990|pages=379–385|doi=10.1016/0167-2789(90)90195-U|bibcode = 1990PhyD...45..379K}}</ref>
Reversible cellular automata are often used to simulate such physical phenomena as gas and fluid dynamics, since they obey the laws of [[thermodynamics]]. Such cellular automata have rules specially constructed to be reversible. Such systems have been studied by [[Tommaso Toffoli]], [[Norman Margolus]] and others. Several techniques can be used to explicitly construct reversible
===Totalistic===
A special class of
===Related automata===
There are many possible generalizations of the cellular automaton concept.
[[File:Oscillator.gif|class=skin-invert-image|right|frame|A cellular automaton based on hexagonal cells instead of squares (rule 34/2)]]
One way is by using something other than a rectangular (cubic, ''etc.'') grid. For example, if a plane is [[hexagonal tiling|tiled with regular hexagons]], those hexagons could be used as cells. In many cases the resulting cellular automata are equivalent to those with rectangular grids with specially designed neighborhoods and rules. Another variation would be to make the grid itself irregular, such as with [[Penrose tiles]].<ref>{{cite web|url=https://www.newscientist.com/article/dn22134-first-gliders-navigate-everchanging-penrose-universe.html|title=First gliders navigate ever-changing Penrose universe|author=Jacob Aron|work=New Scientist}}</ref>
Also, rules can be probabilistic rather than deterministic. Such cellular automata are called [[probabilistic cellular automata]]. A probabilistic rule gives, for each pattern at time ''t'', the probabilities that the central cell will transition to each possible state at time ''t'' + 1. Sometimes a simpler rule is used; for example: "The rule is the Game of Life, but on each time step there is a 0.001% probability that each cell will transition to the opposite color."
The neighborhood or rules could change over time or space. For example, initially the new state of a cell could be determined by the horizontally adjacent cells, but for the next generation the vertical cells would be used.
In cellular automata, the new state of a cell is not affected by the new state of other cells. This could be changed so that, for instance, a 2 by 2 block of cells can be determined by itself and the cells adjacent to itself.
There are ''[[continuous automaton|continuous automata]]''. These are like totalistic cellular automata, but instead of the rule and states being discrete (''e.g.'' a table, using states {0,1,2}), continuous functions are used, and the states become continuous (usually values in [[unit interval|[0,1]]]). The state of a ___location is a finite number of real numbers. Certain cellular automata can yield diffusion in liquid patterns in this way.
[[Continuous spatial automata]] have a continuum of locations. The state of a ___location is a finite number of real numbers. Time is also continuous, and the state evolves according to differential equations. One important example is [[reaction–diffusion]] textures, differential equations proposed by [[Alan Turing]] to explain how chemical reactions could create the stripes on [[zebra]]s and spots on leopards.<ref>{{cite book |last1=Murray |first1=J. D. |title=Mathematical biology |date=2003 |publisher=Springer |___location=New York |isbn=0-387-95228-4 |edition=3rd}}</ref> When these are approximated by cellular automata, they often yield similar patterns. MacLennan [http://www.cs.utk.edu/~mclennan/contin-comp.html] considers continuous spatial automata as a model of computation.
There are known examples of continuous spatial automata, which exhibit propagating phenomena analogous to gliders in the Game of Life.<ref>Pivato, M: "RealLife: The continuum limit of Larger than Life cellular automata", ''Theoretical Computer Science'', 372 (1), March 2007, pp. 46–68</ref>
''Graph rewriting automata'' are extensions of cellular automata based on [[graph rewriting system]]s.<ref>{{Cite book |doi = 10.1007/978-3-642-01284-6_14|isbn = 978-3-642-01283-9|chapter = Graph-Rewriting Automata as a Natural Extension of Cellular Automata|title = Adaptive Networks|series = Understanding Complex Systems|year = 2009|last1 = Tomita|first1 = Kohji|last2 = Kurokawa|first2 = Haruhisa|last3 = Murata|first3 = Satoshi|pages = 291–309}}</ref>
==Elementary cellular automata==
{{Main|Elementary cellular automaton}}
The simplest nontrivial cellular automaton would be one-dimensional, with two possible states per cell, and a cell's neighbors defined as the adjacent cells on either side of it. A cell and its two neighbors form a neighborhood of 3 cells, so there are 2<sup>3</sup> = 8 possible patterns for a neighborhood. A rule consists of deciding, for each pattern, whether the cell will be a 1 or a 0 in the next generation. There are then 2<sup>8</sup> = 256 possible rules.<ref name=bialynick-9/>
[[File:One-d-cellular-automate-rule-30.gif|thumb|An animation of the way the rules of a 1D cellular automaton determine the next generation]]
These 256 cellular automata are generally referred to by their [[Wolfram code]], a standard naming convention invented by Wolfram that gives each rule a number from 0 to 255. A number of papers have analyzed and compared the distinct cases among the 256 cellular automata (many are trivially isomorphic). The [[rule 30]], [[rule 90]], [[rule 110]], and [[rule 184]] cellular automata are particularly interesting. The images below show the history of rules 30 and 110 when the starting configuration consists of a 1 (at the top of each image) surrounded by 0s. Each row of pixels represents a generation in the history of the automaton, with ''t''=0 being the top row. Each pixel is colored white for 0 and black for 1.
[[File:CA rule30s.png|class=skin-invert-image|thumb|Rule 30]]
{| class="wikitable" style="text-align: center"
|+ [[Rule 30]] cellular automaton<br>(binary 00011110 = decimal 30)
|-
! current pattern
| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000
|-
! new state for center cell
| 0 || 0 || 0 || 1 || 1 || 1 || 1 || 0
|}
Rule 30 exhibits ''class 3'' behavior, meaning even simple input patterns such as that shown lead to chaotic, seemingly random histories.
[[File:Sample run of Rule 110 elementary cellular automaton, starting from single cell.png|class=skin-invert-image|thumb|256 iterations of Rule 110]]
{| class="wikitable" style="text-align: center"
|+ [[Rule 110]] cellular automaton<br>(binary 01101110 = decimal 110)
|-
! current pattern
| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000
|-
! new state for center cell
| 0 || 1 || 1 || 0 || 1 || 1 || 1 || 0
|}
Rule 110, like the Game of Life, exhibits what Wolfram calls ''class 4'' behavior, which is neither completely random nor completely repetitive. Localized structures appear and interact in various complicated-looking ways. In the course of the development of ''[[A New Kind of Science]]'', as a research assistant to Wolfram in 1994, [[Matthew Cook]] proved that some of these structures were rich enough to support [[universal Turing machine|universality]]. This result is interesting because rule 110 is an extremely simple one-dimensional system, and difficult to engineer to perform specific behavior. This result therefore provides significant support for Wolfram's view that class 4 systems are inherently likely to be universal. Cook presented his proof at a [[Santa Fe Institute]] conference on Cellular Automata in 1998, but Wolfram blocked the proof from being included in the conference proceedings, as Wolfram did not want the proof announced before the publication of ''A New Kind of Science''.<ref name=giles>{{cite journal | author=Giles, Jim | title=What Kind of Science is This? | journal=[[Nature (journal)|Nature]] | volume=417 | issue=6886 | pages=216–218 | year=2002|doi=10.1038/417216a | pmid=12015565 | bibcode=2002Natur.417..216G | s2cid=10636328 | doi-access=free }}</ref> In 2004, Cook's proof was finally published in Wolfram's journal ''[[Complex Systems (journal)|Complex Systems]]'' (Vol. 15, No. 1), over ten years after Cook came up with it. Rule 110 has been the basis for some of the smallest universal Turing machines.<ref>{{cite journal | url=http://www.nybooks.com/articles/archives/2002/oct/24/is-the-universe-a-computer/?pagination=false | author=Weinberg, Steven | title=Is the Universe a Computer? | journal=[[The New York Review of Books]] | date=24 October 2002 | volume=49 | issue=16 | access-date=12 October 2012}}</ref>
==
An elementary cellular automaton rule is specified by 8 bits, and all elementary cellular automaton rules can be considered to sit on the [[vertex (geometry)|vertices]] of the 8-dimensional unit [[hypercube]]. This unit hypercube is the cellular automaton rule space. For next-nearest-neighbor cellular automata, a rule is specified by 2<sup>5</sup> = 32 bits, and the cellular automaton rule space is a 32-dimensional unit hypercube. A distance between two rules can be defined by the number of steps required to move from one vertex, which represents the first rule, and another vertex, representing another rule, along the [[edge (geometry)|edge]] of the hypercube. This rule-to-rule distance is also called the [[Hamming distance]].
Cellular automaton rule space allows us to ask the question concerning whether rules with similar dynamical behavior are "close" to each other. Graphically drawing a high dimensional hypercube on the 2-dimensional plane remains a difficult task, and one crude locator of a rule in the hypercube is the number of bit-1 in the 8-bit string for elementary rules (or 32-bit string for the next-nearest-neighbor rules). Drawing the rules in different Wolfram classes in these slices of the rule space show that class 1 rules tend to have lower number of bit-1s, thus located in one region of the space, whereas class 3 rules tend to have higher proportion (50%) of bit-1s.<ref name=li-packard />
For larger cellular automaton rule space, it is shown that class 4 rules are located between the class 1 and class 3 rules.<ref>{{cite journal|journal=Physica D|volume=45|issue=1–3|year=1990|pages=77–94|title= Transition phenomena in cellular automata rule space |author1=Wentian Li |author2=Norman Packard |author3=Chris G Langton |doi=10.1016/0167-2789(90)90175-O|bibcode = 1990PhyD...45...77L |citeseerx=10.1.1.15.2786}}</ref> This observation is the foundation for the phrase [[edge of chaos]], and is reminiscent of the [[phase transition]] in [[thermodynamics]].
==Applications==
===Biology===
[[File:Textile cone.JPG|thumb|left|''[[Conus textile]]'' exhibits a cellular automaton pattern on its shell.<ref name=coombs/>]]
{{further|Patterns in nature}}
Several biological processes occur—or can be simulated—by cellular automata.
Some examples of biological phenomena modeled by cellular automata with a simple state space are:
* Patterns of some [[seashell]]s, like the ones in the genera ''[[Cone snail|Conus]]'' and ''[[Cymbiola]]'', are generated by natural cellular automata. The [[pigment]] cells reside in a narrow band along the shell's lip. Each cell [[secretion|secretes]] pigments according to the activating and inhibiting activity of its neighbor pigment cells, obeying a natural version of a mathematical rule.<ref name="coombs">{{citation|last=Coombs|first=Stephen|title=The Geometry and Pigmentation of Seashells|date=15 February 2009|url=http://www.maths.nott.ac.uk/personal/sc/pdfs/Seashells09.pdf|pages=3–4|archive-url=https://web.archive.org/web/20130107235922/http://www.maths.nott.ac.uk/personal/sc/pdfs/Seashells09.pdf|access-date=2 September 2012|archive-date=7 January 2013|url-status=dead}}</ref> The cell band leaves the colored pattern on the shell as it grows slowly. For example, the widespread species ''[[Conus textile]]'' bears a pattern resembling Wolfram's [[rule 30]] cellular automaton.<ref name="coombs" />
* Plants regulate their intake and loss of gases via a cellular automaton mechanism. Each [[Stomata|stoma]] on the leaf acts as a cell.<ref>{{cite journal | doi = 10.1073/pnas.0307811100 | last1 = Peak | first1 = West | last2 = Messinger | first2 = Mott | year = 2004 | title = Evidence for complex, collective dynamics and emergent, distributed computation in plants | journal = Proceedings of the National Academy of Sciences | volume = 101 | issue = 4| pages = 918–922 |bibcode = 2004PNAS..101..918P | pmid=14732685 | pmc=327117| doi-access = free }}</ref>
* Moving wave patterns on the skin of [[cephalopod]]s can be simulated with a two-state, two-dimensional cellular automata, each state corresponding to either an expanded or retracted [[chromatophore]].<ref>{{Cite web|title=Archived copy|url=http://gilly.stanford.edu/past_research_files/APackardneuralnet.pdf|url-status=dead|archive-url=https://web.archive.org/web/20100725123926/http://gilly.stanford.edu/past_research_files/APackardneuralnet.pdf|archive-date=25 July 2010|access-date=14 September 2008}}</ref>
* Threshold automata have been invented to simulate [[neuron]]s, and complex behaviors such as recognition and learning can be simulated.<ref name="ilachinski-275">{{Harvnb|Ilachinsky|2001|p=275|ref=ilachinski}}</ref>
* [[Fibroblast]]s bear similarities to cellular automata, as each fibroblast only interacts with its neighbors.<ref>{{cite book|title=Disordered Systems and Biological Organization|year=1986|pages=374–375|author=Yves Bouligand|chapter=Fibroblasts, Morphogenesis and Cellular Automata}}</ref>
Additionally, biological phenomena which require explicit modeling of the agents' velocities (for example, those involved in [[collective cell migration]]) may be modeled by cellular automata with a more complex state space and rules, such as [[BIO-LGCA|biological lattice-gas cellular automata]]. These include phenomena of great medical importance, such as:
* Characterization of different modes of [[Metastasis|metastatic]] invasion.<ref>{{Cite journal|last1=Ilina|first1=Olga|last2=Gritsenko|first2=Pavlo G.|last3=Syga|first3=Simon|last4=Lippoldt|first4=Jürgen|last5=La Porta|first5=Caterina A. M.|last6=Chepizhko|first6=Oleksandr|last7=Grosser|first7=Steffen|last8=Vullings|first8=Manon|last9=Bakker|first9=Gert-Jan|last10=Starruß|first10=Jörn|last11=Bult|first11=Peter|date=September 2020|title=Cell–cell adhesion and 3D matrix confinement determine jamming transitions in breast cancer invasion|journal=Nature Cell Biology|language=en|volume=22|issue=9|pages=1103–1115|doi=10.1038/s41556-020-0552-6|issn=1465-7392|pmc=7502685|pmid=32839548}}</ref>
* The role of [[Tumour heterogeneity|heterogeneity]] in the development of aggressive carcinomas.<ref>{{Cite journal|last1=Reher|first1=David|last2=Klink|first2=Barbara|last3=Deutsch|first3=Andreas|last4=Voss-Böhme|first4=Anja|date=2017-08-11|title=Cell adhesion heterogeneity reinforces tumour cell dissemination: novel insights from a mathematical model|journal=Biology Direct|volume=12|issue=1|pages=18|doi=10.1186/s13062-017-0188-z|issn=1745-6150|pmc=5553611|pmid=28800767 |doi-access=free }}</ref>
* [[Phenotypic switching]] during tumor proliferation.<ref>{{Cite journal|last1=Hatzikirou|first1=H.|last2=Basanta|first2=D.|last3=Simon|first3=M.|last4=Schaller|first4=K.|last5=Deutsch|first5=A.|date=2012-03-01|title='Go or Grow': the key to the emergence of invasion in tumour progression?|url=https://academic.oup.com/imammb/article-lookup/doi/10.1093/imammb/dqq011|journal=Mathematical Medicine and Biology|language=en|volume=29|issue=1|pages=49–65|doi=10.1093/imammb/dqq011|pmid=20610469|issn=1477-8599}}</ref>
===Chemistry===
The [[Belousov–Zhabotinsky reaction]] is a spatio-temporal [[chemical oscillator]] that can be simulated by means of a cellular automaton. In the 1950s [[Anatol Zhabotinsky|A. M. Zhabotinsky]] (extending the work of [[B. P. Belousov]]) discovered that when a thin, homogenous layer of a mixture of [[malonic acid]], acidified bromate, and a ceric salt were mixed together and left undisturbed, fascinating geometric patterns such as concentric circles and spirals propagate across the medium. In the "Computer Recreations" section of the August 1988 issue of ''[[Scientific American]]'',<ref>A. K. Dewdney, The hodgepodge machine makes waves, Scientific American, p. 104, August 1988.</ref> [[A. K. Dewdney]] discussed a cellular automaton<ref>{{cite journal | last1 = Gerhardt | first1 = M. | last2 = Schuster | first2 = H. | year = 1989 | title = A cellular automaton describing the formation of spatially ordered structures in chemical systems | journal = Physica D | volume = 36 | issue = 3| pages = 209–221 | doi=10.1016/0167-2789(89)90081-x| bibcode = 1989PhyD...36..209G }}</ref> developed by Martin Gerhardt and Heike Schuster of the University of Bielefeld (Germany). This automaton produces wave patterns that resemble those in the Belousov-Zhabotinsky reaction. Combining the attachment to one only particle from the growing aggregate, following the seminal model of Witten and Sander <ref>{{Cite journal |last1=Witten |first1=T. A. |last2=Sander |first2=L. M. |date=1981-11-09 |title=Diffusion-Limited Aggregation, a Kinetic Critical Phenomenon |url=https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.47.1400 |journal=Physical Review Letters |volume=47 |issue=19 |pages=1400–1403 |doi=10.1103/PhysRevLett.47.1400|bibcode=1981PhRvL..47.1400W }}</ref> to simulate the diffusion-limited growth with the attachment to kink positions as proposed yet by Kossel and Stranski in 1920's, see <ref>{{Cite journal |last=Woodruff |first=D. P. |date=2015-04-13 |title=How does your crystal grow? A commentary on Burton, Cabrera and Frank (1951) 'The growth of crystals and the equilibrium structure of their surfaces' |journal=Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences |volume=373 |issue=2039 |pages=20140230 |doi=10.1098/rsta.2014.0230 |pmc=4360084 |pmid=25750141|bibcode=2015RSPTA.37340230W }}</ref> for the kinetics-limited version of the attachment, Goranova et al <ref>{{Cite journal |last1=Goranova |first1=D. |last2=Rashkov |first2=R. |last3=Avdeev |first3=G. |last4=Tonchev |first4=V. |date=2016-09-01 |title=Electrodeposition of Ni–Cu alloys at high current densities: details of the elements distribution |url=https://link.springer.com/article/10.1007/s10853-016-0126-y |journal=Journal of Materials Science |language=en |volume=51 |issue=18 |pages=8663–8673 |doi=10.1007/s10853-016-0126-y |bibcode=2016JMatS..51.8663G |issn=1573-4803}}</ref>proposed a model for electrochemical co-deposition of two metal cations.
===Physics===
[[File:Gas velocity.gif|thumb|300px|right|Visualization of a lattice gas automaton. The shades of grey of the individual pixels are proportional to the gas particle density (between 0 and 4) at that pixel. The gas is surrounded by a shell of black cells that act as reflectors to create a closed space.]]
Probabilistic cellular automata are used in [[statistical physics|statistical]] and [[condensed matter physics]] to study phenomena like fluid dynamics and phase transitions. The [[Ising model]] is a prototypical example, in which each cell can be in either of two states called "up" and "down", making an idealized representation of a [[magnet]]. By adjusting the parameters of the model, the proportion of cells being in the same state can be varied, in ways that help explicate how [[ferromagnet]]s become demagnetized when heated. Moreover, results from studying the demagnetization phase transition can be transferred to other phase transitions, like the evaporation of a liquid into a gas; this convenient cross-applicability is known as [[universality (dynamical systems)|universality]].<ref>{{cite book|last=Sethna |first=James P. |title=Statistical Mechanics: Entropy, Order Parameters, and Complexity |year=2008 |publisher=[[Oxford University Press]] |url=https://pages.physics.cornell.edu/~sethna/StatMech/ |isbn=978-0-198-56677-9 |oclc=845714772}}</ref><ref>{{cite book|first=Mehran |last=Kardar |author-link=Mehran Kardar |title=Statistical Physics of Fields |title-link=Statistical Physics of Particles |year=2007 |publisher=[[Cambridge University Press]] |isbn=978-0-521-87341-3 |oclc=920137477}}</ref> The phase transition in the [[Two-dimensional critical Ising model|two-dimensional Ising model]] and other systems in its [[universality class]] has been of particular interest, as it requires [[conformal field theory]] to understand in depth.<ref>{{cite journal|first1=Andrea |last1=Cappelli |first2=Jean-Bernard |last2=Zuber |author-link2=Jean-Bernard Zuber |year=2010 |title=A-D-E Classification of Conformal Field Theories |journal=[[Scholarpedia]] |volume=5 |number=4 |pages=10314 |arxiv=0911.3242 |doi=10.4249/scholarpedia.10314 |bibcode=2010SchpJ...510314C|s2cid=18207779 |doi-access=free }}</ref>
Other cellular automata that have been of significance in physics include [[lattice gas automaton|lattice gas automata]], which simulate fluid flows. In a series of works<ref name="Krzyzewski2017"/><ref name="Toktarbaiuly2018"/><ref name="Krzyzewski2019"/><ref name="Popova2020"/> the so-called ''vicinal Cellular Automaton'' (vicCA) was proposed and further developed to model the possibly unstable growth and sublimation of vicinal crystal surfaces in 1+1D. Besides the attachment/detachment events being encoded in the rules of the CA, the adatoms on top of the vicinal form a thin layer, and their thermal motion is modeled by a Monte Carlo module.<ref name="Krzyzewski2017"/><ref name="Krzyzewski2019"/> A decisive step further was the transition of the model to 2+1D,<ref name="Zaluska2021"/> where a number of different structures were obtained, referred to by the authors as “vicinal creatures”—step bunches, step meanders, nano-pillars, nanowires, etc.<ref name="Zaluska2021"/> The vicCA model was extensively used by Alexey Redkov<ref name="Redkov2025"/> to develop a Machine Learning algorithm on top of it, significantly speeding up calculations by a factor of 10⁵ while enabling systematic classification of the observed phenomena.
===Computer science, coding, and communication===
Cellular automaton processors are physical implementations of CA concepts, which can process information computationally. Processing elements are arranged in a regular grid of identical cells. The grid is usually a square tiling, or [[tessellation]], of two or three dimensions; other tilings are possible, but not yet used. Cell states are determined only by interactions with adjacent neighbor cells. No means exists to communicate directly with cells farther away.<ref>{{cite book | author=Muhtaroglu, Ali | title=Cellular Automaton Processor Based Systems for Genetic Sequence Comparison/Database Searching | chapter=4.1 Cellular Automaton Processor (CAP) | pages=62–74 | publisher=Cornell University |date=August 1996}}</ref> One such cellular automaton processor array configuration is the [[systolic array]]. Cell interaction can be via electric charge, magnetism, vibration ([[phonons]] at quantum scales), or any other physically useful means. This can be done in several ways so that no wires are needed between any elements. This is very unlike processors used in most computers today ([[Von Neumann architecture|von Neumann designs]]) which are divided into sections with elements that can communicate with distant elements over wires.
[[Rule 30]] was originally suggested as a possible [[block cipher]] for use in [[cryptography]]. Two-dimensional cellular automata can be used for constructing a [[pseudorandom number generator]].<ref>{{cite journal | first1=M. | last1=Tomassini | first2=M. | last2=Sipper | first3=M. | last3=Perrenoud | title=On the generation of high-quality random numbers by two-dimensional cellular automata | journal=IEEE Transactions on Computers | volume=49 | issue=10 | pages=1146–1151 | year=2000 | doi=10.1109/12.888056| s2cid=10139169 | url=http://infoscience.epfl.ch/record/28657 }}</ref> Cellular automata have been proposed for [[public-key cryptography]]. The [[one-way function]] is the evolution of a finite CA whose inverse is believed to be hard to find. Given the rule, anyone can easily calculate future states, but it appears to be very difficult to calculate previous states. <!-- However, the designer of the rule can create it in such a way as to easily invert it. Therefore, it is apparently a [[trapdoor function]], and can be used as a public-key cryptosystem. The security of such systems is not currently known. --> Cellular automata have also been applied to design [[ECC memory|error correction codes]].<ref>{{cite journal | title=Design of CAECC - cellular automata based error correcting code | first1=D. Roy | last1=Chowdhury | first2=S. | last2=Basu | first3=I. Sen | last3=Gupta | first4=P. Pal | last4=Chaudhuri | journal=[[IEEE Transactions on Computers]] | volume=43 | issue=6 | date=June 1994 | doi=10.1109/12.286310 | pages=759–764}}</ref>
In the study of cellular automaton as computational systems, understanding their underlying generative rules is crucial for applications in coding, [[cryptography]], and system design. Other recent work has taken a more general approach to such problems. A noteworthy conceptual framework for extracting generative rules from complex dynamical systems was introduced by Zenil et al. (2019), based on [[Algorithmic information theory]] (AIT) with an algorithmic information calculus (AIC),<ref>{{cite journal |last1=Zenil |first1=Hector |last2=Kiani |first2=N. A. |last3=Marabita |first3=F. |last4=Deng |first4=Y. |last5=Elias |first5=S. |last6=Schmidt |first6=A. |last7=Ball |first7=G. |last8=Tegnér |first8=J. |title=An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems |journal=Science |year=2019 |doi=10.1016/j.sci.2019.30270-6 |doi-broken-date=17 July 2025 }}</ref> under the name Algorithmic Information Dynamics (AID).<ref>{{cite journal | last=Zenil | first=Hector | title=Algorithmic Information Dynamics | journal=Scholarpedia | date=25 July 2020 | volume=15 | issue=7 | doi=10.4249/scholarpedia.53143 | doi-access=free | bibcode=2020SchpJ..1553143Z | hdl=10754/666314 | hdl-access=free }}</ref> In the context of cellular automata, AID was used to reconstruct phase spaces and identify causal mechanisms of discrete systems (including CA).<ref>{{cite journal |last1=Zenil |first1=Hector |last2=Kiani |first2=Narsis A. |last3=Zea |first3=Allan A. |last4=Tegnér |first4=Jesper |title=Causal deconvolution by algorithmic generative models |journal=Nature Machine Intelligence |volume=1 |issue=1 |year=2019 |pages=58–66 |doi=10.1038/s42256-018-0005-0 }}</ref> This approach applied perturbation analysis to quantify the [[Kolmogorov complexity|algorithmic complexity]] of system components, enabling reconstruction of the system’s generative rules without requiring explicit kinetic equations. This method provided insights into the causal structure of systems and their reprogrammability toward desired states.<ref> {{cite book | last1=Zenil | first1=Hector | last2=Kiani | first2=Narsis A. | last3=Tegner | first3=Jesper | title=Algorithmic Information Dynamics: A Computational Approach to Causality with Applications to Living Systems | publisher=Cambridge University Press | year=2023 | doi=10.1017/9781108596619 | isbn=978-1-108-59661-9 | url=https://doi.org/10.1017/9781108596619}}</ref>
Other problems that can be solved with cellular automata include:
* [[Firing squad synchronization problem]]
* [[Majority problem (cellular automaton)|Majority problem]]
===Generative art and music===
{{see|Generative art}}
Cellular automata have been used in [[generative music]]<ref>Burraston, Dave, and Ernest Edmonds. "[https://web2.qatar.cmu.edu/~gdicaro/15382-Spring18/additional/generative-music-ca-review.pdf Cellular automata in generative electronic music and sonic art: a historical and technical review]." Digital Creativity 16.3 (2005): 165-185.</ref> and [[evolutionary music]] composition<ref>Miranda, Eduardo Reck. "[https://sites.google.com/site/jimmycifuentes/EvolvingCAMusic.pdf Evolving cellular automata music: From sound synthesis to composition]." Proceedings of 2001 Workshop on Artificial Life Models for Musical Applications. 2001.</ref> and [[procedural terrain]] generation in video games.<ref>{{Cite book|chapter-url=https://link.springer.com/chapter/10.1007/978-3-030-14687-0_2|doi = 10.1007/978-3-030-14687-0_2|chapter = Evolving Diverse Cellular Automata Based Level Maps|title = Proceedings of 6th International Conference in Software Engineering for Defence Applications|series = Advances in Intelligent Systems and Computing|year = 2020|last1 = Ashlock|first1 = Daniel|last2 = Kreitzer|first2 = Matthew|volume = 925|pages = 10–23|isbn = 978-3-030-14686-3| s2cid=85562837 }}</ref>
===Maze generation===
{{excerpt|Maze generation algorithm|Cellular automaton algorithms}}
==Specific rules==
Specific cellular automata rules include:
{{cols}}
* [[Brian's Brain]]
* [[Codd's cellular automaton]]
* [[CoDi]]
* [[Conway's game of life]]
* [[Day and Night (cellular automaton) |Day and Night]]
* [[Langton's ant]]
* [[Langton's loops]]
* [[
* [[Nobili cellular automata]]
* [[Rule 90]]
* [[Rule 184]]
* [[Seeds (cellular automaton)|Seeds]]
* [[Turmite]]
* [[Von Neumann cellular automaton]]
* [[Wireworld]]
{{colend}}
==See also==
{{cols|colwidth=26em}}
* {{annotated link|Agent-based model}}
* {{annotated link|Automata theory}}
* {{annotated link|Cyclic cellular automaton}}
* {{annotated link|Discrete calculus}}
* {{annotated link|Excitable medium}}
* {{annotated link|Golly (program)|Golly}}
* {{annotated link|Iterative Stencil Loops}}
* {{annotated link|Lattice model (physics)|Lattice model}}
* {{annotated link|Movable cellular automaton}}
* {{annotated link|Quantum cellular automaton}}
* {{annotated link|Spatial decision support system}}
* {{annotated link|Unconventional computing}}
{{colend}}
==References==
{{Reflist|30em|refs=
<ref name="Krzyzewski2017">F. Krzyżewski, M. Załuska-Kotur, A. Krasteva, H. Popova, and V. Tonchev, "Step bunching and macrostep formation in 1D atomistic scale model of unstable vicinal crystal growth," Journal of Crystal Growth '''474''', 135 (2017). [https://doi.org/10.1016/j.jcrysgro.2017.06.010 DOI]</ref>
<ref name="Toktarbaiuly2018">O. Toktarbaiuly et al., "Step bunching with both directions of the current: Vicinal W(110) surfaces versus atomistic-scale model," Phys. Rev. B '''97''', 035436 (2018). [https://doi.org/10.1103/PhysRevB.97.035436 DOI]</ref>
<ref name="Krzyzewski2019">F. Krzyżewski, M. Załuska-Kotur, A. Krasteva, H. Popova, and V. Tonchev, "Scaling and Dynamic Stability of Model Vicinal Surfaces," Crystal Growth & Design '''19''', 821 (2019). [https://doi.org/10.1021/acs.cgd.8b01587 DOI]</ref>
<ref name="Popova2020">H. Popova, F. Krzyżewski, M. A. Załuska-Kotur, and V. Tonchev, "Quantifying the Effect of Step–Step Exclusion on Dynamically Unstable Vicinal Surfaces: Step Bunching without Macrostep Formation," Crystal Growth & Design '''20''', 7246 (2020). [https://doi.org/10.1021/acs.cgd.0c00957 DOI]</ref>
<ref name="Zaluska2021">M. Załuska-Kotur, H. Popova, and V. Tonchev, "Step bunches, nanowires and other vicinal 'Creatures'—Ehrlich–Schwoebel effect by cellular automata," Crystals '''11''', 1135 (2021). [https://doi.org/10.3390/cryst11091135 DOI]</ref>
<ref name="Redkov2025">A. V. Redkov, "Data science of the in silico crystallization," Acta Materialia '''287''', 120762 (2025). [https://doi.org/10.1016/j.actamat.2025.120762 DOI]</ref>
}}
==
{{Refbegin|30em}}
*{{cite book | title=Game of Life Cellular Automata|editor-first=Andrew | editor-last=Adamatzky | editor-link=Andrew Adamatzky | publisher=Springer | year=2010 | isbn=978-1-84996-216-2 }}
*{{cite book | first1=Iwo | last1=Bialynicki-Birula | first2=Iwona | last2=Bialynicka-Birula | title=Modeling Reality: How Computers Mirror Life | year=2004 | publisher=[[Oxford University Press]] | isbn=978-0-19-853100-5| ref=bialynick}}
*{{cite book | first1=Bastien | last1=Chopard | first2=Michel | last2=Droz | title=Cellular Automata Modeling of Physical Systems | year=2005 | publisher=[[Cambridge University Press]] | isbn=978-0-521-46168-9 | ref=chopard-droz}}
* {{Harvc|last=Eppstein|first=David|year=2010|contribution=Growth and decay in life-like cellular autometa|in= Adamatzky}}
*{{cite book | editor=Gutowitz, Howard | title=Cellular Automata: Theory and Experiment | year=1991 | publisher=[[MIT Press]] | isbn=978-0-262-57086-2 | ref=gutowitz}}
*{{cite book | author=Ilachinski, Andrew | title=Cellular Automata: A Discrete Universe | year=2001 | publisher=[[World Scientific]] | isbn=978-981-238-183-5 | ref=ilachinski}}
*{{cite book | first1=Lemont B. | last1=Kier | first2=Paul G. | last2=Seybold | first3=Chao-Kun | last3=Cheng | title=Modeling Chemical Systems using Cellular Automata | year=2005 | publisher=Springer | isbn=978-1-4020-3657-6 | ref=kier-seybold-cheng}}
* {{cite book | last=von Neumann |first=John |editor-last=Burks |editor-first=Arthur W. | title=Theory of Self-Reproducing Automata | url=https://archive.org/details/theoryofselfrepr00vonn_0 |url-access=registration | year=1966 | publisher=[[University of Illinois Press]] |place=Urbana}}
* {{Harvc|last=Wainwright|first=Robert|year=2010|contribution=Conway's game of life: early personal recollections|in= Adamatzky}}
*{{cite book | author=Wolfram, Stephen | author-link=Stephen Wolfram | title=A New Kind of Science | year=2002 | publisher=[[Wolfram Media]] | isbn=978-1-57955-008-0 | ref=wolfram | url=https://archive.org/details/newkindofscience00wolf }}
{{refend}}
==Further reading==
{{refbegin|30em}}
*{{cite SEP |url-id=cellular-automata |title=Cellular Automata |first=Francesco |last=Berto |first2=Jacopo |last2=Tagliabue |ref=none}}
*{{cite book |chapter=The Evolutionary Design of Collective Computation in Cellular Automata |first1=James P. |last1=Crutchfeld |first2=Melanie |last2=Mitchell |first3=Rajarshi |last3=Das |editor1-first=J. P. |editor1-last=Crutchfield |editor2-first=P. K. |editor2-last=Schuster |title=Evolutionary Dynamics: Exploring the Interplay of Selection, Neutrality, Accident, and Function |place=New York |publisher=Oxford University Press |year=2002 |ref=none}}
*{{cite journal |last1=Kroc |first1=Jiří |last2=Jiménez-Morales |first2=Francisco |last3=Guisado |first3=José Luis |last4=Lemos |first4=María Carmen |last5=Tkáč |first5=Jakub |title=Building Efficient Computational Cellular Automata Models of Complex Systems: Background, Applications, Results, Software, and Pathologies |date=December 2019 |url=https://www.researchgate.net/publication/338019707 |journal=Advances in Complex Systems |volume=22 |issue=5 |pages=1950013 (38 pages) |doi=10.1142/S0219525919500139 |s2cid=212988726 |ref=none}}
*{{cite conference |title=Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work |first1=Melanie |last1=Mitchell |first2=James P. |last2=Crutchfeld |first3=Rajarshi |last3=Das |conference=Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96) |place=Moscow, Russia |publisher=Russian Academy of Sciences |year=1996 |ref=none}}
*{{cite journal |first=A. M. |last=Turing |year=1952 |title=The Chemical Basis of Morphogenesis |journal= Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences|volume=B237 |issue=641 |pages=37–72 |doi=10.1098/rstb.1952.0012 |bibcode=1952RSPTB.237...37T |ref=none}} Proposes reaction-diffusion, a type of continuous automaton.
{{refend}}
==External links==
{{Commons category|Cellular automata}}
{{Wikibooks|Cellular Automata}}
*[https://mcell.ca/ Mirek's Cellebration] – Home to free cellular automata explorer software, "MCell". The software supports a large number of 1D and 2D rules. The site provides both an extensive rules lexicon and many image galleries loaded with examples of rules. Source code (Javascript) is available.
*[https://www.sourceforge.net/projects/golly Golly] supports von Neumann, Nobili, GOL, and a great many other systems of cellular automata. Developed by Tomas Rokicki and Andrew Trevorrow. This is the only simulator currently available that can demonstrate von Neumann type self-replication.
*[http://atlas.wolfram.com/TOC/TOC_200.html Wolfram Atlas] – An atlas of various types of one-dimensional cellular automata.
*[http://www.conwaylife.com/ Conway Life]
*[http://cafaq.com/ Cellular automaton FAQ] from the newsgroup comp.theory.cell-automata
*[http://cell-auto.com/neighbourhood/index.html "Neighbourhood Survey"] (includes discussion on triangular grids, and larger neighborhood CAs)
*[http://bactra.org/notebooks/cellular-automata.html Cosma Shalizi's Cellular Automata Notebook] contains an extensive list of academic and professional reference material.
{{Authority control}}
[[Category:Cellular automata| ]]
[[Category:Systems theory]]
[[Category:Dynamical systems]]
[[Category:Computational fields of study]]
| |||