Wang Tiles – 1

In Penrose Tilings – 1 I introduced, briefly, Wang Tiles.  I’ve been playing with them a bit since for a number of reasons.  These tiles can represent a Turing machine and so a set of them represents a computer and a program to execute along with input and output.  If I hand you a set of Wang tiles that I’ve created, for example this set

Wang Tiles for adding

you would probably execute my program (with various inputs) without knowing anything about the tiles.  Given the way they are you’d probably arrange them so that the text on the tiles was right side up (which is good because Wang tiles can’t be rotated) and you’d probably guess that neighboring squares should have matching colors on the side they share.  That is almost enough to force the tiles.  However this is a computer program and requires input and this particular program doesn’t have a fixed input.  If I gave you some input, you would (I think) become a compiler or a computer yourself and run (or interpret? I’m not sure) the program and arrive at the output. I can initialize the program above (which is the addition of numbers program) with the tiles below.

input for Wang Tile addition of 2 and 2.

From here you are forced to execute the rest of the code which will result in

2+2=4

Your input consists of two ones above the ‘head’ (of the Turing machine we’re mimicking) and two ones below it (and perhaps some zeroes).  The left column can be viewed as the tape of the Turing machine initially while the right column can be viewed as the tape of the machine after the program has run.  You’ll notice that there’s a consecutive string of four ones, 2+2=4.  It would be easy to show you how to use this ‘calculator’ to perform addition of positive integers.  You could, in principle, carry these tiles in a bag and perform computations when needed much as you would with an abacus.

This raises some questions from the interested reader.  How do I program with Wang tiles?  I want to cover that here eventually, but for the time being I recommend another blog, called Moyix which has a readable explanation.

I like Wang Tiles more than Turing machines because the mechanism for computation is the person tiling.  I’m going to give some sets to friends and children I know and see if they can run the above program (and some others like the Busy Beaver program with 3 states shown below that I ‘ran’ while giving midterms this morning. The missing tiles on the lower  left is because I don’t have enough tiles representing zeroes yet.)

Busy Beaver with three states on two symbols

These tiles don’t even have to have characters on them, just some indication of which way is ‘up’ so that the tiles are not rotated.  The colors alone are enough to encode the program.  I plan on making a wooden set over break.  I want to see if I can feed my programs to kids and if they will run them.  I’m not sure what I’m trying to prove with such an aim, but perhaps I’ll figure that out along the way.

These tiles give us a way of envisioning computations.  What does a computable function look like?  What are the best choice of colors?  This reminds me of some questions about Penrose tiles.  Recall that we can describe a Penrose tiling (non uniquely) by an infinite sequence of zeros and ones subject to the constraint that there are no consecutive ones.  Sequences that agree after some initial segment describe the same tiling so we ought to take a quotient.  That’ll be the topic of a Penrose Tilings – 2 post eventually.  For now, the idea is that such a set of sequences can be mapped 1:1 onto the real numbers (non uniquely) and so there ought to be a sense by which different Penrose Tilings correspond to different real numbers.  Some should be rational, some irrational and some even transcendental (most in fact :).  We should be able to perform algebra on these tilings and, one suspects, mimic anything on the reals by tilings.  The idea of a calculus of Penrose Tilings is exciting but doomed.  Because all we can ever see is a finite portion of the tiling, we can never tell from such a picture which tiling we are looking at.  Every picture of a Penrose tiling in existence can be thought of as just sections of the (0,0,0,…) tiling.

Reflecting on these properties of Penrose Tilings is similar or related in some way to thinking about the nature of the real numbers.  I think we fool ourselves into thinking that we can distinguish between real numbers.  Certainly this is the case with irrational numbers.  If I give you a number like 1.41421356237… you might say “Oh, there’s the square root of two.”  How can we say this?  What we mean is that this number starts the same way as the square root of two.  There are an uncountably infinite amount of other such numbers though so what makes us distinguish the square root of two out of all the other uncountably many other irrational numbers arbitrarily close to the square root of two?  I think what stops us is our ability to name them.

How many irrational numbers can you name?  Aside from multiples?  Yet these are essentially all the real numbers.  The rationals, while dense, are measure zero.  They only serve to approximate that which we fail to see, name and experience.  The number line is a terribly mysterious object.  Thinking about our inability to see different Penrose tilings is just a consequence of that mystery.

I have always found that physics provided me with extra insight and intuition about mathematical objects.  It allows the tool of analogy to leverage my understanding of one idea against a new one.  In the same sense I wonder what intuition we could gain looking at colorful pictures of computations and infinite tilings that represent, somehow, real numbers?

Information is an object I know little about.  Posts like Shea’s on Information Field Theory, the Bekenstein-Hawking entropy, and comics such as XKCD’s “A bunch of rocks,” give me a dizzy feeling.  On the one hand Wang tiles are colorful squares on the other they represent deep ideas about computability and decidability and they can do so in a deceptively pleasing fashion.