Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download

A (one dimensional) cellular automaton is a function1 F : Σ → Σ with the property that there is a K > 0 such that F (x)i depends only on the 2K + 1 coordinates xi−K , xi−K+1, . . . , xi−1, xi, xi+1, . . . , xi+K . A periodic point of σ is any x such that σ^p (x) = x for some p ∈ N, and a periodic point of F is any x such that F^q (x) = x for some q ∈ N. Given a cellular automaton F, a point x ∈ Σ is jointly periodic if there are p, q ∈ N such that σ^p (x) = F^q (x) = x, that is, it is a periodic point under both functions.

This project aims to explore the nature of one-dimensional Cellular Automata, in the hope of finding the structure of cellular automata through its periodic points.

2033 views
License: MIT
ubuntu2004
1
(* ::Package:: *)
2
3
(*Author: Klaus Sutner*)
4
(*Affiliation: Carnegie Mellon University*)
5
(*email: sutner@cs.cmu.edu*)
6
(*url: http://www.cs.cmu.edu/~sutner*)
7
(*version: 1.0*)
8
9
(* this file is generated by TanglePaclet, do not edit *)
10
11
BeginPackage["KlausSutner`Automata`Cellaut`",{"KlausSutner`Automata`Utils`","KlausSutner`Automata`Fsm`"}];
12
13
14
15
16
CA::usage = "CA[w,k,r] represents a cellular automaton of width w, alphabet k and rule number r.";
17
ECA::usage = "ECA[r] represents elementary cellular automaton with rule number r. Converts to CA[3,2,r].";
18
WidthCA::usage = "WidthCA[C] returns the width of a cellular automaton.";
19
AlphabetCountCA::usage = "AlphabetCountCA[C] returns the size of the alphabet of a cellular automaton.";
20
RuleCA::usage = "RuleCA[C] returns the rule numbew of a cellular automaton.";
21
LocalMapCA::usage = "LocalMapCA[f,C] assigns to f the local map of cellular automaton C.";
22
DomCodomCA::usage = "DomCodomCA[C] returns the domain and codomain of the local map of cellular automaton C.";
23
GlobalMapCA::usage = "GlobalMapCA[f,C] assigns to f the global map of cellular automaton C.";
24
ConvertToCA::usage = "ConvertToCA[f,w,k] returns the cellular automaton defined by local map f.";
25
ToFredkinCA::usage = "ToFredkinCA[C] returns the Fredkin automaton associated with cellular automaton C.";
26
ToWidthTwoCA::usage = "ToWidthTwoCA[C] returns the width-2 cellular automaton corresponding to C.";
27
ComposeCA::usage = "ComposeCA[C1,C2] composes the cellular automata C1 and C2.";
28
SeedConfiguration::usage = "SeedConfiguration[args] produces a seed configuration for a cellular automaton.";
29
OrbitCA::usage = "OrbitCA[C,X,t] returns the t-step orbit of configuration X under cellular automaton C.";
30
PrintCA::usage = "PrintCA[C] prints the rule table of cellular automata C.";
31
ToSemiautomatonCA::usage = "ToSemiautomatonCA[C] converts cellular automaton C into a semi-automaton.";
32
BalancedQCA::usage = "BalancedQCA[C] checks if cellular automaton C is balanced.";
33
ClassifyCA::usage = "ClassifyCA[C] tests whether a cellular automaton C is surjective, open or injective.";
34
ToWelchAutomatonCA::usage = "ToWelchAutomatonCA[C] converts cellular automaton C into the corresponding Welch automata.";
35
InverseCA::usage = "InverseCA[C] constructs the inverse cellular automaton.";
36
ShrinkCA::usage = "ShrinkCA[C] removes useless variables at either end of the local map of cellular automaton C.";
37
ShiftOrbit::usage = "ShiftOrbit[orb,k] right-shifts an orbit by k places.";
38
Begin["`Private`"];
39
SyntaxInformation[CA] = {"ArgumentsPattern"->{_,_,_}};
40
SyntaxInformation[ECA] = {"ArgumentsPattern"->{_}};
41
ECA[r_Integer?NonNegative] := CA[3,2,r];
42
SyntaxInformation[WidthCA] = {"ArgumentsPattern"->{_}};
43
Attributes[WidthCA]={Listable};
44
WidthCA[CA[w_,k_,r_]] := w;
45
SyntaxInformation[AlphabetCountCA] = {"ArgumentsPattern"->{_}};
46
Attributes[AlphabetCountCA]={Listable};
47
AlphabetCountCA[CA[w_,k_,r_]] := k;
48
SyntaxInformation[RuleCA] = {"ArgumentsPattern"->{_}};
49
Attributes[RuleCA]={Listable};
50
RuleCA[CA[w_,k_,r_]] := r;
51
Attributes[LocalMapCA] = {HoldFirst};
52
Options[LocalMapCA] = {"KAdic"->True};
53
LocalMapCA[ ff_, ca_CA, opts : OptionsPattern[] ] :=
54
(
55
ClearAll[ff];
56
AssignFunction[ ff, Sequence@@DomCodomCA[ca], "KAdic"->OptionValue["KAdic"] ]
57
);
58
SyntaxInformation[DomCodomCA] = {"ArgumentsPattern"->{_,OptionsPattern[]}};
59
Options[DomCodomCA]={Full->True};
60
DomCodomCA[ca_CA,OptionsPattern[]] :=
61
With[ {r = RuleCA[ca], w = WidthCA[ca], k = AlphabetCountCA[ca]},
62
With[ {res = { IntegerDigits[Range[0, k^w - 1], k, w],
63
Reverse[IntegerDigits[r, k, k^w]] } },
64
If[OptionValue[Full], res, Rule@@@Pairs@@res ] ] ];
65
SyntaxInformation[GlobalMapCA] = {"ArgumentsPattern"->{_,_,OptionsPattern[]}};
66
Options[GlobalMapCA]={"Boundary"->"Cyclic","BoundaryZero"->0};
67
Attributes[GlobalMapCA]={HoldFirst};
68
GlobalMapCA[ ff_, ca_CA, opts:OptionsPattern[] ] :=
69
Module[ {w,w2,loc},
70
ClearAll[ff];
71
w = WidthCA[ca];
72
w2 = Ceiling[w/2];
73
LocalMapCA[loc,ca,"KAdic"->False];
74
ff = Switch[ OptionValue["Boundary"],
75
"Cyclic", loc /@ Partition[#,w,1,w2]&,
76
"Fixed"|"Periodic", loc /@ Partition[#,w,1,w2,OptionValue["BoundaryZero"]]&,
77
None, loc /@ Partition[#,w,1]&
78
];
79
];
80
SyntaxInformation[ConvertToCA] = {"ArgumentsPattern"->{_,_,_,OptionsPattern[]}};
81
Options[ConvertToCA]={Type->Function};
82
ConvertToCA[ ff_, w_Integer?Positive, k_Integer?Positive, opts:OptionsPattern[] ] :=
83
Module[ {A,r},
84
A = Tuples[ Range[0,k-1], w ];
85
r = Switch[ OptionValue[Type],
86
Function, ff@@@A,
87
Rule, A /. ff,
88
Boole, Boole[ ff@@@UnBoole[A] ]
89
];
90
CA[ w, k, FromDigits[Reverse[r],k] ]
91
];
92
SyntaxInformation[ToFredkinCA] = {"ArgumentsPattern"->{_,OptionsPattern[]}};
93
ToFredkinCA[ ca_CA ] :=
94
Module[ {f, ff, k = AlphabetCountCA[ca], w = WidthCA[ca]},
95
LocalMapCA[ f, ca ];
96
ff[xx__] := With[ { zz = Mod[{xx}, k ], ci = Ceiling[w/2] },
97
k zz[[ci]] + Mod[ f @@ zz + Quotient[{xx}[[ci]], k], k] ];
98
ConvertToCA[ff, w, k^2]
99
];
100
SyntaxInformation[ToWidthTwoCA] = {"ArgumentsPattern"->{_,OptionsPattern[]}};
101
ToWidthTwoCA[ca_CA] :=
102
Module[ {w, k, ff},
103
w = WidthCA[ca];
104
k = AlphabetCountCA[ca];
105
GlobalMapCA[ff, ca, "Boundary" -> None];
106
CA[ 2, k^(w - 1),
107
FromDigits[ Reverse[FromDigits[#,k]& /@ (ff /@ Tuples[Range[0,k-1],2w-2]) ],
108
k^(w - 1)] ]
109
];
110
SyntaxInformation[ComposeCA] = {"ArgumentsPattern"->{_,_,OptionsPattern[]}};
111
ComposeCA[ C1_CA, C2_CA, opts:OptionsPattern[] ] :=
112
Module[ {k,alph,w,f1,f2,B,norm},
113
w = WidthCA[C1] + WidthCA[C2] - 1;
114
k = AlphabetCountCA[C1];
115
GlobalMapCA[ f1, C1, "Boundary"->None];
116
LocalMapCA[ f2, C2, "KAdic"->False];
117
B = f2[f1[#]]& /@ Reverse[Tuples[Range[0,k-1],w]];
118
CA[ w, k, FromDigits[B,k] ]
119
] /; AlphabetCountCA[C1]===AlphabetCountCA[C2];
120
121
ComposeCA[C1_CA,C2_CA,ca__CA,opts:OptionsPattern[]] :=
122
ComposeCA[ComposeCA[C1,C2,opts],ca,opts];
123
ComposeCA[ca_CA,opts:OptionsPattern[]] := ca;
124
SyntaxInformation[SeedConfiguration] = {"ArgumentsPattern"->{_,_.,OptionsPattern[]}};
125
Options[SeedConfiguration]={Alignment->Center,Padding->0,"RandomDigits"->0};
126
SeedConfiguration[n_Integer?Positive,opts:OptionsPattern[]]:=
127
SeedConfiguration[{1},n,opts];
128
SeedConfiguration[s_Integer?NonNegative,n_Integer?Positive,opts:OptionsPattern[]]:=
129
SeedConfiguration[{s},n,opts];
130
SeedConfiguration[s_List,n_Integer?Positive,opts:OptionsPattern[]]:=
131
Module[{rnd,whr,pad,typ},
132
If[0<(rnd=OptionValue["RandomDigits"]),
133
Return[RandomInteger[{0,rnd-1},n]]];
134
whr=OptionValue[Alignment];
135
pad=OptionValue[Padding];
136
Flatten[Switch[whr,
137
Center,PadLeft[s,n,pad,Floor[1/2 (n-Length[s])]],
138
Right,PadLeft[s,n,pad],
139
_,PadRight[s,n,pad]]
140
]
141
];
142
SyntaxInformation[OrbitCA] = {"ArgumentsPattern"->{_,_,_.,OptionsPattern[]}};
143
Options[OrbitCA]={"Boundary"->"Cyclic","BoundaryZero"->0};
144
OrbitCA[ ca_CA, pat_List, t_Integer:40, opts:OptionsPattern[] ] :=
145
Module[ {rho},
146
GlobalMapCA[ rho, ca, SelectOptions[GlobalMapCA,opts] ];
147
NestList[ rho, pat, t ]
148
];
149
SyntaxInformation[PrintCA] = {"ArgumentsPattern"->{_,OptionsPattern[]}};
150
PrintCA[ca_CA] :=
151
Module[ {rules,k,A,res},
152
rules = DomCodomCA[ca,Full->False];
153
k = AlphabetCountCA[ca];
154
Assert[ k<8, "Alphabet too large."];
155
A = AlphabetList[Alpha[k,<|"AlphabetType"->"Digit"|>]];
156
rules = MapAt[StringJoin[A[[#+1]]]&, rules,{All,1}];
157
res = Switch[ WidthCA[ca],
158
1, {rules},
159
2|3, Partition[ rules, AlphabetCountCA[ca]^(WidthCA[ca]-1) ],
160
_, Partition[ rules, AlphabetCountCA[ca]^(WidthCA[ca]-2) ]
161
];
162
TableForm[Thread[res],TableSpacing->{1,2}]
163
];
164
SyntaxInformation[ToSemiautomatonCA] = {"ArgumentsPattern"->{_,OptionsPattern[]}};
165
Options[ToSemiautomatonCA]={StateType->"Indexed"};
166
ToSemiautomatonCA[ca_CA,opts:OptionsPattern[]]:=
167
Module[{w,k,n,A,lb,tr,G},
168
w = WidthCA[ca];
169
k = AlphabetCountCA[ca];
170
n = k^(w-1);
171
A = Alpha[k, <|"AlphabetType"->"Digit", "AlphabetOffset"->0|> ];
172
lb = Reverse@IntegerDigits[RuleCA[ca],k,k^w]+1;
173
tr = DirectedEdge@@@Pairs[Flatten@Thread@Table[Range[n],{k}],Flatten@Table[i,{k},{i,n}],lb];
174
G = Graph[ tr ];
175
Switch[ OptionValue[StateType],
176
"Indexed", None,
177
"Shallow", V = CartesianProduct@@Table[Range[k],{w-1}];
178
G = VertexReplace[ G, Thread[VertexList[G]->V] ],
179
"Words", V = Words[{w-1},A];
180
G = VertexReplace[ G, Thread[VertexList[G]->V] ]
181
];
182
FA[ TSys[ n, k, G,
183
Alpha[k, <|"AlphabetType"->"Digit", "AlphabetOffset"->0|> ],
184
<| "TransType"->TransitionType[n,k,G] |>],
185
<| "AccCond"->Existential[All, All],"Special"->"MultiEntry" |> ]
186
];
187
SyntaxInformation[BalancedQCA] = {"ArgumentsPattern"->{_,OptionsPattern[]}};
188
Options[BalancedQCA] = {Full->False};
189
BalancedQCA[ ca_CA, opts : OptionsPattern[] ] :=
190
With[ {cod = Last@DomCodomCA[ca],cnt = AlphabetCountCA[ca]^(WidthCA[ca]-1)},
191
If[ OptionValue[Full],
192
Frequencies[cod],
193
Union[Last/@Tally[cod]] === {cnt}
194
]
195
];
196
SyntaxInformation[ClassifyCA] = {"ArgumentsPattern"->{_,OptionsPattern[]}};
197
Options[ClassifyCA]={Full->False};
198
ClassifyCA[ca_CA,opts:OptionsPattern[]]:=
199
Module[{n,T,G,scc,ntscc,sccind,ed,H,HH,diag,res},
200
If[ !BalancedQCA[ca], Return[0] ];
201
n = AlphabetCountCA[ca]^(WidthCA[ca]-1);
202
T = TransitionSystem@ToSemiautomatonCA[ca];
203
G = TransitionSystemGraph[ProductTransitionSystem[T,StateType->"Shallow"]];
204
{scc,ntscc,sccind} = StronglyConnectedComponents[G];
205
{H,scc,ntscc} = Most@CondensationGraph[G,Full->True,Type->"Shallow"];
206
diag = First@Select[scc,MemberQ[#,{1,1}]&];
207
HH = Subgraph[H,Intersection[
208
FlattenOne[VertexOutComponent[H,#]& /@ ntscc],
209
FlattenOne[VertexOutComponent[ReverseGraph@H,#]& /@ ntscc]
210
]];
211
212
res = Which[
213
Length[diag] != n, 0,
214
Length[ntscc]==1, 3,
215
VertexDegree[HH,diag]==0, 2,
216
True, 1 ];
217
If[ OptionValue[Full], Sow[{res,H,HH,scc,ntscc}] ];
218
res
219
];
220
SyntaxInformation[ToWelchAutomatonCA] = {"ArgumentsPattern"->{_,OptionsPattern[]}};
221
Options[ToWelchAutomatonCA]={Full->True};
222
ToWelchAutomatonCA[ca_CA,opts:OptionsPattern[]]:=
223
Module[{sa,mr,mxr,pos,Wr,ml,mxl,Wl,nwm},
224
sa = ToSemiautomatonCA[ca];
225
(* right Welsh *)
226
mr = ToKernelFA[ sa, {1}, Full->True ];
227
mxr = Max[ Length/@ StateList[mr] ];
228
pos = Select[StateList[mr],Length[#]==mxr&];
229
Wr = CloneFA[ SubAutomatonFA[mr, pos, StateType->"Deep"],
230
"InitialStates"->{1}, "FinalStates"->All ];
231
(* left Welsh *)
232
ml = ToKernelFA[ ReverseFA[sa],{1},Full->True];
233
mxl = Max[ Length/@ StateList[ml] ];
234
pos = Select[StateList[ml],Length[#]==mxl&];
235
Wl = CloneFA[ SubAutomatonFA[ ml, pos, StateType->"Deep" ],
236
"InitialStates"->{1}, "FinalStates"->All ];
237
nwm = AlphabetCountCA[ca]^(WidthCA[ca]-1)/(mxl mxr);
238
If[ OptionValue[Full],
239
{{mxl,nwm,mxr},{Wl,Wr}},
240
{mxl,nwm,mxr}
241
]
242
];
243
SyntaxInformation[InverseCA] = {"ArgumentsPattern"->{_,OptionsPattern[]}};
244
Options[InverseCA]={};
245
InverseCA[CA[1,k_Integer,r_Integer]]:=
246
Module[{lab},
247
LocalMapCA[lab, CA[1,k,r], Full->True ];
248
Assert[PermutationListQ[lab+1]];
249
CA[ 1, k, FromDigits[ Reverse[InversePermutation[lab+1]-1], k ] ]
250
];
251
InverseCA[ca_CA,opts:OptionsPattern[]]:=
252
Module[{k,ll,wi,Wl,Wr,dql,defl,dqr,defr,ww,sa,Ll,Lr,rule,rk},
253
k = AlphabetCountCA[ca];
254
ll = k^(WidthCA[ca]-1);
255
{wi,{Wl,Wr}} = ToWelchAutomatonCA[ca];
256
{dql,defl} = PropertyQFA[Wl,"Definite",Full->True];
257
{dqr,defr} = PropertyQFA[Wr,"Definite",Full->True];
258
ww = defl + defr;
259
sa = ToSemiautomatonCA[ca];
260
Lr = auxFullanguage[sa,defl];
261
Ll = auxFullanguage[ReverseFA[sa],defr];
262
Lr = (#[[2]]&/@#)& /@ GatherBy[ Lr, First ];
263
Ll = Map[ Reverse,(#[[2]]&/@#)& /@ GatherBy[ Ll, First ],{2} ];
264
rule = Last /@ Sort@FlattenOne@MapIndexed[
265
(Flatten/@CartesianProduct@@Join[#1,{#2}])&,Pairs[Ll,Lr]];
266
rk = Thread[Range[ll]->Flatten[Thread[Table[Range[k]-1,{ll/k}]]]];
267
CA[ ww, k, FromDigits[ Reverse[rule/.rk], k ] ]
268
];
269
auxFullanguage[M_FA,r_Integer]:=
270
Module[{n,tr,targ,extend},
271
n = StateCount[M];
272
tr = List@@@TransitionList[M];
273
targ[p_Integer] := targ[p] = Reverse /@ Rest /@ Cases[tr,{p,_,_} ] ;
274
extend[{p_Integer,L_List,q_Integer}] :=
275
Table[ {p,Append[L,x[[1]]],x[[2]]}, {x,targ[q]} ];
276
Union[Most /@ Nest[ FlattenOne[extend/@#]&, Table[ {p,{},p}, {p,n} ], r ]]
277
];
278
SyntaxInformation[ShrinkCA] = {"ArgumentsPattern"->{_,OptionsPattern[]}};
279
ShrinkCA[ CA[w_Integer, k_Integer, r_Integer ] ]:=
280
ShrinkCA[ IntegerDigits[r,k,k^w], k ];
281
ShrinkCA[ rr_List,k_Integer]:=
282
Module[ {red},
283
red = FixedPoint[ auxDepFirst[#,k]&,rr,10 ];
284
red = FixedPoint[ auxDepLast[#,k]&,red,10 ];
285
CA[ PadicOrder[Length[red],k], k, FromDigits[red,k] ]
286
];
287
288
auxDepFirst[L_List, k_Integer] :=
289
With[{part = Partition[L, Length[L]/k]},
290
If[ SameQ@@part, First@part, L]];
291
292
auxDepLast[L_List, k_Integer] :=
293
With[{part = Partition[L, k]},
294
If[AllTrue[part, SameQ @@ #1 & ], First /@ part, L]];
295
SyntaxInformation[ShiftOrbit] = {"ArgumentsPattern"->{_,_.}};
296
ShiftOrbit[orb_?MatrixQ,k_Integer:1] :=
297
MapIndexed[RotateRight[ #1, k #2 ]&, orb];
298
WidthCA::args = "Wrong argument(s), try WidthCA[C]";
299
WidthCA[__] := $Failed /; Message[WidthCA::args];
300
AlphabetCountCA::args = "Wrong argument(s), try AlphabetCountCA[C]";
301
AlphabetCountCA[__] := $Failed /; Message[AlphabetCountCA::args];
302
RuleCA::args = "Wrong argument(s), try RuleCA[C]";
303
RuleCA[__] := $Failed /; Message[RuleCA::args];
304
LocalMapCA::args = "Wrong argument(s), try LocalMapCA[f,C]";
305
LocalMapCA[__] := $Failed /; Message[LocalMapCA::args];
306
DomCodomCA::args = "Wrong argument(s), try DomCodomCA[C]";
307
DomCodomCA[__] := $Failed /; Message[DomCodomCA::args];
308
GlobalMapCA::args = "Wrong argument(s), try GlobalMapCA[f,C]";
309
GlobalMapCA[__] := $Failed /; Message[GlobalMapCA::args];
310
ConvertToCA::args = "Wrong argument(s), try ConvertToCA[f,w,k]";
311
ConvertToCA[__] := $Failed /; Message[ConvertToCA::args];
312
ToFredkinCA::args = "Wrong argument(s), try ToFredkinCA[C]";
313
ToFredkinCA[__] := $Failed /; Message[ToFredkinCA::args];
314
ToWidthTwoCA::args = "Wrong argument(s), try ToWidthTwoCA[C]";
315
ToWidthTwoCA[__] := $Failed /; Message[ToWidthTwoCA::args];
316
ComposeCA::args = "Wrong argument(s), try ComposeCA[C1,C2]";
317
ComposeCA[__] := $Failed /; Message[ComposeCA::args];
318
SeedConfiguration::args = "Wrong argument(s), try SeedConfiguration[args]";
319
SeedConfiguration[__] := $Failed /; Message[SeedConfiguration::args];
320
OrbitCA::args = "Wrong argument(s), try OrbitCA[C,X,t]";
321
OrbitCA[__] := $Failed /; Message[OrbitCA::args];
322
PrintCA::args = "Wrong argument(s), try PrintCA[C]";
323
PrintCA[__] := $Failed /; Message[PrintCA::args];
324
ToSemiautomatonCA::args = "Wrong argument(s), try ToSemiautomatonCA[C]";
325
ToSemiautomatonCA[__] := $Failed /; Message[ToSemiautomatonCA::args];
326
BalancedQCA::args = "Wrong argument(s), try BalancedQCA[C]";
327
BalancedQCA[__] := $Failed /; Message[BalancedQCA::args];
328
ClassifyCA::args = "Wrong argument(s), try ClassifyCA[C]";
329
ClassifyCA[__] := $Failed /; Message[ClassifyCA::args];
330
ToWelchAutomatonCA::args = "Wrong argument(s), try ToWelchAutomatonCA[C]";
331
ToWelchAutomatonCA[__] := $Failed /; Message[ToWelchAutomatonCA::args];
332
InverseCA::args = "Wrong argument(s), try InverseCA[C]";
333
InverseCA[__] := $Failed /; Message[InverseCA::args];
334
ShrinkCA::args = "Wrong argument(s), try ShrinkCA[C]";
335
ShrinkCA[__] := $Failed /; Message[ShrinkCA::args];
336
ShiftOrbit::args = "Wrong argument(s), try ShiftOrbit[orb,k]";
337
ShiftOrbit[__] := $Failed /; Message[ShiftOrbit::args];
338
Protect[{
339
WidthCA,AlphabetCountCA,RuleCA,LocalMapCA,DomCodomCA,GlobalMapCA,ConvertToCA,ToFredkinCA,ToWidthTwoCA,ComposeCA,SeedConfiguration,OrbitCA,PrintCA,ToSemiautomatonCA,BalancedQCA,ClassifyCA,ToWelchAutomatonCA,InverseCA,ShrinkCA,ShiftOrbit}];
340
End[];
341
EndPackage[];
342
343