Brute force searches using overlapping constraint templates, as described in Chapter 5 Section 7 of NKS have been surprisingly unsuccessful at finding hierarchical aperiodic patterns; although, one known example is mentioned in the extensive notes. Much more can be done simply by examining preexisting results. Every edge-matching tiling over $\mathbb{Z}^2$ must have a definition in terms of overlapping templates. Such a definition can be obtained simply by listing all possible matching configurations in what is called an Atlas. The purpose of this memo is to obtain and analyze the $3 \times 3$ Atlas for the Trilobite and Crab tiling (a very simple limit-periodic pattern, which we mentioned in the previous post on Static Plane Filling Cellular Automata).

What we are missing so far is a definition of Trilobite and Crab as a substitution system. Producing the correct codified replacement rules is the most difficult part of this entire analysis. Here they are anyways (in a good-enough form, but sort of hacked):

    RRule = Join[{
        T[x0_, mc, h_, v_] :> {
          T[2 x0, mc, h, v],
          T[2 x0 + {1, 0}, oc, h, 1],
          T[2 x0 + {0, 1}, oc, 1, v],
          T[2 x0 - {1, 0}, oc, h, 0],
          T[2 x0 - {0, 1}, oc, 0, v],
          T[2 x0 + {1, 1}, t, 0],
          T[2 x0 + {-1, 1}, t, 1],
          T[2 x0 + {-1, -1}, t, 2],
          T[2 x0 + {1, -1}, t, 3]},

        (* don't need trilobites here *)
        T[x0_, oc, h_, v_] :> {
          T[2 x0, mc, h, v],
          T[2 x0 + {1, 0}, oc, h, 0],
          T[2 x0 + {0, 1}, oc, 0, v],
          T[2 x0 - {1, 0}, oc, h, 1],
          T[2 x0 - {0, 1}, oc, 1, v]}
        },
       (* don't need crabs here *)
       MapThread[
        T[x0_, t, #1] :> {
           T[2 x0, t, #1],
           T[2 x0 + RotateLeft[
               {{1, 1}, {-1, 1}, {-1, -1}, {1, -1}}, #1][[1]], t, #1],
           T[2 x0 + RotateLeft[
               {{1, 1}, {-1, 1}, {-1, -1}, {1, -1}}, #1][[2]], t, #3],
           T[2 x0 + RotateLeft[
               {{1, 1}, {-1, 1}, {-1, -1}, {1, -1}}, #1][[3]], t, #1],
           T[2 x0 + RotateLeft[
               {{1, 1}, {-1, 1}, {-1, -1}, {1, -1}}, #1][[4]], t, #2]
           } &, {{0, 1, 2, 3}, {1, 2, 3, 0}, {3, 0, 1, 2}}]];

Since there are a total of twelve tiles in play--two crabs and one trilobite, each in four orientations--we will use three colors plus monomino markings as seen in Troika, "Reality is not always Probable". The depiction functions are as follows:

Monomino[v0_, 0] := {Black, Disk[v0, 1/8]}
Monomino[v0_, 1] := {Black, Disk[v0 + {1/4, 1/4}, 1/8], 
  Disk[v0 - {1/4, 1/4}, 1/8]}
Monomino[v0_, 2] := {Black, Disk[v0, 1/8], 
  Disk[v0 + {1/4, -1/4}, 1/8], Disk[v0 - {1/4, -1/4}, 1/8]}
Monomino[v0_, 3] := {Black, Disk[v0 + {1/4, 1/4}, 1/8], 
  Disk[v0 - {1/4, 1/4}, 1/8],
  Disk[v0 + {1/4, -1/4}, 1/8], Disk[v0 - {1/4, -1/4}, 1/8]}

ColRules = {
   T[x_, t, r_] :> {Lighter@RGBColor[1, 0, 0], 
     Rectangle[x - {1/2, 1/2}], Monomino[x, r]},
   T[x_, oc, b1_, b2_] :> {Lighter@RGBColor[0, 1, 0], 
     Rectangle[x - {1/2, 1/2}], Monomino[x, Mod[2 b1 + b2, 4]]},
   T[x_, mc, b1_, b2_] :> {Lighter@RGBColor[0, 0, 1], 
     Rectangle[x - {1/2, 1/2}], Monomino[x, Mod[2 b1 + b2, 4]]}
   };

ColRules2 = {
   T[x_, t, r_] :> {Lighter@RGBColor[1, 0, 0], 
     Rectangle[x - {1/2, 1/2}], Monomino[x, r]},
   T[x_, oc, r_] :> {Lighter@RGBColor[0, 1, 0], 
     Rectangle[x - {1/2, 1/2}], Monomino[x, r]},
   T[x_, mc, r_] :> {Lighter@RGBColor[0, 0, 1], 
     Rectangle[x - {1/2, 1/2}], Monomino[x, r]}
   };

ColRules3 = {
   T[x_, t, 
     r_] :> {Switch[r, 0, Hue[(2 - 1)/8], 1, Hue[(2 2 - 1)/8], 2,
      Lighter@Hue[(2 3 - 1)/8], 3, Lighter@Hue[(2 4 - 1)/8]], 
     Rectangle[x]},
   T[x_, oc, b1_, b2_] :> {RGBColor[0, 0, 0], Rectangle[x]},
   T[x_, mc, b1_, b2_] :> {RGBColor[0, 0, 0], Rectangle[x]}
   };

dat = Union[Flatten[T[{0, 0}, mc, 0, 0] /. RRule /. RRule /. RRule]];
Row[Show[#, ImageSize -> 500] & /@ {Graphics[dat /. ColRules], 
   Graphics[dat /. ColRules3]}]

For comparison to our previous animation, we project all green and blue tiles to black on the right. As long as the trilobite orientations are known, the crab orientations can be recovered, after propagation from a distance, by noting orientation of trilobites to direct north, south, east and west.

Now that we have the substitution system working, we just need to blow up the pattern large enough to notice every possible configuration:

ToNum = {T[x_, t, r_] :> r,
   T[x_, oc, b1_, b2_] :> 4 + 2 b1 + b2,
   T[x_, mc, b1_, b2_] :> 8 + 2 b1 + b2};

GetBlocks[dat_] := With[{cents = dat[[All, 1]]},
  dat[[#]] /. ToNum & /@ (Select[
     Flatten /@ 
      DeleteCases[Outer[Flatten[Position[cents, #1 + #2]] &,
        cents, {{0, 0}, {1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1,
           1}, {-1, -1}, {1, -1}}, 1],
       {}, Infinity], Length[#] == 9 &])]

datSets = NestList[Union[Flatten[# /. RRule]] &, T[{0, 0}, mc, 0, 0], 6];

AbsoluteTiming[
 AllBlocks = GetBlocks[#] & /@ datSets[[2 ;; -1]];
 ]

Length /@ AllBlocks
Length[Union[#]] & /@ AllBlocks

Out[]:= {1, 13, 85, 421, 1861, 7813}
Out[]:= {1, 13, 75, 144, 156, 156}

This code could be a little more elegant, but apparently it gets the job done. We obtain a set of 156 $3\times3$ templates. Due to sublattice symmetry, this count is far too many. We can reduce to only $32$ in $8$ groups of $4$:

ReducedAtlas = Cases[Union[AllBlocks[[-1]]], {_, _, _, _, _, 0 | 1 | 2 | 3, 
   0 | 1 | 2 | 3, 0 | 1 | 2 | 3, 0 | 1 | 2 | 3}]

Out[332]= {
{0,5,6,6,5,0,3,0,1}, {1,7,7,4,4,2,1,0,1}, {2,5,6,6,5,2,3,2,1},
{3,7,7,4,4,2,3,0,3}, {8,4,4,5,6,1,0,1,0}, {8,4,4,5,6,1,0,3,0}, 
{8,4,4,5,6,1,0,3,2}, {8,4,4,5,6,3,0,1,0}, {8,4,4,5,6,3,0,3,0}, 
{8,4,4,5,6,3,2,1,0}, {8,5,6,4,4,0,1,2,3}, {9,4,5,5,7,1,0,1,0}, 
{9,4,5,5,7,1,0,1,2}, {9,4,5,5,7,1,0,3,2}, {9,4,5,5,7,1,2,1,0}, 
{9,4,5,5,7,1,2,1,2}, {9,4,5,5,7,3,2,1,0}, {9,5,7,4,5,0,1,2,3}, 
{10,6,4,7,6,1,0,3,2}, {10,6,4,7,6,3,0,3,0}, {10,6,4,7,6,3,0,3,2}, 
{10,6,4,7,6,3,2,1,0}, {10,6,4,7,6,3,2,3,0}, {10,6,4,7,6,3,2,3,2}, 
{10,7,6,6,4,0,1,2,3}, {11,6,5,7,7,1,0,3,2}, {11,6,5,7,7,1,2,1,2}, 
{11,6,5,7,7,1,2,3,2}, {11,6,5,7,7,3,2,1,0}, {11,6,5,7,7,3,2,1,2}, 
{11,6,5,7,7,3,2,3,2}, {11,7,7,6,5,0,1,2,3}}

The $3 \times 3$ templates are required to overlap on $1 \times 3$ edges, so we can even map blue to green and reduce $12$ colors to $8$. Perhaps a little more work could be done to prove that these set of $32$ (or $8$ in four rotational classes) indeed close under inflation, but we leave that task for another day.