A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, and theoretical biology. It consists of an infinite, regular grid of cells, each in one of a finite number of states. The grid can be in any finite number of dimensions. Time is also discrete, and the state of a cell at time t is a function of the states of a finite number of cells (called its neighborhood) at time t-1. These neighbors are a selection of cells relative to the specified cell, and do not change. (Though the cell itself may be in its neighborhood, it is not usually considered a neighbor.) Every cell has the same rule for updating, based on the values in this neighbourhood. Each time the rules are applied to the whole grid a new generation is created. Discrete mathematics, also called finite mathematics, is the study of mathematical structures that are fundamentally discrete, in the sense of not supporting or requiring the notion of continuity. ... In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation. ... Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Theoretical biology is an interdisciplinary field of academic study and research that involves the use of quantitative tools in biology. ... In information processing, a state is the complete set of properties (for example, its energy level, etc. ... Discrete time is non-continuous time. ...

Overview

One example of a cellular automaton (CA) would be an infinite sheet of graph paper, where each square is a cell, each cell has two possible states (black and white), and the neighbors of a cell are the 8 squares touching it. Then, there are 2⁹ = 512 possible patterns for a cell and its neighbors. The rule for the cellular automaton could be given as a table. For each of the 512 possible patterns, the table would state whether the center cell will be black or white on the next time step. This is an example of a two dimensional cellular automaton. See Conway's Game of Life for the most popular CA of this form. Graph paper or quad-ruled paper is writing paper that is printed with fine lines making up a regular grid. ... Gospers Glider Gun creating gliders. The Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. ...

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, often called a configuration. More generally, it is sometimes assumed that the universe starts out covered with a periodic pattern, and only a finite number of cells violate that pattern. The latter assumption is common in one-dimensional cellular automata.

A torus, a toroidal shape.

Cellular automata are often simulated on a finite grid rather than an infinite one. In two dimensions, the universe would be a rectangle instead of an infinite plane. The obvious problem with finite grids is how to handle the cells on the edges. How they are handled will affect the values of all the cells in the grid. One possible method is to allow the values in those cells to remain constant. Another method is to define neighbourhoods differently for these cells. One could say that they have fewer neighbours, but then one would also have to define new rules for the cells located on the edges. These cells are usually handled with a toroidal arrangement: when one goes off the top, one comes in at the corresponding position on the bottom, and when one goes off the left, one comes in on the right. (This essentially simulates an infinite periodic tiling, and in the field of Partial Differential Equations is sometimes referred to as periodic boundary conditions.) This can be visualized as taping the left and right edges of the rectangle to form a tube, then taping the top and bottom edges of the tube to form a torus (doughnut shape). Universes of other dimensions are handled similarly. This is done in order to solve boundary problems with neighborhoods. For example, in a 1-dimensional cellular automaton like the examples below, the neighborhood of a cell x_i^t—where t is the time step (vertical), and i is the index (horizontal) in one generation—is {x_i−1^t−1, x_i^t−1, x_i+1^t−1}. There will obviously be problems when a neighbourhood on a left border references its upper left cell, which is not in the cellular space, as part of its neighborhood. Image File history File links Torus. ... Image File history File links Torus. ... In geometry, a torus (pl. ... In mathematics, a periodic function is a function that repeats its values, after adding some definite period to the variable. ... In mathematics, and in particular analysis, a partial differential equation (PDE) is an equation involving partial derivatives of an unknown function. ... In geometry, a torus (pl. ... Dimension (from Latin measured out) is, in essence, the number of degrees of freedom available for movement in a space. ...

History

Stanislaw Ulam, while working at the Los Alamos National Laboratory in the 1940s, studied the growth of crystals, using a simple lattice network as his model. At the same time, John von Neumann, Ulam's colleague at Los Alamos, was working on the problem of self-replicating systems. Von Neumann's initial design was founded upon the notion of one robot building another robot. This design is known as the kinematic model. 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. Ulam suggested that von Neumann develop his design around a mathematical abstraction, such as the one Ulam used to study crystal growth. Thus was born the first system of cellular automata. Like Ulam's lattice network, von Neumann's cellular automata are two-dimensional, with his self-replicator implemented algorithmically. The result was a universal copier and constructor working within a CA 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. Neumann proved mathematically that a particular pattern would make endless copies of itself within the given cellular universe. This design is known as the tessellation model. Stanisław Ulam in the 1950s. ... Los Alamos National Laboratory, aerial view from 1995. ... In physics, a lattice model is a physical model that is defined on a lattice, as opposed to the continuum of space or spacetime. ... John von Neumann (Hungarian Margittai Neumann János Lajos) (born December 28, 1903 in Budapest, Austria-Hungary; died February 8, 1957 in Washington D.C., United States) was a Hungarian-born mathematician and polymath who made contributions to quantum physics, functional analysis, set theory, topology, economics, computer science, numerical analysis... Self-replication is the process by which some things make copies of themselves. ... Von Neumann cellular automata are the original expression of cellular automata, the development of which were prompted by suggestions made to John von Neumann, by his close friend and mathematician Stanisław Ulam. ... It has been suggested that this article or section be merged with Universal Assembler. ... In mathematics, orthogonal is synonymous with perpendicular when used as a simple adjective that is not part of any longer phrase with a standard definition. ... A tessellated plane seen in street pavement. ...

In the 1970s a two-state, two-dimensional cellular automaton named Game of Life became very widely known, particularly among the early computing community. Invented by John Conway, and popularized by Martin Gardner in a Scientific American article, its rules are as follows: If a black cell has 2 or 3 black neighbors, it stays black. If a white cell has 3 black neighbors, it becomes black. In all other cases, the cell stays or becomes white. 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. Possibly because it was viewed as a largely recreational topic, little follow-up work was done outside of investigating the particularities of the Game of Life and a few related rules. The 1970s decade refers to the years from 1970 to 1979, inclusive. ... Gospers Glider Gun creating gliders. The Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. ... John Horton Conway (born December 26, 1937, Liverpool, England) is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. ... Martin Gardner (b. ... Scientific American is a popular-science magazine, published (first weekly and later monthly) since August 28, 1845, making it the oldest continuously published magazine in the United States. ... An artistic representation of a Turing Machine . ...

In 1969, however, 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 just the output of a deterministic computation on a giant cellular automaton. This was the first book on what today is called digital physics. For the Stargate SG-1 episode, see 1969 (Stargate SG-1). ... Konrad Zuse (1992) Statue in Bad Hersfeld Konrad Zuse (June 22, 1910 – December 18, 1995) was a German engineer and computer pioneer. ... Calculating Space is the title of MIT´s English Translation of Konrad Zuse´s book Rechnender Raum (published in Germany in 1969), the first book on digital physics. ... In theoretical physics, digital physics holds the basic premise that the entire history of our universe is computable, that is, the output of a (presumably short) computer program. ...

In 1983 Stephen Wolfram published the first of a series of papers systematically investigating a very basic but essentially unknown class of cellular automata, which he terms elementary cellular automata (see below). The unexpected complexity of the behavior of these simple rules led Wolfram to suspect that complexity in nature may be due to similar mechanisms. Additionally, during this period Wolfram formulated the concepts of intrinsic randomness and computational irreducibility, and suggested that rule 110 may be universal—a fact proved by Matthew Cook in the 1990s. 1983 (MCMLXXXIII) was a common year starting on Saturday of the Gregorian calendar. ... Stephen Wolfram (born August 29, 1959 in London) is a scientist known for his work in theoretical particle physics, cellular automata, complexity theory, and computer algebra, and is the creator of the computer program Mathematica. ... The rule 110 cellular automaton is a one-dimensional two-state cellular automaton with the following rule table: Rule 110, like the Game of Life, exhibits what Stephen Wolfram calls Class 4 behavior, which is neither completely random nor completely repetitive. ... In computability theory a programming language or any other logical system is called Turing-complete if it has a computational power equivalent to a universal Turing machine. ... Matthew Cook was born in Morgantown, West Virginia, in 1970 and grew up in Evanston, Illinois. ...

Wolfram left academia in the mid-late 1980s to create Mathematica, which he then used to extend his earlier results to a broad range of other simple, abstract systems. In 2002 he published his results in the 1280-page text A New Kind of Science, which extensively argued that the discoveries about cellular automata are not isolated facts but are robust and have significance for all disciplines of science. Despite much confusion in the press and academia, the book did not argue for a fundamental theory of physics based on cellular automata, and although it did describe a few specific physical models based on cellular automata, it also provided models based on qualitatively different abstract systems. The 1980s refers to the years of and between 1980 and 1989. ... This article is about computer software. ... For album titles with the same name, see 2002 (album). ... A New Kind of Science is a controversial book by Stephen Wolfram, published in 2002. ...

In his 2005 book, The Lifebox, The Seashell and The Soul, Dr Rudy Rucker expanded upon Wolfram's theories toward a theory of Universal Automatism. This used cellular automata a model to explain how simple rules can generate complex results. Rudolf Rucker, Fall 2005. ...

Simplest

The simplest nontrivial CA would be one-dimensional, with two possible states per cell, and a cell's neighbors defined to be the adjacent cells on either side of it. A cell and its two neighbors form a neighborhood of 3 cells, so there are 2³=8 possible patterns for a neighborhood. There are then 2⁸=256 possible rules. These 256 CAs are generally referred to using Wolfram notation, a standard naming convention invented by Wolfram. The name of a CA is the decimal number which, in binary, gives the rule table, with the eight possible neighborhoods listed in reverse counting order. For example, below are tables defining the "rule 30 CA" and the "rule 110 CA" (in binary, 30 and 110 are written 11110 and 1101110, respectively) and graphical representations of them starting from a 1 in the center of each image: Wolfram code is a name often used for the method of enumerating elementary cellular automaton rules used by Stephen Wolfram in his book A New Kind of Science. ... The binary numeral system, or base-2 number system, is a numeral system that represents numeric values using two symbols, usually 0 and 1. ... Rule 30 is an elementary Cellular Automaton Rule. ... // The rule 110 cellular automaton is a one-dimensional two-state cellular automaton with the following rule table: Rule 110, like the Game of Life, exhibits what Stephen Wolfram calls Class 4 behavior, which is neither completely random nor completely repetitive. ...

A table completely defines a CA rule. For example, the rule 30 table says that if three adjacent cells in the CA currently have the pattern 100 (left cell is on, middle and right cells are off), then the middle cell will become 1 (on) on the next time step. The rule 110 CA says the opposite for that particular case.

A number of papers have analyzed and compared these 256 CAs. The rule 30 and rule 110 CAs are particularly interesting.

Rule 30 generates apparent randomness despite the lack of anything that could reasonably be considered random input. Wolfram proposed using its center column as a pseudorandom number generator (PRNG); it passes many standard tests for randomness, and Wolfram uses this rule in the Mathematica product for creating random integers. (In particular, in the 1990s a cryptography survey book claimed that rule 30 was equivalent to a linear feedback shift register (LFSR), but in fact the claim was about rule 90.) Although Rule 30 produces randomness on many input patterns, there are also an infinite number of input patterns that result in repeating patterns. The trivial example of such a pattern is the input pattern only consisting of zeros. A less trivial example, found by Matthew Cook, is any input pattern consisting of infinite repetitions of the pattern '00001000111000', with repetitions optionally being separated by six ones. A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers which are not truly random. ... The 1990s decade refers to the years from the start of 1990 to the end of 1999. ... A linear feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. ... Matthew Cook was born in Morgantown, West Virginia, in 1970 and grew up in Evanston, Illinois. ...

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, Cook proved in 1994 that these structures were rich enough to support universality. This result is interesting because rule 110 is an extremely simple one-dimensional system, and one which is 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 to be published before the publication of A New Kind of Science. In 2004, Cook's proof was finally published in Wolfram's journal Complex Systems (Vol. 15, No. 1), over ten years after Cook came up with it. A New Kind of Science is a controversial book by Stephen Wolfram, published in 2002. ... 1994 (MCMXCIV) was a common year starting on Saturday of the Gregorian calendar, and was designated as the International Year of the Family and the International Year of the Sport and the Olympic Ideal by United Nations. ... The Santa Fe Institute (or SFI) is a non-profit research institute dedicated to the study of complex systems in Santa Fe, New Mexico founded by George Cowan, David Pines, Stirling Colgate, Murray Gell-Mann, Nick Metropolis, Herb Anderson, Peter A. Carruthers, and Richard Slansky in 1984 to study complex... 1998 (MCMXCVIII) was a common year starting on Thursday of the Gregorian calendar, and was designated the International Year of the Ocean [1]. // Coated in ice, power and telephone lines sag and often break, resulting in power outages. ... 2004 (MMIV) was a leap year starting on Thursday of the Gregorian calendar. ...

Reversible

A CA is said to be reversible if for every current configuration of the CA there is exactly one past configuration (preimage). If one thinks of a CA as a function mapping configurations to configurations, reversibility implies that this function is bijective. In mathematics, the image of an element x in a set X under the function f : X → Y, denoted by f(x), is the unique y in Y that is associated with x. ... In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one_to_one and onto. ...

For one dimensional CA there are known algorithms for finding preimages, and any 1D rule can be proved either reversible or irreversible. For CA of two or more dimensions it has been proved that the reversibility is undecidable for arbitrary rules. The proof by Jarkko Kari is related to the tiling problem by Wang tiles. In mathematics, the image of an element x in a set X under the function f : X → Y, denoted by f(x), is the unique y in Y that is associated with x. ... Undecidable has more than one meaning: In mathematical logic: A decision problem is undecidable if there is no known algorithm that decides it. ... Jarkko J. Kari is a Finnish mathematician and computer scientist. ... Wang tiles (or Wang dominoes), first proposed by Hao Wang in 1961, are equal-sized squares with a color on each edge which give rise to a simple undecidable decision problem. ...

Reversible CA are often used to simulate such physical phenomena as gas and fluid dynamics, since they obey the laws of thermodynamics. Such CA have rules specially constructed to be reversible. Such systems have been studied by Tommaso Toffoli, Norman Margolus and others. Thermodynamics (from the Greek θερμη, therme, meaning heat and δυναμις, dunamis, meaning power) is a branch of physics that studies the effects of changes in temperature, pressure, and volume on physical systems at the macroscopic scale by analyzing the collective motion of their particles using statistics. ... Worked on the theory of artificial life, in such publications as his PhD thesis, and many other published articles. ...

For finite CAs that are not reversible, there must exist patterns for which there are no previous states. These patterns are called Garden of Eden patterns. In other words, no pattern exists which will develop into a Garden of Eden pattern. A Garden of Eden pattern, discovered by R. Banks in 1971, the first such pattern discovered in Conways Game of Life. ...

Several techniques can be used to explicitly construct reversible CA with known inverses. Two common ones are the second order technique and the partitioning technique, both of which involve modifying the definition of a CA in some way. Although such automata do not strictly satisfy the definition given above, it can be shown that they can be emulated by conventional CAs with sufficiently large neighborhoods and numbers of states, and can therefore be considered a subset of conventional CA. A second order cellular automaton is a reversible cellular automaton (CA) where the state of a cell at time t depends not only on its neighborhood at time t-1, but also on its state at time t-2. ... A block cellular automaton is a special kind of cellular automaton (CA) in which the lattice of cells is divided into non-overlapping blocks, and each block is evolved independently according to some rule that maps the states of the cells in the block at time t-1 to their...

Totalistic

A special class of CAs are totalistic CAs. The state of each cell in a totalistic CA is represented by a number (usually an integer value drawn from a finite set), and the value of a cell at time t depends only on the sum of the values of the cells in its neighborhood (possibly including the cell itself) at time t−1. If the state of the cell at time t does depend on its own state at time t−1 then the CA is properly called outer totalistic, although the distinction is not always made. Conway's Game of Life is an example of an outer totalistic CA with cell values 0 and 1. Gospers Glider Gun creating gliders. The Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. ...

A notation exists to describe rulesets of two-state totalistic CAs consisting of an initial indicating the neighbourhood of each cell and sums following the letters S (for survival) and B (for birth) for which those changes occur. In this notation Conway's Game of Life is M:S23/B3. This notation has been extended for non-totalistic CAs, where a letter or letters follow each sum indicating what patterns of neighbours cause survival or birth events.

Cryptography use

Rule 30 was originally suggested as a possible stream cipher for use in cryptography. The operation of A5/1, a LFSR-based stream cipher used to encrypt mobile phone conversations. ... The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write) is the study of message secrecy. ...

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 be able 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. Public key cryptography is a form of cryptography which generally allows users to communicate securely without having prior access to a shared secret key, by using a pair of cryptographic keys, designated as public key and private key, which are related mathematically. ... A one-way function is a function which is easy to calculate but hard to invert — it is difficult to calculate the input to the function given its output. ... A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse) without special information, called the trapdoor. Trapdoor functions are widely used in cryptography. ...

Related automata

There are many possible generalizations of the CA concept.

One way is by using something other than a rectangular (cubic, etc.) grid. For example, if a plane is tiled with equilateral triangles, those triangles could be used as cells. In geometry, a tiling (also called tessellation, mosaic or dissection) of a given shape S consists of a collection of other shapes which precisely cover S. Often the shape S to be tiled is the Euclidean plane, but other shapes and three-dimensional objects are considered as well. ...

Also, rules can be probabilistic rather than deterministic. 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.

The grid can be finite, so that patterns can "fall off" the edge of the universe.

In CA, 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 automata. These are like totalistic CA, 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 [0,1]). The state of a location is a finite number of real numbers. Certain CA can yield diffusion in liquid patterns in this way. A continuous automaton can be described as a cellular automaton whereby the valid states a cell can take are not discrete, but continuous, for example, [0,1]. Such automata can be used to model certain physical reactions more closely, such as diffusion. ... In mathematics, the unit interval is the interval [0,1], that is the set of all real numbers x such that zero is less than or equal to x and x is less than or equal to one. ...

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 zebras and spots on leopards. When these are approximated by CA, such CAs often yield similar patterns. MacLennan [1] considers continuous spatial automata as a model of computation. Continuous spatial automata, unlike cellular automata, have a continuum of locations. ... Reaction–diffusion systems are mathematical models that describe how the concentration of one or more substances change under the influence of two processes: chemical reactions in which the substances are converted into each other, and diffusion which causes the substances to spread out in space. ... Alan Mathison Turing, OBE (June 23, 1912 – June 7, 1954), was an English mathematician, logician, and cryptographer. ... Species Equus zebra Equus hartmannae Equus quagga Equus grevyi The Zebra is a part of the horse family, Equidae, native to central and southern Africa. ...

There are known examples of continuous spatial automata which exhibit propagating phenomena analogous to gliders in the Game of Life.

Natural biotic types

Conus textile exhibits a cellular automata pattern on its shell

Some living things use naturally occurring cellular automata in their functioning. ImageMetadata File history File links Download high resolution version (1600x1200, 423 KB) A Textile Cone Snail (Conus textile) Location: Cod Hole, Great Barrier Reef, Australia Date: 7 August 2005 Photographer: Richard Ling <richard@research. ... ImageMetadata File history File links Download high resolution version (1600x1200, 423 KB) A Textile Cone Snail (Conus textile) Location: Cod Hole, Great Barrier Reef, Australia Date: 7 August 2005 Photographer: Richard Ling <richard@research. ...

Patterns of some seashells, like the ones in Conus and Cymbiola genus, are generated by natural CA. The pigment cells reside in a narrow band along the shell's lip. Each cell secretes pigments according to the activating and inhibiting activity of its neighbour pigment cells, obeying a natural version of a mathematical rule.^{[citation needed]} 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 the Rule 30 CA described above. The hard, rigid outer calcium carbonate covering of certain animals is called a shell. ... Genera Asprella Chelyconus Conus Floraconus Leptoconus The cone snails or cone shells (family Conidae) are marine snails found in coral reefs. ... Natural Ultramarine pigment in powdered form. ... Secretion is the process of segregating, elaborating, and releasing chemicals from a cell, or a secreted chemical substance or amount of substance. ...

Plants regulate their intake and loss of gases via a CA mechanism. Each stoma on the leaf acts as a cell.
This is not about surgically created bowel openings; see stoma (medicine) In botany, a stoma (also stomate; plural stomata) is a tiny opening or pore, found mostly on the undersurface of a plant leaf, and used for gas exchange. ...

Chemical types

The Belousov-Zhabotinsky reaction is a spatio-temporal chemical oscillator which can be simulated by means of a cellular automaton. In the 1950s 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 Professor A. K. Dewdney presented a cellular automaton whose behavior closely resembles the Belousov-Zhabotinsky reaction. Whether the Belousov-Zhabotinsky reaction actually occurs as the result of a cellular automaton at the molecular level is not yet known. So far, no naturally occurring chemical cellular automata have been observed. All such reactions are done in laboratory settings. A Belousov-Zhabotinsky reaction, or BZ reaction, is one of a class of reactions that result in the establishment of a nonlinear chemical oscillator. ... This article does not cite its references or sources. ... Scientific American is a popular-science magazine, published (first weekly and later monthly) since August 28, 1845, making it the oldest continuously published magazine in the United States. ... Alexander Keewatin Dewdney (* August 5, 1941 in London, Ontario) is a Canadian mathematician, computer scientist, and philosopher who has written a number of books on the future and implications of modern computing. ...

Computer processors

CA processors are a physical, not software only, implementation 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 the small number of adjoining cells. Cells interact, communicate, directly only with adjoining, adjacent, neighbor cells. No means exists to communicate directly with cells farther away. 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 no wires are needed between any elements. Computer software (or simply software) refers to one or more computer programs and data held in the storage of a computer for some purpose. ... A tessellated plane seen in street pavement. ...

This is very unlike processors used in most computers today, von Neumann designs, which are divided into sections with elements that can communicate with distant elements, over wires.

Error Correction Coding

CA have been applied to design error correction codes in the paper "Design of CAECC - Cellular Automata Based Error Correcting Code", by D. Roy Chowdhury, S. Basu , I. Sen Gupta , P. Pal Chaudhuri. The paper defines a new scheme of building SEC-DED codes using CA, and also reports a fast hardware decoder for the code.

See also

Specific CA rules

• Conway's Game of Life
• Life-like cellular automata
• Cyclic cellular automaton
• Langton's ant
• Wireworld
• Rule 30
• Rule 110
• Cyclic Cellular Automaton

Gospers Glider Gun creating gliders. The Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. ... A cellular automaton is Life-like if it meets the following criteria: The CA has two dimensions. ... A one-dimensional cyclic cellular automaton with n = 4, run for 300 steps from a random initial configuration. ... Langtons ant is a two-dimensional Turing machine with a very simple set of rules, invented by Chris Langton. ... 2 Wireworld diodes, the above one in conduction direction, the lower one in reverse-biasing Wireworld is a well-known cellular automaton first proposed by Brian Silverman in 1987, as part of his program Phantom Fish Tank. ... Rule 30 is an elementary Cellular Automaton Rule. ... The rule 110 cellular automaton is a one-dimensional two-state cellular automaton with the following rule table: Rule 110, like the Game of Life, exhibits what Stephen Wolfram calls Class 4 behavior, which is neither completely random nor completely repetitive. ...

Self-replication in cellular automata

• Byl's loop
• Chou-Reggia loop
• Codd's cellular automaton
• Evoloop
• Langton's loops
• SDSR loop
• von Neumann's Universal constructor
• Asynchronous cellular automaton

The Chou-Reggia loop is an artificial lifeform similar in concept to Langtons loop. ... Codds Cellular Automaton is a cellular automaton devised by the British computer scientist Edgar F. Codd in 1968. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ... Lum de do day dea dea dea ... The SDSR (Structurally Dissolvable Self-Reproducing) loop is a variant of Langtons loops. ... The Nobili-Pesavento 29-state approximation of von Neumanns universal constructor, with a tape of instructions extending to the right. ... Cellular automata, as with other multi-agent system models, usually treat time as discrete and state updates as occurring synchronously. ...

Problems solved by cellular automata

• Majority problem
• Firing squad synchronization problem

The majority problem, first solved for many configurations by Gács, Kurdyumov, and Levin,[1] is the problem of finding one-dimensional cellular automaton rules that accurately perform majority voting. ... One solution to the FSSP using 15 states and 3n units of time. ...

Related topics

• A New Kind of Science
• Automata theory
• Excitable medium
• The Ooze
• Spatial Decision Support System - Mentions cellular automata based models of land use dynamics which allow urban and regional planners to test intervention strategies.

A New Kind of Science is a controversial book by Stephen Wolfram, published in 2002. ... In theoretical computer science, automata theory is the study of abstract machines and problems they are able to solve. ... An excitable medium is a nonlinear dynamical system which has the capacity to propagate a wave of some description, and which cannot support the passing of another wave until a certain amount of time has passed (known as the refractory time). ... This article or section does not cite its references or sources. ... Spatial Decision Support Systems (sDSS) developed in parallel with the concept of Decision Support Systems (DSS). ...

References

• "History of Cellular Automata" from Stephen Wolfram's A New Kind of Science
• Cellular automaton FAQ from the newsgroup comp.theory.cell-automata
• Neighbourhood survey includes discussion on triangular grids, and larger neighbourhood CAs.
• von Neumann, John, 1966, The Theory of Self-reproducing Automata, A. Burks, ed., Univ. of Illinois Press, Urbana, IL.
• Wolfram, Stephen, 1985, Cryptography with Cellular Automata, CRYPTO'85.
• Cosma Shalizi's Cellular Automata Notebook contains an extensive list of academic and professional reference material.
• Wolfram's papers on CAs
• A.M. Turing. 1952. The Chemical Basis of Morphogenesis. Phil. Trans. Royal Society, vol. B237, pp. 37 - 72. (proposes reaction-diffusion, a type of continuous automaton).
• Jim Giles. 2002. What kind of science is this? Nature 417, 216 - 218. (discusses the court order that suppressed publication of the rule 110 proof).
• Zuse´s publications on CA-based physics (1967, 1969, 1970), with comments by Juergen Schmidhuber
• Frish U., Hasslacher B., and Pommeau Y. Lattice gas method for partial differential equations. Phys. Rev. Lett., 56(1505), 1986.
• Peak, West, Messinger, Mott (2004) "Evidence for complex, collective dynamics and emergent, distributed computation in plants". Proceedings of the National Institute of Science of the USA 101 (4), 918-922

Stephen Wolfram (born August 29, 1959 in London) is a scientist known for his work in theoretical particle physics, cellular automata, complexity theory, and computer algebra, and is the creator of the computer program Mathematica. ... Jürgen Schmidhuber (born 1963 in Munich) is a computer scientist and artist known for his work on machine learning, universal Artificial Intelligence (AI), artificial neural networks, digital physics, and low-complexity art. ... There are very few or no other articles that link to this one. ...

External links

• Mirek's Cellebration - Home to free MCell and MJCell cellular automata explorer software and rule libraries. 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. MCell is a Windows application, while MJCell is a Java applet. Source code is available.
• Modern Cellular Automata - Easy to use interactive exhibits of live color 2D cellular automata, powered by Java applet. Included are exhibits of traditional, reversible, hexagonal, multiple step, fractal generating, and pattern generating rules. Thousands of rules are provided for viewing. Free software is available.
• Repeating Rule 30 patterns - A list of Rule 30 input patterns that produce repeating patterns.
• Self-replication loops in Cellular Space - Java applet powered exhibits of self replication loops.
• Web base CA generator - Experiment with creating image files containing pictures of 1D cellular automata. C++ source code is available.
• EvoCell is a platform for evolving cellular automatons - Released under the GPL
• Tiled CA - Windows software with source code for creating tiled CA.
• Triangular, pentagonal, and hexagonal CA - Java applet powered interactive exhibits.
• Free web-app to watch cellular automata grow in your browser - Build elementary 1D cellular automata.
• Prenzl!! Artistic Cellular Automata - Open source software to run and develop artistic cellular automata and other dynamical systems
• Open source Java code and application for multiple state CA on 2D lattice