大分工業高等専門学校紀要第43号(平成18年11月)

ON BEHAVIORS OF CELLULAR AUTOMATA WITH RULE 58
UNDER THE BOUNDARY CONDITION 0-1

Tatsuro SATO
Dept. of General Education

In this paper, we treat the behaviors of 1-dimensional finite cellular automata with a triplet local
transition rule 58 having the fixed boundary condition 0-1. The behaviors of CA-58(n) were observed bycomputer experiments, and some formulae on the limit cycle and the transient length were found out. The
purpose of this paper is to give theoretical proofs to above formulae.
Key Words : cellular automata, limit cycle, transient length, boundary condition

1.

INTRODUCTION

Cellular automata were initially introduced by J.
von Neumann as theoretical models to demonstratea system capable of self-reproducing organisms anduniversal computation in 1950s1). From 1980s
downward, cellular automata have been realizedagain as a theoretical model of complex system byS.Wolfram and the other physicists. And many
researchers have investigated and applied them.
Cellular automata have very simple structure. Whilecellular automata obey simple transition rules, theirbehaviors are very complicated. The complication iscaused by interaction between cells and is similar tobehaviors of complex systems as fractal and chaotic
phenomena. The importance of cellular automata
seems to increase in the fields of mathematics,
physics, biology, computer science, economics andso on.
Various cellular automata have been analyzed
concerning one dimensional and two dimensional
cellular automata, cellular automata with a cyclic
cell array or a linear cell array and so on. Wolfram
classified 1-dimensional cellular automata into four
complex classes according to patterns generated by
the synchronous dynamics, a homogeneous state, a
set of separated simple stable or periodic structures,a chaotic pattern and complex localized structures
which are sometimes long-lived2),3).
Investigating behaviors of cellular automata, we
think that the transient length and the period lengthof limit cycle are important concepts. Cellularautomata having limit cycles of period length 1 or 2
were investigated by Inokuchi et al.4). So first, weaimed at cellular automata having limit cycles ofperiod length 35),6),7),8),9),10),11). By computer
experiments, we observed that there were sevencellular automata having limit cycles of period
length 3 except cellular automata with threshold
rules, 24, 27, 46, 57, 58, 130 and 152. And weinvestigated their transient length and period lengthof limit cycle. Secondly, we investigated cellular
automata with threshold rules. There are 38
threshold rules except for symmetric, reverse andsymmetric reverse rules, 0, 1, 2, 3, 4, 5, 7, 8, 10, 11,12, 13, 14, 15, 19, 23, 32, 34, 35, 42, 43, 50, 51, 76,77, 128, 136, 138, 140, 142, 160, 162, 168, 170,178, 200, 204 and 232. And we reproved that
their period lengths of limit cycles are 4 or less andwe proved that their transient lengths are 3 ×(cell-size)-4 or less12),13).

2. PRELIMINARIESIn this section, we define 1-dimensional finite
cellular automata and introduce notations used inthis paper.
Cellular automata treated in this paper havelinearly ordered and finite number cells bearing withstates 0 or 1. The next state of any cell depends on
the states of the left cell, the cell itself and the rightcell. In this section, we will formally define cellular
automata CA-R(n) with rule number R of triplet
local transition rule f and n cell array.
Let Q be a state set {0, 1} and n a positiveinteger. The complement of a state a ∈ Q will bedenoted by a-, that is a-=1-a. The n-th cartesian
product of Q is denoted Qn in other words, Qn is the- 41 -大分工業高等専門学校紀要

第 43 号(平成 18 年 11 月)

set of all n-tuples consisting of 0 and 1. For
example,Q3={000, 001, 010, 011, 100, 101,110, 111}.
DEFINITION 2.1
The triplet local transition rule is a function f :Q3 → Q, and the rule number R of f is defined by
R=2 4 a + 2b+c f (abc) .

∑a ,b ,c∈Q

is denoted by a fixed point. And a number of a limit
cycle of period length T is denoted by γ T (n) .
DEFINITION 2.5
h(x) is defined as follows ;h(x)=min{s ≥ 0| δ s(x) is on a limit cycle}.
Then the transient length H(n) of CA − Rα − β (n) isdefined as H(n)=max{h(x)|x ∈ Qn}.

Usually the triplet local transition rule of rulenumber R is denoted by rule R for short.
DEFINITION 2.2
Let I={1, 2, ･･･ , n} be a set of cells. We calln-dimensional vector space Qn a configuration
space. And a configuration is a vector x=(x1,x2, ･･･, xn) ∈ Qn.
The positive integer n is called cell-size. Usually avector (x1, x2, ･･･, xn) denotes x1 x2･･･xn for short.
DEFINITION 2.3
The global transition function δ is defined asfollows;δ (x1 x2･･･xn)=(f( α x1 x2)f(x1 x2 x3)･･･f(xn-1 xn β ))where f is rule R and α , β ∈ Q.
We call a pair ( α , β ) a boundary. We say that theboundary condition is cyclic if and only if α = xnand β = x1, and the boundary condition is fixed ifand only if α and β are fixed. We say that theboundary condition is a-b if α =a and β =b.

CA − Rα − β (n) denotes an one-dimensional cellular
automata such that n cells exist and its transition
rule R and its boundary condition is α - β .
DEFINITION 2.4
Let x be a configuration of CA − Rα − β (n) . The
configuration x is on a limit cycle of period length T
if there exists a positive integer s such that δ s(x)=x,and T=min{s ≥ 1| δ s(x)=x}. And the configurations
x(1), x(2), ･･･, x(T-1) form a limit cycle of period
length T if x(i+1)= δ (x(i)) and x(T)=x(1), and x(i)is on a limit cycle of period length T where1 ≤ i ≤ T-1.
A limit cycle of period length T is denoted by aT-cycle, in particular, a limit cycle of period length 1

DEFINITION 2.6
The symmetric transition rule f # : Q3 → Q of a local
transition rule f is defined as follows;f # (abc)=f (cba)
for all triples abc ∈ Q3.
DEFINITION 2.7
The reverse transition rule f ° : Q3 → Q of a local
transition rule f is defined as follows ;f ° (abc)=[f (a-b-c-)]-=1-f (1-a, 1-b, 1-c)
for all triples abc ∈ Q3.
Let rule R ° and rule R# be the reverse and symmetricrule of rule R respectively. It is trivial that f ##=f andR#=R+56(r3-r6)+14(r1-r4) and f ° ° =f, f # ° =f ° #and R ° =255-(128 r0+64r1+32 r2+16 r3+8 r4+4 r5+2r6+ r7) where r4a+2b+c=f(abc) for all triples abc ∈ Q3.
Then, we can identify CA − R °α − − β − (n) andCA − R # β −α (n) with CA − Rα − β (n) . So,

CA − Rα −β (n) , CA − R °α − − β − (n) , CA − R # β −α (n)#and CA − R ° β − −α − (n) can be identified with eachother.
Considering the reverse rule, the symmetric rule andthe symmetric reverse rule, 256 triplet transition
rules can be classified into nonequivalent 88 groups.
In addition to above definitions, the notations in thispaper are as follows;
・ ak=aa･･･a (a=0 or 1).
k-times

Let A be a subsequence.
・ Ak=AA･･･A.
k-times・[ A)∗l: sequence composed of l bits taken from theleft edge when some A's are arranged.
・( A]∗l : sequence composed of l bits taken from the- 42 -right edge when some A's are arranged.

大分工業高等専門学校紀要

第 43 号(平成 18 年 11 月)

・ ∗ : an arbitrary bit.
・ The state of i-th cell of a configuration x isdenoted by xi.
・ x0 and xn+1 mean the left and right boundary of x
respectively. That is, in CA − Rα − β (n) x0= αand xn+1= β .

3. BEHAVIORS OF CA‐580-1(n)A finite cellular automaton CA-580-1(n) treated inthis section has the following triplet local
transition rule f by the definition of the rule number:
111 110 101 100 011 010 001 000
00111010because 58=25+24+23+20.
LEMMA 3.1
For any configuration x of CA-580-1(n), δ (x) does
not contain the subsequence 1111.
Proof.
We set δ (x)=y and yiyi+1yi+2yi+3=1111 (1 ≤ i ≤ n-3).
Then, we have xi-1xixi+1=001, 011, 100 or 101 for
yi=1.
(i)
In the case xi-1xixi+1=001 or 101
For yi+1=1, we have xi+2=1. But this contradicts
yi+2=1 as f(11 ∗ )=0.
(ii)
In the case xi-1xixi+1=011
This case contradicts yi+1=1 as f(11 ∗ )=0.
(iii)
In the case xi-1xixi+1=100
For yi+1yi+2 =11, we have xi+2xi+3=11. But thiscontradicts yi+3=1 as f(11 ∗ )=0.
□COROLLARY 3.2For any configuration x of CA-580-1(n), we set
δ (x)=y. Then, we have y1y2y3≠111.
LEMMA 3.3
For any configuration x of CA-580-1(n), we setδ k ( x) =y where k ≥ 2. Then, we have yn-2yn-1yn≠111.
Proof.
We set yn-2yn-1yn=111 and δ k-1(x)=z. Then, we havezn-3zn-2zn-1zn=1111. But this contradicts lemma 3.1 as
k-1 ≥ 1.
□LEMMA 3.4
For any configuration x of CA-580-1(n), δ k ( x)does not contain the subsequence 000 where k ≥ n-2.
Proof.

We set δ k ( x) =y, yiyi+1yi+2=000 (1 ≤ i ≤ n-2) andδ k −1 ( x) =z. Then, we have zi+1zi+2zi+3=000, 010, 110
or 111 for yi+2=0.
(i)
In the case zi+1zi+2zi+3=010
This case contradicts yi+1=0 as f( ∗ 01)=1.
(ii)
In the case zi+1zi+2zi+3=110 or 111
For yi+1=0, we have zi=1. But this contradicts
lemma 3.1 as k-1 ≥ n-3.
(iii)
In the case zi+1zi+2zi+3=000
Only this case is suitable by zi-1zi=00. Then, wehave zi-1zizi+1zi+2zi+3=00000.
(iii-a) In the case i-1>n-(i+2) i.e. 2i>n-1
We set δ k-{n-(i+2)}(x)=w. Then, we have wn-2wn-1
wn=000. As k-{n-(i+2)}>k-(i-1) ≥ n-2-(n-3)=1,
we have k-{n-(i+2)} ≥ 2. Therefore, this casecontradicts lemma 3.3.
(iii-b) In the case i-1 ≤ n-(i+2) i.e. 2i ≤ n-1
Considering x1x2x3=000 for y1y2y3=000 whereδ (x)=y, we have δ k-{n-(i+2)}(x)=0n andk-{n-(i+2)} ≥ m-2-(m-3)=1. But no predecessorof 0n exists. Therefore, this case is irrelevant. □LEMMA 3.5
For any configuration x of CA-580-1(n), δ k ( x)does not contain the subsequence 111 wherek ≥ 2n-5.
Proof.
We set δ k ( x) =y, yiyi+1yi+2=111 (1 ≤ i ≤ n-2),

δ k −1 ( x) =z and δ k −2 ( x) =w. Then, we have zi-1zizi+1=001, 011, 100 or 101 for yi=1.
(i)
In the case zi-1zizi+1=001 or 101
For yi+1=0, we have zi+2=1. But this contradicts
yi+2=1 as f(11 ∗ )=0.
(ii)
In the case zi-1zizi+1=011
This case contradicts yi+1=1 as f(11 ∗ )=0.
(iii)
In the case zi-1zizi+1=100
For yi+1yi+2 =11, we have zi+2zi+3=11 i.e. zi-1zi
zi+1zi+2zi+3=10011. Then, we have wi-2wi-1wi=001,011, 100 or 101 for zi-1=1.
(iii-a) In the case wi-2wi-1wi=001 or 101
For zi=0, we have wi+1=0. But this contradicts
zi+1=0 as f(10 ∗ )=1.
(iii-b) In the case wi-2wi-1wi=100
For zi=0, we have wi+1=0. But this contradicts
lemma 3.4 as k-2 ≥ 2n-7.
(iii-c) In the case wi-2wi-1wi=011
For zi+1 zi+2=01, we have wi+1wi+2=10 consideringf(10 ∗ )=0. For zi+3=1, we have wi+3wi+4=01 or 11.
Therefore, we have wi-2wi-1･･･wi+4=0111001 or
0111011. Repeating this operation, we set- 43 -

大分工業高等専門学校紀要

第 43 号(平成 18 年 11 月)

δ k-2(i-1)(x)=u. Then, we have u1u2u3=111. But
this contradicts corollary 3.2 because of k-2(i-1)□≥ 2n-5-2i+2 ≥ 1.
LEMMA 3.6
For any configuration x of CA-580-1(n), δ k ( x)does not contain the subsequence 00 where k ≥ 2n-4.
Proof.
We set δ k ( x) =y, yiyi+1=00 (1 ≤ i ≤ n-1) andδ k −1 ( x) =z. Considering lemma 3.4 and lemma 3.5,
we have zi-1zizi+1=010 or 110 for yi=0 as k-1 ≥ 2n-5.
But this contradicts yi+1=0 as f(10 ∗ )=1.
□
LEMMA 3.7
For any configuration x of CA-580-1(n), δ k ( x)does not contain the subsequence 1010 wherek ≥ 2n-6.
Proof.
We set δ k ( x) =y, yiyi+1yi+2yi+3=1010 (1 ≤ i ≤ n-3)
and δ k −1 ( x) =z. For yi=1, we have zi-1zizi+1=001,011, 100 or 101.
(i)
In the case zi-1zizi+1=001 or 101
For yi+1=1, we have zi+2=0. For yi+2 yi+3=10, we
have zi+3zi+4=10 considering lemma 3.4. Thus,
we have zi+1zi+2zi+3zi+4=1010.
(ii)
In the case zi-1zizi+1=100
For yi+1=0, we have zi+2=0. But this contradicts
lemma 3.4 as k-1 ≥ 2n-7.
(iii)
In the case zi-1zizi+1=011
For yi+1yi+2=01, we have zi+2zi+3=01 consideringf(11 ∗ )=0 and lemma 3.4. For yi+3=0, we havezi+4=0. Therefore we have zi+1zi+2zi+3zi+4=1010.
Repeating the above, we set δ k-{n-(i+3)}(x)=w.
Then, we have wn-3wn-2wn-1wn=1010 wherek-{n-(i+3)} ≥ 2n-6-(n-4) ≥ n-2. Moreover we setδ k-{n-(i+3)}-1(x)=u. For wn-1wn=10, we have
un-2un-1un=011. But this contradicts wn-2=0 asf( ∗ 01)=1.
□COROLLARY 3.8
For any configuration x of CA-580-1(n), δ k ( x)does not contain the subsequence 0101 wherek ≥ 2n-5.
Proof.
We set δ k ( x) =y, yiyi+1yi+2yi+3=0101 (1 ≤ i ≤ n-3)
and δk −1

In the case i ≥ 2
We have zizi+1zi+2zi+3=1010 considering lemma
3.4 and f(11 ∗ )=0. But this contradicts lemma
3.7 as k-1 ≥ 2n-6.
(ii)
In the case i=1
We set z1z2z3z4=0010 and δ k −2 ( x) =w. Then, wehave w1w2w3w4 w5=00010. But this contradicts
lemma 3.4 as k-2 ≥ 2n-7.
□(i)

LEMMA 3.9
For any configuration x of CA-580-1(n), we setδ k ( x) =y where k ≥ 2n-4. Then, the followings hold;1.

y= [110)∗n , [101)∗n or [011)∗n .

2.

Above three configurations make a limit cycle.

Proof.
Considering lemma 3.4, lemma 3.5, lemma 3.6
lemma 3.7 and corollary 3.8, we can construct theconfiguration y as follows ;・ 011011011･･･ = [011) ∗n・ 101101101･･･ = [101)∗n・ 110110110･･･ = [110)∗n
It follows thatδ ( [011)∗n ) = [110)∗n , δ ( [110)∗n ) = [101)∗n andδ ( [101)∗n ) = [011)∗n by direct calculations.
Especially, we set x= [1110)∗n . Then, we can showthat δ 2i ( x) = (110]∗i [1110) ∗n−i by induction on i.
Let i=n-3, then we have δ 2 ( n−3) ( x) = (110]∗n −2 111 ,δ 2 n−5 ( x) = (101]∗n−3100 andδ 2 n−4 ( x) = (011]∗n−3 011 = (011]∗n=(011)l= [011) ∗nn=3l1(011)l= [101) ∗nn=3l+111(011)l= [110)∗nn=3l+2.

And the last configurations are configurations on alimit cycle by lemma 3.9.
□Finally, we have the following theorem about
CA-580-1(n).
THEOREM 3.10
CA-580-1(n) has a unique limit cycle of period length
3 and its transient length is 2n-4.

4. CONCLUSIONS( x) =z.

As conclusive remarks, we could show that- 44 -大分工業高等専門学校紀要

第 43 号(平成 18 年 11 月)

CA-580-1(n) has a unique limit cycle of period length
3 and its transient length is 2n-4. There are somefuture tasks. The first is to investigate CA-58 (n)under the other fixed boundary conditions 0-0, 1-0
and 1-1. The second is to investigate 1-dimensional
cellular automata with threshold rules under freeboundary conditions14). And the last is to investigate
1-dimensional cellular automata with reversible
transition functions considered as a special type ofquantum cellular automata15) and 2-dimensional
cellular automata with reversible linear transition
functions using von Neumann neighborhood.
REFERENCES
1)

J. von Neumann: Theory of Self-Reproducing Automata,Illinois Univ. Press, edited and completed by A. W. Burks,
1966.
2) Stephen Wolfram.: Universality and complexity in cellular
automata., Physica D, Vol.10, pp.1-35,1984.
3) Stephen Wolfram: Theory and Applications of CellularAutomata, World Scientific, 1986.
4) Inokuchi, S. and Kawahara, Y.: On cellular automata withlimit cycles of period length one or two (in Japanese), RIMS
Kokyuroku, Research Institute for Mathematical Sciences
Kyoto Univ.,Vol.906,pp.126-134,1995.
5) Sato, T.: On Behaviors of Cellular Automata with Rule 27,
Kyushu Journal of Mathematics,Vol.50,No.1,pp.133-152,
1996.
6) Sato, T.: On Behaviors of Cellular Automata with Rule 11,Research Reports of Oita National College of Technology,Vol.32,pp.128-136,1996.

7) Sato, T.: On Behaviors of Cellular Automata with Rule 43(inJapanese), Research Reports of Oita National College ofTechnology, Vol.33,pp.63-68,1997.
8) Sato, T.: On Behaviors of Cellular Automata with Rule 189,
Research Reports of Oita National College of Technology,
Vol.34,pp.50-53,1998.
9) Sato, T.: On Behaviors of Cellular Automata with Rule 190,
Research Reports of Oita National College of Technology,
Vol.35,pp.53-58,1999.
10) Sato, T.: On Behaviors CA-570-0(m) and CA-571-0(m),Memoirs of Oita National College of Technology, Vol.37,
pp.47-51,2001.
11) Sato, T.: On Behaviors CA-570-1(m) and CA-571-0(m),Memoirs of Oita National College of Technology, Vol.41,
pp.63-70,2005.
12) Shingai, R.: The Maximum Period Realized in 1-D Uniform
Neural Networks with a Refractory Period,
THE TRANSACTIONS OF THE IECE OF JAPAN, Vol.E-61,
No.10,pp.804-808,1978.
13) Inokuchi, S. and Sato, T.: On Limit Cycles and Transient
Lengths of Cellular Automata with Threshold Rules,
Bulletin of Informatics and Cybernetics,Vol.32,No.1,
pp.25-60,2000.
14) Sato,H. and Nishi,T.: One-dimensional Discrete-time Binary
Cellular Neural Networks (in Japanese), THECNICALREPORT OF IEICE.,Vol. NLP200-130,pp.1-8,2001.
15) Inokuchi, S., Honda, K., Lee.H.Y., Sato, T., Mizoguchi, Y.
and Kawahara, Y.: On Reversible Cellular Automata withFinite Cell Array, Lecture Notes in Computer Science,
Springer-Verlag.Vol.3699,pp.130-141,2005.
(Received September 29, 2006)- 45 -