Response Curves for Cellular Automata in One and Two Dimensions: An Example of Rigorous Calculations

Response Curves for Cellular Automata in One and Two Dimensions: An Example of Rigorous Calculations

Henryk Fuks (Brock University, Canada) and Andrew Skelton (Brock University, Canada)
Copyright: © 2010 |Pages: 15
DOI: 10.4018/jncr.2010070106
OnDemand PDF Download:
No Current Special Offers


In this paper, the authors consider the problem of computing a response curve for binary cellular automata, that is, the curve describing the dependence of the density of ones after many iterations of the rule on the initial density of ones. The authors demonstrate how this problem could be approached using rule 130 as an example. For this rule, preimage sets of finite strings exhibit recognizable patterns; therefore, it is possible to compute both cardinalities of preimages of certain finite strings and probabilities of occurrence of these strings in a configuration obtained by iterating a random initial configuration n times. Response curves can be rigorously calculated in both one- and two-dimensional versions of CA rule 130. The authors also discuss a special case of totally disordered initial configurations, that is, random configurations where the density of ones and zeros are equal to 1/2.
Article Preview

Basic Definitions

Let jncr.2010070106.m06 be called a symbol set, and let jncr.2010070106.m07 be the set of all bisequences over jncr.2010070106.m08, where by a bisequence we mean a function on jncr.2010070106.m09 to jncr.2010070106.m10. Throughout the remainder of this text the configuration space jncr.2010070106.m11 will be simply denoted by jncr.2010070106.m12.

A block of lengthjncr.2010070106.m13 is an ordered set jncr.2010070106.m14, where jncr.2010070106.m15, jncr.2010070106.m16. Let jncr.2010070106.m17 and let jncr.2010070106.m18 denote the set of all blocks of length jncr.2010070106.m19 over jncr.2010070106.m20 and jncr.2010070106.m21 be the set of all finite blocks over jncr.2010070106.m22.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2022): Forthcoming, Available for Pre-Order
Volume 10: 4 Issues (2021): 3 Released, 1 Forthcoming
Volume 9: 4 Issues (2020)
Volume 8: 4 Issues (2019)
Volume 7: 4 Issues (2018)
Volume 6: 2 Issues (2017)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing