nach oben

2010 | Buch

Game of Life Cellular Automata

herausgegeben von: Andrew Adamatzky

Verlag: Springer London

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

In the late 1960s British mathematician John Conway invented a virtual mathematical machine that operates on a two-dimensional array of square cell. Each cell takes two states, live and dead. The cells’ states are updated simultaneously and in discrete time. A dead cell comes to life if it has exactly three live neighbours. A live cell remains alive if two or three of its neighbours are alive, otherwise the cell dies. Conway’s Game of Life became the most programmed solitary game and the most known cellular automaton. The book brings together results of forty years of study into computational, mathematical, physical and engineering aspects of The Game of Life cellular automata. Selected topics include phenomenology and statistical behaviour; space-time dynamics on Penrose tilling and hyperbolic spaces; generation of music; algebraic properties; modelling of financial markets; semi-quantum extensions; predicting emergence; dual-graph based analysis; fuzzy, limit behaviour and threshold scaling; evolving cell-state transition rules; localization dynamics in quasi-chemical analogues of GoL; self-organisation towards criticality; asynochrous implementations. The volume is unique because it gives a comprehensive presentation of the theoretical and experimental foundations, cutting-edge computation techniques and mathematical analysis of the fabulously complex, self-organized and emergent phenomena defined by incredibly simple rules.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction to Cellular Automata and Conway’s Game of Life

Abstract

Although cellular automata has origins dating from the 1950s, widespread popular interest did not develop until John Conway’s “Game of Life” cellular automaton was initially revealed to the public in a 1970 Scientific American article (Gardner in Sci. Am. 223:120–123, 1970). The feature of his “game” that probably evoked this intensive interest was the discovery of “oscillators” (periodic forms) and “gliders” (translating oscillators). This introductory chapter is for those who are either unfamiliar with the game, or feel that a brief “refresher course” would be appropriate.

Carter Bays

Historical

Frontmatter

Chapter 2. Conway’s Game of Life: Early Personal Recollections

Abstract

When the October 1970 issue of Scientific American arrived, I had no idea the extent to which Martin Gardner’s article in that issue would affect my life. As long as I can remember, my custom would be to seek out the Mathematical Games column in search for Gardner’s latest topic with the usual reader challenges. My first reaction to that particular article introducing a new pastime titled “The fantastic combinations of John Conway’s new solitaire game ‘life''' was only mildly interesting. A couple of days later, still curious about the outcome of random patterns, I located an old checkerboard and a small jarful of pennies to investigate this new game.

Robert Wainwright

Chapter 3. Conway’s Life

Abstract

The rules of Conway’s Life, a two dimensional cellular automaton, are explained. Some of its characteristics and typical behavior are described. An algorithm to calculate periodic states using de Bruijn diagrams is explained. The paper is written in July 4, 1988.

Harold V. McIntosh

Chapter 4. Life’s Still Lifes

Abstract

The de Bruijn diagram describing those decompositions of the neighborhoods of a one dimensional cellular automaton which conform to predetermined requirements of periodicity and translational symmetry shows how to construct extended configurations satisfying the same requirements. Similar diagrams, formed by stages, describe higher dimensional automata, although they become more laborious to compute with increasing neighborhood size. The procedure is illustrated by computing some still lifes for Conway’s game of Life, a widely known two dimensional cellular automaton. This paper is written in September 10, 1988.

Harold V. McIntosh

Chapter 5. A Zoo of Life Forms

Abstract

A catalog is presented, of those Life forms on strips of widths up to nine whose translational behavior during a single generation can be inferred from two levels of de Bruijn diagrams. The paper is written in October 26, 1988; revised July 20, 1992.

Harold V. McIntosh

Classical topics

Chapter 6. Growth and Decay in Life-Like Cellular Automata

Abstract

Since the study of life began, many have asked: is it unique in the universe, or are there other interesting forms of life elsewhere? Before we can answer that question, we should ask others: What makes life special? If we happen across another system with life-like behavior, how would we be able to recognize it? We are speaking, of course, of the mathematical systems of cellular automata, of the fascinating patterns that have been discovered and engineered in Conway’s Game of Life, and of the possible existence of other cellular automaton rules with equally complex behavior to that of Life.

David Eppstein

Chapter 7. The B36/S125 “2x2” Life-Like Cellular Automaton

Abstract

The B36/S125 (or “2x2”) cellular automaton is one that takes place on a 2D square lattice much like Conway’s Game of Life. Although it exhibits high-level behaviour that is similar to Life, such as chaotic but eventually stable evolution and the existence of a natural diagonal glider, the individual objects that the rule contains generally look very different from their Life counterparts. In this article, a history of notable discoveries in the 2x2 rule is provided, and the fundamental patterns of the automaton are described. Some theoretical results are derived along the way, including a proof that the speed limits for diagonal and orthogonal spaceships in this rule are c/3 and c/2, respectively. A Margolus block cellular automaton that 2x2 emulates is investigated, and in particular a family of oscillators made up entirely of 2×2 blocks are analyzed and used to show that there exist oscillators with period 2^ℓ(2^k−1) for any integers k,ℓ≥1.

Nathaniel Johnston

Chapter 8. Object Synthesis in Conway’s Game of Life and Other Cellular Automata

Abstract

Of the very large number of cellular automata rules in existence, a relatively small number of rules may be considered interesting. Some of the features that make such rules interesting permit patterns to expand, contract, separate into multiple sub-patterns, or combine with other patterns. Such rules generally include still-lifes, oscillators, spaceships, spaceship guns, and puffer trains. Such structures can often be used to construct more complicated computational circuitry, and rules that contain them can often be shown to be computationally universal. Conway’s Game of Life is one rule that has been well-studied for several decades, and has been shown to be very fruitful in this regard.

Mark D. Niemiec

Chapter 9. Gliders and Glider Guns Discovery in Cellular Automata

Abstract

The theories of complexity are the understanding of how independent agents are interacting in a system to influence each other and the whole system. Surprising computational tasks could result from interactions of independent agents in complex systems as emergence of computation is a hot topic in the science of complexity. A promising environment to study emergent computation is cellular automata which are the simplest mathematical representation of complex systems. They are uniform frameworks in which the simple agents are cells evolving through time on the basis of a local function, called the transition rules.

Emmanuel Sapin

Chapter 10. Constraint Programming to Solve Maximal Density Still Life

Abstract

The Maximum Density Still Life problem fills a finite Game of Life board with a stable pattern of cells that has as many live cells as possible. Although simple to state, this problem is computationally challenging for any but the smallest sizes of board. Especially difficult is to prove that the maximum number of live cells has been found. Various approaches have been employed. The most successful are approaches based on Constraint Programming (CP). We describe the Maximum Density Still Life problem, introduce the concept of constraint programming, give an overview on how the problem can be modelled and solved with CP, and report on best-known results for the problem.

Geoffrey Chu, Karen Elizabeth Petrie, Neil Yorke-Smith

Asynchronous, Continuous and Memory-Enriched Automata

Chapter 11. Larger than Life’s Extremes: Rigorous Results for Simplified Rules and Speculation on the Phase Boundaries

Abstract

Larger than Life (LtL), is a four-parameter family of two-dimensional cellular automata that generalizes John Conway’s Game of Life (Life) to large neighborhoods and general birth and survival thresholds. LtL was proposed by David Griffeath in the early 1990s to explore whether Life might be a clue to a critical phase point in the threshold-range scaling limit. The LtL family of rules includes Life as well as a rich set of two-dimensional rules, some of which exhibit dynamics vastly different from Life. In this chapter we present rigorous results and conjectures about the ergodic classifications of several sets of “simplified” LtL rules, each of which has a property that makes the rule easier to analyze. For example, these include symmetric rules such as the threshold voter automaton and the anti-voter automaton, monotone rules such as the threshold growth models, and others. We also provide qualitative results and speculation about LtL rules on various phase boundaries and summarize results and open questions about our favorite “Life-like” LtL rules.

Kellie Michele Evans

Chapter 12. RealLife

Abstract

Let ℝ^D be D-dimensional Euclidean space, and let

https://static-content.springer.com/image/chp%3A10.1007%2F978-1-84996-217-9_12/192419_1_En_12_IEq1_HTML.gif

. A ‘Euclidean automaton’ is a shift-commuting transformation of

https://static-content.springer.com/image/chp%3A10.1007%2F978-1-84996-217-9_12/192419_1_En_12_IEq2_HTML.gif

determined by a local rule, analogous to a cellular automaton (CA). In her study of ‘Larger than Life’ (LtL) CA, Evans conjectured that, as their radius grows to infinity, LtL CA converge to a ‘continuum limit’ Euclidean automaton. We prove Evan’s conjecture, and name this family of Euclidean automata ‘RealLife’. We also show that the ‘life forms’ (fixed points, periodic orbits, and propagating structures) of LtL CA converge to life forms of RealLife. We next prove a number of existence results for fixed points of RealLife. Finally, we turn to a more qualitative discussion of the biology of the ‘bugs’ which seem ubiquitous in LtL and RealLife.

Marcus Pivato

Chapter 13. Variations on the Game of Life

Abstract

The Game of Life is defined in the framework of Cellular Automata with discrete states that are updated synchronously. Though this in itself has proven to be fertile ground for research, it leaves open questions regarding the robustness of the model with respect to variations in updating methods, cell state representations, neighborhood definitions, etc. These questions may become important when the ideal conditions under which the Game of Life is supposed to operate cannot be satisfied, like in physical realizations. This chapter describes three models in which Game of Life-like behavior is obtained, even though some basic tenets are violated.

Ferdinand Peper, Susumu Adachi, Jia Lee

Chapter 14. Does Life Resist Asynchrony?

Abstract

Undoubtedly, Conway’s Game of Life — or simply Life — is one of the most amazing inventions in the field of cellular automata. Forty years after its discovery, the model still fascinates researchers as if it were an inexhaustible source of puzzles. One of the most intriguing questions is to determine what makes this rule so particular among the quasi-infinite set of rules one can search. In this chapter we analyse how the Game of Life is affected by the presence of two structural pertubations: a change in the synchrony of the updates and a modification of the links between the cells.

Nazim Fatès

Chapter 15. LIFE with Short-Term Memory

Abstract

This chapter considers an extension to the standard framework of cellular automata in which, cells are endowed with memory of their previous state values. The effect of short-term memory, i.e., memory of only the latest states, in the (formally unaltered) Life rule is described in this work.

Ramón Alonso-Sanz

Chapter 16. Localization Dynamics in a Binary Two-Dimensional Cellular Automaton: The Diffusion Rule

Abstract

We study a two-dimensional cellular automaton (CA), called Diffusion Rule, which exhibits diffusion-like dynamics of propagating patterns. In computational experiments we discover a wide range of mobile and stationary localizations (gliders, oscillators, glider guns, puffer trains), analyze spatio-temporal dynamics of collisions between gliders, and discuss possible applications in unconventional computing.

Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh

Non-Orthogonal Lattices

Chapter 17. The Game of Life in Non-square Environments

Abstract

Here we explore the Game of Life (GoL) where it exists in other cellular automata (CA) “universes” of from one to four dimensions. We also look at various tessellations — triangular, pentagonal, hexagonal, and three dimensional “densely packed spheres”. For our exploration, we specifically define (and examine) only CA rules that conform to the definition of a GoL given in Chap. 1 — namely that for a given rule, (1) random configurations must stabilize, (2) at least one glider must exist under the rule and (3) all neighbors are treated the same. These rather intuitive restrictions will limit our survey to a reasonable number of interesting rules.

Carter Bays

Chapter 18. The Game of Life Rules on Penrose Tilings: Still Life and Oscillators

Abstract

John Horton Conway’s Game of Life is a simple two-dimensional, two state cellular automaton (CA), remarkable for its complex behaviour. That behaviour is known to be very sensitive to a change in the CA rules. Here we continue our investigations into its sensitivity to changes in the lattice, by the use of an aperiodic Penrose tiling lattice.

Nick Owens, Susan Stepney

Chapter 19. A Spherical XOR Gate Implemented in the Game of Life

Abstract

Are there uniquely spherical cellular automata machines? Might there be computational processes that come about more naturally on spheres than they would in the plane? This chapter describes an exploration of geodesic grids as environments for cellular automata (CA) and specifically addresses the movements of Game of Life (GoL) gliders whose interactions are affected by the positive curvature of spheres. 2D CA are typically arranged on regular planar grids with periodic boundary conditions — equivalent to the topology of a torus. This chapter instead considers the dynamics of CA on spheres. The unavoidable discontinuities that arise from mapping a 2D grid onto the sphere are accepted as integral components of the environment. A novel XOR gate built on GoL is demonstrated, utilizing the double-crossing of glider paths following geodesic great circles.

Jeffrey Ventrella

Complexity

Frontmatter

Chapter 20. Emergent Complexity in Conway’s Game of Life

Abstract

It is shown that both small, finite patterns and random infinite very low density (“sparse”) arrays of the Game of Life can produce emergent structures and processes of great complexity, through ramifying feedback networks and cross-scale interactions. The implications are discussed: it is proposed that analogous networks and interactions may have been precursors to natural selection in the real world.

Nick Gotts

Chapter 21. Macroscopic Spatial Complexity of the Game of Life Cellular Automaton: A Simple Data Analysis

Abstract

In this chapter we present a simple data analysis of an ensemble of 20 time series, generated by averaging the spatial positions of the living cells for each state of the Game of Life Cellular Automaton (GoL). We show that at the macroscopic level described by these time series, complexity properties of GoL are also presented and the following emergent properties, typical of data extracted complex systems such as financial or economical come out: variations of the generated time series following an asymptotic power law distribution, large fluctuations tending to be followed by large fluctuations, and small fluctuations tending to be followed by small ones, and fast decay of linear correlations, however, the correlations associated to their absolute variations exhibit a long range memory. Finally, a Detrended Fluctuation Analysis (DFA) of the generated time series, indicates that the GoL spatial macro states described by the time series are not either completely ordered or random, in a measurable and very interesting way.

A. R. Hernández-Montoya, H. F. Coronel-Brizio, M. E. Rodríguez-Achach

Physics

Frontmatter

Chapter 22. The Enlightened Game of Life

Abstract

The link between light and the development of complex behavior is as much subtle as evident. Examples include the moonlight triggered mass spawning of hard corals in the Great Barrier, or the light-switch hypothesis in evolutionary biology, which ascribes the Cambrian explosion to the development of vision.

Claudio Conti

Chapter 23. Towards a Quantum Game of Life

Abstract

Cellular automata provide a means of obtaining complex behaviour from a simple array of cells and a deterministic transition function. They supply a method of computation that dispenses with the need for manipulation of individual cells and they are computationally universal. Classical cellular automata have proved of great interest to computer scientists but the construction of quantum cellular automata pose particular difficulties. We present a version of John Conway’s famous two-dimensional classical cellular automata Life that has some quantum-like features, including interference effects. Some basic structures in the new automata are given and comparisons are made with Conway’s game.

Adrian P. Flitney, Derek Abbott

Music

Frontmatter

Chapter 24. Game of Life Music

Abstract

At the time when the first author was post-graduate student, in the evenings he used to entertain himself with the equipment in the electronic music studio at the University of York until dawn. It must have been around three o’clock in the morning of a rather cold winter night in the late 1980s, when he connected his Atari 1040ST computer to a synthesizer to test the first prototype of a system, which he was developing for his thesis. The system, named CAMUS (short for Cellular Automata Music), implemented a method that he invented to render music from the behaviour of the Game of Life (GoL) cellular automata (CA).

Eduardo R. Miranda, Alexis Kirke

Computation

Frontmatter

Chapter 25. Universal Computation and Construction in GoL Cellular Automata

Abstract

This chapter is concerned with the developments of universal computation and construction within Conway’s Game of Life (GoL). I will begin by describing the history of the concepts and mechanisms for universal computation and construction in GoL, before explaining how a Universal Computer–Constructor (UCC) would operate in this automaton. Moreover, I shall present the design of a working UCC in the rule. It is both capable of computing any calculation (i.e. it is Turing-complete) and constructing most, if not all, of the constructible configurations within the rule. It cannot construct patterns which have no predecessor; neither can any machine in the rule (for obvious reasons). As such, it is more accurately a general constructor, rather than a universal constructor.

Adam P. Goucher

Chapter 26. A Simple Universal Turing Machine for the Game of Life Turing Machine

Abstract

In this chapter we present a simple universal Turing machine which is small enough to fit into the design limits of the Turing machine build in Conway’s Game of Life by the author. That limit is 8 symbols and 16 states. By way of comparison we also describe one of the smallest known universal Turing machines due to Rogozhin which has 6 symbols and 4 states.

Paul Rendell

Chapter 27. Computation with Competing Patterns in Life-Like Automaton

Abstract

We study a Life-like cellular automaton rule B2/S2345 where a cell in state ‘0’ takes state ‘1’ if it has exactly two neighbors in state ‘1’ and the cell remains in the state ‘1’ if it has between two and five neighbors in state ‘1.’ This automaton is a discrete analog spatially extended chemical media, combining both properties of sub-excitable and precipitating chemical media. When started from random initial configuration B2/S2345 automaton exhibits chaotic behavior. Configurations with low density of state ‘1’ show emergence of localized propagating patterns and stationary localizations. We construct basic logical gates and elementary arithmetical circuits by simulating logical signals with mobile localizations reaction propagating geometrically restricted by stationary non-destructible localizations. Values of Boolean variables are encoded into two types of patterns — symmetric (False) and asymmetric (True) patterns — which compete for the ‘empty’ space when propagate in the channels. Implementations of logical gates and binary adders are illustrated explicitly.

Genaro J. Martínez, Andrew Adamatzky, Kenichi Morita, Maurice Margenstern

Backmatter

Titel: Game of Life Cellular Automata
herausgegeben von: Andrew Adamatzky
Verlag: Springer London
Electronic ISBN: 978-1-84996-217-9
Print ISBN: 978-1-84996-216-2
DOI: https://doi.org/10.1007/978-1-84996-217-9