Message Boards Message Boards

GROUPS:

Note on NKS ch.5 sec.7: Systems Based on Constraints

Posted 14 days ago
259 Views
|
1 Reply
|
3 Total Likes
|

enter image description here

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]}]

RGB monomino pattern

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}}

Templates

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.

enter image description here -- you have earned Featured Contributor Badge enter image description here Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract