Cellular automaton - AbsoluteAstronomy.com

A cellular automaton
Automaton
An automaton is a self-operating machine. The word is sometimes used to describe a robot, more specifically an autonomous robot. An alternative spelling, now obsolete, is automation.-Etymology:...

(pl. cellular automata, abbrev. CA) is a discrete

Discrete mathematics

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...

model studied in computability theory

Computability theory (computer science)

Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science...

, mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, physics

Physics

Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...

, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states
State (computer science)
In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....

, such as "On" and "Off" (in contrast to a coupled map lattice

Coupled map lattice

A coupled map lattice is a dynamical system that models the behavior of non-linear systems . They are predominantly used to qualitatively study the chaotic dynamics of spatially extended systems. This includes the dynamics of chaos where the number of effective degrees of freedom diverge as the...

). The grid can be in any finite number of dimensions. For each cell, a set of cells called its neighborhood (usually including the cell itself) is defined relative to the specified cell. For example, the neighborhood of a cell might be defined as the set of cells a distance of 2 or less from the 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) 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. For example, the rule might be that the cell is "On" in the next generation if exactly two of the cells in the neighborhood are "On" in the current generation, otherwise the cell is "Off" in the next generation. 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, though exceptions are known.

Cellular automata are also called "cellular spaces", "tessellation automata", "homogeneous structures", "cellular structures", "tessellation structures", and "iterative arrays".

Overview

One way to simulate a two-dimensional cellular automaton is with an infinite sheet of graph paper

Graph paper

Graph paper, graphing paper, grid paper or millimeter paper is writing paper that is printed with fine lines making up a regular grid. The lines are often used as guides for plotting mathematical functions or experimental data and drawing diagrams. It is commonly found in mathematics and...

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 and white. The "neighbors" of a cell are the 8 squares touching it. For such a cell and its neighbors, there are 512 (= 2⁹) 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

Conway's Game of Life

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....

is a popular version of this model.

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.

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

Torus

In geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with the circle...

(doughnut shape). Universes of other dimensions

Dimensions

Dimensions is a French project that makes educational movies about mathematics, focusing on spatial geometry. It uses POV-Ray to render some of the animations, and the films are release under a Creative Commons licence....

are handled similarly. This is done in order to solve boundary problems with neighborhoods, but another advantage of this system is that it is easily programmable using modular arithmetic

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

functions. 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.

History

Stanisław Ulam, while working at the Los Alamos National Laboratory

Los Alamos National Laboratory

Los Alamos National Laboratory is a United States Department of Energy national laboratory, managed and operated by Los Alamos National Security , located in Los Alamos, New Mexico...

in the 1940s, studied the growth of crystals, using a simple lattice network

Lattice model (physics)

In physics, a lattice model is a physical model that is defined on a lattice, as opposed to the continuum of space or spacetime. Lattice models originally occurred in the context of condensed matter physics, where the atoms of a crystal automatically form a lattice. Currently, lattice models are...

as his model. At the same time, John von Neumann

John von Neumann

John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...

, 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

Crystal growth

A crystal is a solid material whose constituent atoms, molecules, or ions are arranged in an orderly repeating pattern extending in all three spatial dimensions. Crystal growth is a major stage of a crystallization process, and consists in the addition of new atoms, ions, or polymer strings into...

. Thus was born the first system of cellular automata. Like Ulam's lattice network, von Neumann's cellular automata

Von Neumann cellular automata

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 fellow mathematician Stanisław Ulam...

are two-dimensional, with his self-replicator implemented algorithmically. The result was a universal copier and constructor

Von Neumann universal constructor

John von Neumann's Universal Constructor is a self-replicating machine in a cellular automata environment. It was designed in the 1940s, without the use of a computer. The fundamental details of the machine were published in von Neumann's book Theory of Self-Reproducing Automata, completed in...

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. Von Neumann gave an existence proof that a particular pattern would make endless copies of itself within the given cellular universe. This design is known as the tessellation

Tessellation

A tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...

model, and is called a von Neumann universal constructor

Von Neumann universal constructor

.

Also in the 1940s, Norbert Wiener

Norbert Wiener

Norbert Wiener was an American mathematician.A famous child prodigy, Wiener later became an early researcher in stochastic and noise processes, contributing work relevant to electronic engineering, electronic communication, and control systems.Wiener is regarded as the originator of cybernetics, a...

and Arturo Rosenblueth

Arturo Rosenblueth

Arturo Rosenblueth Stearns was a Mexican researcher, physician and physiologist, who is known as one of the pioneers of cybernetics.- Biography:...

developed a cellular automaton model of excitable media. Their specific motivation was the mathematical description of impulse conduction in cardiac systems. Their original work continues to be cited in modern research publications on cardiac arrhythmia and excitable systems.

In the 1960s, cellular automata were studied as a particular type of dynamical system

Dynamical system

A dynamical system is a concept in mathematics where a fixed rule describes the time dependence of a point in a geometrical space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a...

and the connection with the mathematical field of symbolic dynamics

Symbolic dynamics

In mathematics, symbolic dynamics is the practice of modeling a topological or smooth dynamical system by a discrete space consisting of infinite sequences of abstract symbols, each of which corresponds to a state of the system, with the dynamics given by the shift operator...

was established for the first time. In 1969, Gustav A. Hedlund

Gustav A. Hedlund

Gustav Arnold Hedlund , an American mathematician, was one of the founders of symbolic and topological dynamics.-Biography:Hedlund was born May 7, 1904, in Somerville, Massachusetts. He did his undergraduate studies at Harvard University, earned a masters degree from Columbia University, and...

compiled many results following this point of view 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

Curtis–Hedlund–Lyndon theorem

The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A...

of the set of global rules of cellular automata as the set of continuous

Continuous function

In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...

endomorphisms of shift space

Shift space

In symbolic dynamics and related branches of mathematics, a shift space or subshift is a set of infinite words representing the evolution of a discrete system. In fact, shift spaces and symbolic dynamical systems are often considered synonyms....

s.

In the 1970s a two-state, two-dimensional cellular automaton named Game of Life

Conway's Game of Life

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....

became very widely known, particularly among the early computing community. Invented by John Conway

John Horton Conway

John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...

and popularized by Martin Gardner

Martin Gardner

Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...

in a Scientific American
Scientific American
Scientific American is a popular science magazine. It is notable for its long history of presenting science monthly to an educated but not necessarily scientific public, through its careful attention to the clarity of its text as well as the quality of its specially commissioned color graphics...

article, its rules are as follows: If a cell has 2 black neighbours, it stays the same. If it has 3 black neighbours, it becomes black. In all other situations it becomes white. Despite its simplicity, the system achieves an impressive diversity of behavior, fluctuating between apparent randomness

Randomness

Randomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....

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

Turing machine

A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...

. 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.

In 1969, however, German computer pioneer Konrad Zuse

Konrad Zuse

Konrad Zuse was a German civil engineer and computer pioneer. His greatest achievement was the world's first functional program-controlled Turing-complete computer, the Z3, which became operational in May 1941....

published his book Calculating Space
Calculating Space
Calculating Space is the title of MIT's English translation of Konrad Zuse's 1969 book Rechnender Raum , the first book on digital physics....

, 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 giant cellular automaton. This was the first book on what today is called digital physics

Digital physics

In physics and cosmology, digital physics is a collection of theoretical perspectives based on the premise that the universe is, at heart, describable by information, and is therefore computable...

.

In 1983 Stephen Wolfram

Stephen Wolfram

Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...

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
Elementary cellular automaton
In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors....

(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 later by Wolfram's research assistant Matthew Cook

Matthew Cook

Matthew Cook is a mathematician and computer scientist who proved Stephen Wolfram's conjecture that the Rule 110 cellular automaton is Turing-complete. Rule 110 is arguably the simplest Turing-complete system currently known....

in the 1990s.

In 2002 Wolfram published a 1280-page text A New Kind of Science, which extensively argues 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.

Elementary cellular automata

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. 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⁸=256 possible rules. These 256 CAs are generally referred to by their Wolfram code

Wolfram code

Wolfram code is a naming system often used for one-dimensional cellular automaton rules, introduced by Stephen Wolfram in a 1983 paper and used in his book A New Kind of Science....

, a standard naming convention invented by Stephen Wolfram

Stephen Wolfram

Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...

which gives each rule a number from 0 to 255. A number of papers have analyzed and compared these 256 CAs. The rule 30

Rule 30

Rule 30 is a one-dimensional binary cellular automaton rule introduced by Stephen Wolfram in 1983. Wolfram describes it as being his "all-time favourite rule" and details it in his book, A New Kind of Science...

and rule 110 CAs are particularly interesting. The images below show the history of each when the starting configuration consists of a 1 (at the top of each image) surrounded by 0's. Each row of pixels represents a generation in the history of the automation, with t=0 being the top row. Each pixel is colored white for 0 and black for 1.
Rule 30 exhibits class 3 behavior, meaning even simple input patterns such as that shown lead to chaotic, seemingly random histories.

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 Stephen Wolfram in 1994, Matthew Cook proved that some of these structures were rich enough to support universality

Universal Turing machine

In computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan...

. 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

Santa Fe Institute

The Santa Fe Institute is an independent, nonprofit theoretical research institute located in Santa Fe and dedicated to the multidisciplinary study of the fundamental principles of complex adaptive systems, including physical, computational, biological, and social systems.The Institute houses a...

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 announced 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. Rule 110 has been the basis over which some of the smallest universal Turing machines have been built, inspired on the breakthrough concepts that the development of the proof of rule 110 universality produced.

Reversible

A cellular automaton is said to be reversible if for every current configuration of the cellular automaton there is exactly one past configuration (preimage). If one thinks of a cellular automaton as a function mapping configurations to configurations, reversibility implies that this function is bijective. 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

Curtis–Hedlund–Lyndon theorem

The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A...

, a topological characterization of cellular automata. For cellular automata in which not every configuration has a preimage, the configurations without preimages are called Garden of Eden pattern
Garden of Eden pattern
In a cellular automaton, a Garden of Eden configuration is a configuration that cannot appear on the lattice after one time step, no matter what the initial configuration. In other words, these are the configurations with no predecessors....

s.

For one dimensional cellular automata there are known algorithms for deciding whether a rule is reversible or irreversible. However, for cellular automata of two or more dimensions reversibility is undecidable

Undecidable

Undecidable may refer to:In mathematics and logic* Undecidable problem - a decision problem which no algorithm can decide* "Undecidable" is sometimes used as a synonym of "independent", where a formula in mathematical logic is independent of a logical theory if neither that formula nor its negation...

; 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

Jarkko Kari

Jarkko J. Kari is a Finnish mathematician and computer scientist, known for his contributions to the theory of Wang tiles and cellular automata. Kari is currently a professor at the Department of Mathematics, University of Turku.-Biography:...

is related to the tiling problem by Wang tile

Wang tile

Wang tiles , first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems...

s.

Reversible CA are often used to simulate such physical phenomena as gas and fluid dynamics, since they obey the laws of thermodynamics

Thermodynamics

Thermodynamics is a physical science that studies the effects on material bodies, and on radiation in regions of space, of transfer of heat and of work done on or by the bodies or radiation...

. Such CA have rules specially constructed to be reversible. Such systems have been studied by Tommaso Toffoli

Tommaso Toffoli

Tommaso Toffoli is a professor of electrical and computer engineering at Boston University. He joined the faculty in 1995. He was born in June, 1943 in Montereale Valcellina, in northeastern Italy, and was raised in Rome. He received his doctorate in physics from the University of Rome La...

, Norman Margolus

Norman Margolus

Norman H. Margolus is an Canadian-American physicist and computer scientist, known for his work on cellular automata and reversible computing...

and others. Several techniques can be used to explicitly construct reversible CA with known inverses. Two common ones are the second order cellular automaton

Second order cellular automaton

A second-order cellular automaton is a type of reversible cellular automaton invented by Edward Fredkin where the state of a cell at time depends not only on its neighborhood at time , but also on its state at time...

and the block cellular automaton

Block cellular automaton

A block cellular automaton or partitioning cellular automaton is a special kind of cellular automaton in which the lattice of cells is divided into non-overlapping blocks and the transition rule is applied to a whole block at a time rather than a single cell...

, 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. Conversely, it has been shown that every reversible cellular automaton can be emulated by a block cellular automaton.

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. Conway's Game of Life

Conway's Game of Life

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....

is an example of an outer totalistic CA with cell values 0 and 1; outer totalistic cellular automata with the same Moore neighborhood

Moore neighborhood

In cellular automata, the Moore neighborhood comprises the eight cells surrounding a central cell on a two-dimensional square lattice. The neighborhood is named after Edward F. Moore, a pioneer of cellular automata theory. It is one of the two most commonly used neighborhood types, the other one...

structure as Life are sometimes called life-like cellular automata

Life-like cellular automaton

A cellular automaton is Life-like if it meets the following criteria:* The array of cells of the automaton has two dimensions....

Classification

Stephen Wolfram

Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...

, in A New Kind of Science
A New Kind of Science
A New Kind of Science is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata...

and in 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 type 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.
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.
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.
Class 4: Nearly all initial patterns evolve into structures that interact in complex and interesting ways. 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 conjectured that many, if not all class 4 cellular automata are capable of 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." Wolfram's classification has been empirically matched to a clustering of the compressed lengths of the outputs of cellular automata.

There have been several attempts to classify CA in formally rigorous classes, inspired by the 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 to be undecidable

Undecidable problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....

Evolving cellular automata using genetic algorithms

Recently there has been a keen interest in building decentralized systems, be they sensor networks or more sophisticated micro level structures designed at the network level and aimed at decentralized information processing. The idea of emergent computation came from the need of using distributed systems to do information processing at the global level. The area is still in its infancy, but some people have started taking the idea seriously. Melanie Mitchell

Melanie Mitchell

Melanie Mitchell is a professor of computer science at Portland State University. She has worked at the Santa Fe Institute and Los Alamos National Laboratory...

who is Professor of Computer Science at Portland State University

Portland State University

Portland State University is a public state urban university located in downtown Portland, Oregon, United States. Founded in 1946, it has the largest overall enrollment of any university in the state of Oregon, including undergraduate and graduate students. It is also the only public university in...

and also Santa Fe Institute

Santa Fe Institute

External Professor has been working on the idea of using self-evolving cellular arrays to study emergent computation and distributed information processing. Mitchell and colleagues are using evolutionary computation to program cellular arrays. Computation in decentralized systems is very different from classical systems, where the information is processed at some central location depending on the system’s state. In decentralized system, the information processing occurs in the form of global and local pattern dynamics.

The inspiration for this approach comes from complex natural systems like insect colonies, nervous system

Nervous system

The nervous system is an organ system containing a network of specialized cells called neurons that coordinate the actions of an animal and transmit signals between different parts of its body. In most animals the nervous system consists of two parts, central and peripheral. The central nervous...

and economic systems. The focus of the research is to understand how computation occurs in an evolving decentralized system. In order to model some of the features of these systems and study how they give rise to emergent computation, Mitchell and collaborators at the SFI have applied Genetic Algorithms to evolve patterns in cellular automata. They have been able to show that the GA discovered rules that gave rise to sophisticated emergent computational strategies. Mitchell’s group used a single dimensional binary array where each cell has six neighbors. The array can be thought of as a circle where the first and last cells are neighbors. The evolution of the array was tracked through the number of ones and zeros after each iteration. The results were plotted to show clearly how the network evolved and what sort of emergent computation was visible.

The results produced by Mitchell’s group are interesting, in that a very simple array of cellular automata produced results showing coordination over global scale, fitting the idea of emergent computation. Future work in the area may include more sophisticated models using cellular automata of higher dimensions, which can be used to model complex natural systems.

Cryptography use

Rule 30

was originally suggested as a possible Block cipher

Block cipher

In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...

for use in cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

(See CA-1.1).

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

Trapdoor function

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 without special information, called the "trapdoor"...

, and can be used as a public-key cryptosystem. The security of such systems is not currently known.

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 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.

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
Continuous automaton
A continuous automaton can be described as a cellular automaton extended so the valid states a cell can take are not just discrete , but continuous, for example, the real number range [0,1]. The cells however remain discretely separated from each other. One example is called computational verb...

. 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

Unit interval

In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1...

]). The state of a location is a finite number of real numbers. Certain CA 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

Alan Turing

Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...

to explain how chemical reactions could create the stripes on zebra

Zebra

Zebras are several species of African equids united by their distinctive black and white stripes. Their stripes come in different patterns unique to each individual. They are generally social animals that live in small harems to large herds...

s and spots on leopards. When these are approximated by CA, such CAs 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.

Biology

Some biological processes occur—or can be simulated—by cellular automata.

Patterns of some seashell

Seashell

A seashell or sea shell, also known simply as a shell, is a hard, protective outer layer created by an animal that lives in the sea. The shell is part of the body of the animal. Empty seashells are often found washed up on beaches by beachcombers...

s, like the ones in Conus
Cone snail
Conidae is a taxonomic family of minute to quite large sea snails, marine gastropod molluscs in the superfamily Conoidea.The snails within this family are sophisticated predatory animals...

and Cymbiola
Cymbiola
Cymbiola is a genus of large predatory sea snail, a marine gastropod mollusk in the family Volutidae, the volutes. Some of the species within this genus are sometimes placed in the genus Cymbiolacca Iredale, 1929, which is also sometimes treated as a subgenus of Cymbiola.-Species:Species and...

genus, are generated by natural CA. The pigment

Pigment

A pigment is a material that changes the color of reflected or transmitted light as the result of wavelength-selective absorption. This physical process differs from fluorescence, phosphorescence, and other forms of luminescence, in which a material emits light.Many materials selectively absorb...

cells reside in a narrow band along the shell's lip. Each cell secretes

Secretion

Secretion is the process of elaborating, releasing, and oozing chemicals, or a secreted chemical substance from a cell or gland. In contrast to excretion, the substance may have a certain function, rather than being a waste product...

pigments according to the activating and inhibiting activity of its neighbour pigment cells, obeying a natural version of a mathematical rule. The cell band leaves the colored pattern on the shell as it grows slowly. For example, the widespread species Conus textile
Conus textile
Conus textile, common name the cloth of gold cone is a venomous species of sea snail, a marine gastropod mollusk in the family Conidae, the cone snails, cone shells or cones. The species is extremely dangerous to humans.-Distribution:C...

bears a pattern resembling Wolfram's rule 30

Rule 30

CA.

Plants regulate their intake and loss of gases via a CA mechanism. Each stoma on the leaf acts as a cell.

Moving wave patterns on the skin of cephalopod

Cephalopod

A cephalopod is any member of the molluscan class Cephalopoda . These exclusively marine animals are characterized by bilateral body symmetry, a prominent head, and a set of arms or tentacles modified from the primitive molluscan foot...

s can be simulated with a two-state, two-dimensional cellular automata, each state corresponding to either an expanded or retracted chromatophore

Chromatophore

Chromatophores are pigment-containing and light-reflecting cells found in amphibians, fish, reptiles, crustaceans, and cephalopods. They are largely responsible for generating skin and eye colour in cold-blooded animals and are generated in the neural crest during embryonic development...

.

Threshold automata have been invented to simulate neuron

Neuron

A neuron is an electrically excitable cell that processes and transmits information by electrical and chemical signaling. Chemical signaling occurs via synapses, specialized connections with other cells. Neurons connect to each other to form networks. Neurons are the core components of the nervous...

s, and complex behaviors such as recognition and learning can be simulated.

Fibroblast

Fibroblast

A fibroblast is a type of cell that synthesizes the extracellular matrix and collagen, the structural framework for animal tissues, and plays a critical role in wound healing...

s bear similarities to cellular automata, as each fibroblast only interacts with its neighbors.

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

Malonic acid

Malonic acid is a dicarboxylic acid with structure CH22. The ionised form of malonic acid, as well as its esters and salts, are known as malonates. For example, diethyl malonate is malonic acid's ethyl ester...

, 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
Scientific American
Scientific American is a popular science magazine. It is notable for its long history of presenting science monthly to an educated but not necessarily scientific public, through its careful attention to the clarity of its text as well as the quality of its specially commissioned color graphics...

, A. K. Dewdney discussed a cellular automaton which was developed by Martin Gerhardt and Heike Schuster of the University of Bielefeld (West Germany). This automaton produces wave patterns resembling those in the Belousov-Zhabotinsky reaction.

Computer processors

CA processors are physical (not computer simulated) 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

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.

One such CA processor array configuration is the systolic array

Systolic array

In computer architecture, a systolic array is a pipe network arrangement of processing units called cells. It is a specialized form of parallel computing, where cells , compute data and store it independently of each other.thumb|240px...

.

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.

This is very unlike processors used in most computers today, von Neumann designs

Von Neumann architecture

The term Von Neumann architecture, aka the Von Neumann model, derives from a computer architecture proposal by the mathematician and early computer scientist John von Neumann and others, dated June 30, 1945, entitled First Draft of a Report on the EDVAC...

, 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.

CA as models of the fundamental physical reality

As Andrew Ilachinski points out in his Cellular Automata, many scholars have raised the question of whether the universe is a cellular automaton. Ilachinsky argues that the importance of this question may be better appreciated with a simple observation, which can be stated as follows. Consider the evolution of rule 110: if it were some kind of "alien physics", what would be a reasonable description of the observed patterns? If you didn't know how the images were generated, you might end up conjecturing about the movement of some particle-like objects (indeed, physicist James Crutchfield made a rigorous mathematical theory out of this idea proving the statistical emergence of "particles" from CA). Then, as the argument goes, one might wonder if our world, which is currently well described by physics with particle-like objects

Particle physics

Particle physics is a branch of physics that studies the existence and interactions of particles that are the constituents of what is usually referred to as matter or radiation. In current understanding, particles are excitations of quantum fields and interact following their dynamics...

, could be a CA at its most fundamental level.

While a complete theory along this line is still to be developed, entertaining and developing this hypothesis led scholars to interesting speculation and fruitful intuitions on how can we make sense of our world within a discrete framework. Marvin Minsky

Marvin Minsky

Marvin Lee Minsky is an American cognitive scientist in the field of artificial intelligence , co-founder of Massachusetts Institute of Technology's AI laboratory, and author of several texts on AI and philosophy.-Biography:...

, the AI pioneer, investigated how to understand particle interaction with a four-dimensional CA lattice; Konrad Zuse

Konrad Zuse

—the inventor of the first working computer, the Z3—developed an irregularly organized lattice to address the question of the information content of particles. More recently, Edward Fredkin

Edward Fredkin

Edward Fredkin is an early pioneer of digital physics. In recent work, he uses the term digital philosophy . His primary contributions include his work on reversible computing and cellular automata...

exposed what he terms the "finite nature hypothesis", i.e., the idea that "ultimately every quantity of physics, including space and time, will turn out to be discrete and finite." Fredkin and Stephen Wolfram

Stephen Wolfram

Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...

are strong proponents of a CA-based physics.

In recent years, other suggestions along these lines have emerged from literature in non-standard computation. Stephen Wolfram's A New Kind of Science
A New Kind of Science
A New Kind of Science is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata...

considers CA to be the key to understanding a variety of subjects, physics included. The Mathematics Of the Models of Reference—created by iLabs founder Gabriele Rossi and developed with Francesco Berto and Jacopo Tagliabue—features an original 2D/3D universe based on a new "rhombic dodecahedron-based" lattice and a unique rule. This model satisfies universality (it is equivalent to a Turing Machine) and perfect reversibility (a desideratum if one wants to conserve various quantities easily and never lose information), and it comes embedded in a first-order theory, allowing computable, qualitative statements on the universe evolution.

In popular culture

One-dimensional cellular automata were mentioned in the Season 2 episode of NUMB3RS
NUMB3RS
Numb3rs is an American television drama which premiered on CBS on January 23, 2005, and concluded on March 12, 2010. The series was created by Nicolas Falacci and Cheryl Heuton, and follows FBI Special Agent Don Eppes and his mathematical genius brother, Charlie Eppes , who helps Don solve crimes...

"Better or Worse".
The Hacker Emblem
Hacker Emblem
The Hacker Emblem was first proposed in October 2003 by Eric S. Raymond, who claimed a need for a unifying and recognizable symbol for his perception of hacker culture...

, a symbol for hacker culture proposed by Eric S. Raymond
Eric S. Raymond
Eric Steven Raymond , often referred to as ESR, is an American computer programmer, author and open source software advocate. After the 1997 publication of The Cathedral and the Bazaar, Raymond was for a number of years frequently quoted as an unofficial spokesman for the open source movement...

, depicts a glider
Glider (Conway's Life)
The glider is a pattern that travels across the board in Conway's Game of Life. It was first discovered by Richard K. Guy in 1970, while John Conway's group was attempting to track the evolution of the R-pentomino. Gliders are the smallest spaceships, and they travel diagonally at a speed of c/4...

from Conway's Game of Life
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....

.
The Autoverse, an artificial life
Artificial life
Artificial life is a field of study and an associated art form which examine systems related to life, its processes, and its evolution through simulations using computer models, robotics, and biochemistry. The discipline was named by Christopher Langton, an American computer scientist, in 1986...

simulator in the novel Permutation City
Permutation City
Permutation City is a 1994 science fiction novel by Greg Egan that explores many concepts, including quantum ontology, via various philosophical aspects of artificial life and simulated reality. Sections of the story were adapted from Egan's 1992 short story "Dust" which dealt with many of the same...

, is a cellular automaton.
Cellular automata are discussed in the novel Bloom
Bloom (novel)
Bloom, written in 1998, is the fifth science fiction novel written by Wil McCarthy. It was first released as a hardcover in September 1998...

.
Cellular automata are central to Robert J. Sawyer
Robert J. Sawyer
Robert James Sawyer is a Canadian science fiction writer. He has had 20 novels published, and his short fiction has appeared in Analog Science Fiction and Fact, Amazing Stories, On Spec, Nature, and many anthologies. Sawyer has won over forty awards for his fiction, including the Nebula Award ,...

's trilogy WWW
Wake (Robert J. Sawyer novel)
Wake, also called WWW: Wake, is a 2009 novel written by Canadian novelist Robert J. Sawyer. It is the first installment in the WWW Trilogy and was followed by two sequels, Watch and Wonder . An audio book was released on 7 April 2009....

in an attempt to explain how Webmind spontaneously attained consciousness.

Self-replication in cellular automata

Codd's cellular automaton
Codd's cellular automaton
Codd's cellular automaton is a cellular automaton devised by the British computer scientist Edgar F. Codd in 1968. It was designed to recreate the computation- and construction-universality of von Neumann's CA but with fewer states: 8 instead of 29...
Langton's loops
Langton's loops
Langton's loops are a particular "species" of artificial life in a cellular automaton created in 1984 by Christopher Langton. They consist of a loop of cells containing genetic information, which flows continuously around the loop and out along an "arm" , which will become the daughter loop...
Von Neumann universal constructor
Von Neumann universal constructor
John von Neumann's Universal Constructor is a self-replicating machine in a cellular automata environment. It was designed in the 1940s, without the use of a computer. The fundamental details of the machine were published in von Neumann's book Theory of Self-Reproducing Automata, completed in...

Problems solved by cellular automata

Firing squad synchronization problem
Firing squad synchronization problem
The firing squad synchronization problem is a problem in computer science and cellular automata in which the goal is to design a cellular automaton that, starting with a single active cell, eventually reaches a state in which all cells are simultaneously active...
Majority problem
Majority problem (cellular automaton)
The majority problem, or density classification task is the problem of finding one-dimensional cellular automaton rules that accurately perform majority voting.Using local transition rules, cells cannot know the total count of all the ones in system...

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.
Self-replication loops in Cellular Space – Java applet powered exhibits of self replication loops.
A collection of over 10 different cellular automata applets (in Monash University's Virtual Lab)
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 which can demonstrate von Neumann type self-replication.
Wolfram Atlas – An atlas of various types of one-dimensional cellular automata.
Conway Life
First replicating creature spawned in life simulator
The Mathematics of the Models of Reference, featuring a general tutorial on CA, interactive applet, free code and resources on CA as model of fundamental physics

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Overview

History

Elementary cellular automata

Reversible

Totalistic

Classification

Evolving cellular automata using genetic algorithms

Cryptography use

Related automata

Biology

Chemical types

Computer processors

Error correction coding

CA as models of the fundamental physical reality

In popular culture

Self-replication in cellular automata

Problems solved by cellular automata

Related topics

External links