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