37INJECTIVITY OF GLOBAL MAPS OF CELLULAR
AUTOMATAHIROYUKI ISHIBASHI

ABSTRACT.
The purpose is to show briefly and visually that
cellular automata \mathcal{A}s of finite type with a quiescent state q are
injective if and only if cithcr \mathcal{A} contains two mutuaıly erasable

configurations c_{1}, c_{2} in Moore [2] or two not distinguished config‐
urations d_{1}, d_{2} in Myhill [3].
1

1. PRELIMINARIES

o\mathcal{A}=\{\mathbb{Z}^{2}, S, N, f\} : a cellular automaton
where\mathbb{Z}=\{0, \pm 1, \pm 2, \cdots\} : the rational integers,
S=\{s_{1}, s_{2}, \cdot\cdot\cdot . s_{t}\} : the state set 7

N(i)=\begin{ar ay}{l } \dot{i}+(-1, ) \dot{i}+(0,1) \dot{i}+(1, ) \dot{i}+(-1,0) \dot{i}+(0, ) \dot{i}+(1,0) -1)i+(-1 i+(0,-1) i+(1,- ) \end{ar ay}\subset q\mathb {Z}^{2}: neighbourhood of i for i=(i_{1}, i_{2})\in \mathbb{Z}^{2} , ,so|N(i)|=9,

1991 Mathematics Subject Classification. 37B15,68Q80.
Key words and phrases. cellular automaton, tessellation space, global map ofconfigurations, mutually erasable, Garden of Eden .

lThis work was supported by the Research Institutc for Mathematical Sciences,a Joint Usage/Research Center located in Kyoto University.

38
HIROYUKI ISHIBASHI

S

f

:

local map ,oC=S^{\mathbb{Z}^{2}} : configuration set,
C\ni c=(\cdots , c(i), \cdots):\mathbb{Z}^{2}arrow S ,a map

oF:Carrow C : global map

c=(\cdots, c(i), \cdots)\mapsto c'=(\cdots, c'(i), \cdots)
wherec'(i)=f(c(N(i))) with c(N(i))=c|_{N(i)}oC_{n}=\{c|_{\triangle_{n}}|c\in C\}
where \triangle_{n} is an n\cross n- square subset of \mathb {Z}^{2}(Note: Since F is homogeneous, the choice of\triangle_{n} in \mathb {Z}^{2} is not essential. )oC_{n+2}=\{c|_{\triangle_{n+2}}|c\in C\}
where\triangle_{n+2} is the extension of \triangle_{n} one cell onfour sides.

oC_{n+2}\backslash C_{n}=\{c|_{\triangle_{n+2\backslash \triangle_{n}}}|c\in C\}: the set called edges or frames

oE=c\backslash c_{n} : environment of c_{n} ,where c\in C andc_{n}\in C_{n} and we write

c=c_{n}\vee E
0For c=c_{n}\vee e with

c\in C_{n+2}, c_{n}\in C_{n} and e\in C_{n+2}\backslash C_{n} , wehavec(N(i))\subseteq c for i\in\triangle_{n}This allows us to define a function

F_{n,e}:C_{n}arrow C_{n}c_{n}= (. . . c_{n}(i), \cdot \cdot \cdot)\mapsto c_{n}'=(. . . 7c_{n}'(i), \cdot \cdot \cdot)
withc_{n}'(i)=f(c(N(i)))
oq\in S with fandc=c_{n}\vee e
=q

9

:

quiescent state.

39
INJECTIVITY OF GLOBAL MAPS OF CELLULAR AUTOMATA

oc\in C with|\{i\in \mathbb{Z}^{2}|c(i)\neq q\}|<\infty: a configuration of finite type,i.e.,: finite type \Leftrightarrow c=c_{n}\vee Ecfor some c_{n} in C_{n} and E an environment of which states are all q.

* Assumption.

(1) \exists_{q\in S}.
(2) \forall_{C}\in C\Rightarrow c : finite type.

2. STATEMENT OF THE THEOREM

Definition.

d_{1}, d_{2}\in C_{n-4} with d_{1}\neq d_{2} :\Leftrightarrow\exists_{d'}\in C_{n-4},n‐mutually erasable\exists_{g,g'}\in C_{n-2}\backslash C_{n-4}andsuch that

C_{n-2}\ni d_{1}\vee\prime\vee g'\in C_{n-2}.
C_{n-2}\ni d_{2}\veelbL,,b\exists_{h}\in C_{n}\backslash C_{n-2}40HIROYUKI ISHIBASHI

Remark. (a) Let d_{1}, d_{2} be n ‐mutually erasable. Then, for any lin C_{n+2}\backslash C_{n} there exists h' in C_{n}\backslash C_{n-2} such that

F_{n.l}C_{n}\ni c_{1}=d_{1}\vee g\vee hd'\vee g'\vee h'\in C_{n}.
C_{n}\ni c_{2}=d_{2}\vee g\vee h

F_{n,l}(b) Note that d\'{i}=d_{1}\vee g and d_{2}'=d_{2}\vee g are also (n+2) ‐mutuallyerasable by taking h, l for g, h and thus this procedure can be contitiued
until to get their extensions \tilde{c}_{1},\overline{c}_{2} in C.
Definition.

d_{1}, d_{2}\in C_{n-4} with d_{1}\neq d_{2} :\Leftrightarrow\exists_{C'}\in Candn‐not distinguished\exists_{E}\in C\backslash C_{n-4}such thatC\ni c_{1}=d_{1}\vee E Fc^{I}\in C.

C\ni c_{2}=d_{2}\vee E

F

Now we state our theorem.

Theorem.

The following are equivalent:(I) F\neq inje ctive,(I_{n})\exists_{d_{1},d_{2}}\in C_{n-4} : n‐ mutually erasable for somenin \mathbb{N}.

(I_{n}')\exists_{d_{1},d_{2}}\in C_{n-4} : n‐ not distinguished for some n in \mathbb{N}.

41
41
INJECTIVITY OF GLOBAL MAPS OF CELLULAR AUTOMATA

3. PROOF FOR THE THEOREM(a)(I) : F\neq injective \Rightarrow\exists_{C_{1},C_{2}}\in Csuch that(i) c_{1}\neq c_{2}(ii) F(c_{1})=F(c_{2})\RightarrowSincec_{1}, c_{2}: finite type,

we have\exists_{d_{1},d_{2}}\in C_{n-4}and\exists_{E}\in C\backslash C_{n-4} of which states are all q

such thatc_{i}=d_{i}\vee E for

i=1,2,

where(i) d_{1}\neq d_{2} by (i),(ii) F(c_{1})=F(c_{2}) by (ii)

\Rightarrow(I_{n}')(b)\exists_{d_{1},d_{2}}\in C_{n-4} with d_{1}\neq d_{2} and \exists_{E}\in C\backslash C_{n-4}(I_{n}') :such that

F(d_{1}\vee E)=F(d_{2}\vee E)\Rightarrow

expressing E as

E=g\vee h\vee E' , where

ginC_{n-2}\backslash C_{n-4},E'

hinC_{n}\backslash C_{n-2}an environment of C_{n},we have d' in

C_{n-4} and g' in C_{n-2}\backslash C_{n-4} such thatd_{1}\vee\prime\vee g',d_{2}\vee
IUA,b\Rightarrow(I_{n})

.

and

42
HIROYUKI ISHIBASHI(c)(I_{n}) : \exists_{d_{1},d_{2},d'i_{I1}C_{n-4}} with d_{1}\neq d_{2}, \exists_{g,g}/ in C_{n-2}\backslash C_{n-4},\exists_{h} in C_{n}\backslash C_{n-2}such thatd_{1}\vee\prime\vee g'd_{2}\veetua,,e\Rightarrow by(b) of Remark\exists_{g_{1} in C_{n}\backslash C_{n-2}, \exists_{g_{2} in C_{n+2}\backslash C_{n},

\cdot

\cdot

\exists_{C\in}Csuch thatC\ni c_{1}=d_{1}\vee g\vee g_{1}\vee g_{2}\vee\cdot

\cdot

\cdot

C',
C\ni c_{2}=d_{2}\vee g\vee g_{1}\vee g_{2}\vee\cdot

\cdot

\cdot

F

\Rightarrow c_{1}\neq c_{2} by d_{1}\neq d_{2} , and F(c_{1})=F(c_{2})\Rightarrow(I)

.

\cdot

and

43
INJECTIVITY OF GL () BAL MAPS OF CELLULAR AUTOMATAREFERENCES[1] B. Durand, Global Properties of Cellular automata, [E. Goles, S. Martinez,
Eds. , Cellular automata Complex Systems], Kluwer Academic Pblishers,(1999) 1‐22.
[2] K. Jarkko, [Part 1: Spcial issue: Current research trends in cellular automata
thcory], Nat. Comput. 16, no. 3 (2017) 365‐366.
[3] E. \Gamma . Moore, Machine Modeıs of Self‐Reproduction, Proc. Symp. Apl. Math.
14 (1963) 17‐34.
[4] J. Myhill, The Convers to Moore’s Garden‐of‐Eden Theorem, Proc. Am. Math.
Soc. 14 (1963) 685‐686.
[5] H. Nishio, T. Saito, Information of Cellular Automata I‐ An Algebraic Sutady‐, Fundamenta Informaticae 58 (2003) 399‐420.

CHUOU 2‐3‐8, MOROYAMA, IRUMA, SAITAMA, JAPANE‐mail address: hishi@yuzu‐tv.ne.jp