Cellular Automata: Elementary Cellular Automata

Cellular Automata: Elementary Cellular Automata

Rupali Bhardwaj (School of Mathematics and Computer Applications, Thapar University, Patiala, India) and Anil Upadhyay (Department of Mathematics, Bipin Chandra Tripathi Kumaon Engineering College, Dwarahat, India)
Copyright: © 2017 |Pages: 9
DOI: 10.4018/JOEUC.2017010103


Cellular automata (CA) are discrete dynamical systems consist of a regular finite grid of cell; each cell encapsulating an equal portion of the state, and arranged spatially in a regular fashion to form an n-dimensional lattice. A cellular automata is like computers, data represented by initial configurations which is processed by time evolution to produce output. This paper is an empirical study of elementary cellular automata which includes concepts of rule equivalence, evolution of cellular automata and classification of cellular automata. In addition, explanation of behaviour of cellular automata is revealed through example.
Article Preview

1. Introduction

The term cellular automata is a discrete model studied in mathematics, physics, computability theory, complexity science and theoretical biology. Cellular automata consist of a regular finite grid of cell; each cell encapsulating an equal portion of the state, and arranged spatially in a regular fashion to form an n-dimensional lattice. For each cell, a set of cells called its neighbourhood (usually including the cell itself) is defined relative to the specified cell. An initial state (time t=0) is given by assigning a state for each cell; according to some fixed rule (generally, a mathematical function) next state is created (time t= t+1) 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 neighbourhood. For example, the rule might be that the cell is “on” in the next generation if and only if exactly one of the cells in the neighbourhood is “on” in the present generation otherwise the cell is “off” in the next generation. If same set of rules are used to update the stage of every cell in the lattice then cellular automata is called uniform otherwise it is called nonuniform cellular automata. A cellular automaton is a sextuple mathematical structure , whereas:

  • , where L is total number of cells, length of the cellular automaton.

  • S is the finite set of states alphabet, from which the generation of cell take their value,

  • is the evolution function of CA,

  • is the local rule where is the rule number,

  • is the size of neighbourhood defined by where r is radius.

  • is seed of the cellular automaton.

After a brief discussion of cellular automata, this paper will survey finite-width elementary cellular automata. Section 2 will explain construction of elementary cellular automata (ECA) and explain Wolfram's naming conventions for rules used in evolution of CA. Section 3 documents mirrored equivalence, inversion equivalence, and the combination of both. Section 4 will demonstrate how state transition diagrams assists the study of finite-width elementary CA. Section 5 concludes the paper.

2. Elementary Cellular Automata

In their most general form, cellular automata are dynamical systems and their behaviour is illustrated using “space-time diagrams” in which the configuration of states in the d-dimensional lattice is plotted as a function of time. This lattice evolves through time in harmony with some type of rule. Cell’s next state is determined using a particular rule by the state that precedes it in lattice.

Complete Article List

Search this Journal:
Open Access Articles
Volume 32: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 31: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 30: 4 Issues (2018)
Volume 29: 4 Issues (2017)
Volume 28: 4 Issues (2016)
Volume 27: 4 Issues (2015)
Volume 26: 4 Issues (2014)
Volume 25: 4 Issues (2013)
Volume 24: 4 Issues (2012)
Volume 23: 4 Issues (2011)
Volume 22: 4 Issues (2010)
Volume 21: 4 Issues (2009)
Volume 20: 4 Issues (2008)
Volume 19: 4 Issues (2007)
Volume 18: 4 Issues (2006)
Volume 17: 4 Issues (2005)
Volume 16: 4 Issues (2004)
Volume 15: 4 Issues (2003)
Volume 14: 4 Issues (2002)
Volume 13: 4 Issues (2001)
Volume 12: 4 Issues (2000)
Volume 11: 4 Issues (1999)
Volume 10: 4 Issues (1998)
Volume 9: 4 Issues (1997)
Volume 8: 4 Issues (1996)
Volume 7: 4 Issues (1995)
Volume 6: 4 Issues (1994)
Volume 5: 4 Issues (1993)
Volume 4: 4 Issues (1992)
Volume 3: 4 Issues (1991)
Volume 2: 4 Issues (1990)
Volume 1: 3 Issues (1989)
View Complete Journal Contents Listing