Wang pointed out that it is possible to find sets of Wang tiles that mimic the behaviour of any Turing Machine (Wang 1975).
A Turing machine can compute all recursive functions, that is functions whose values can be calculated in a finite number of steps. That is to do, however inefficiently, what any conceivable computer can do.
The basic idea is to use rows of tiles to simulate the tape in the machine, with successive rows corresponding to consecutive states of the machine.
The following examples are based on those in “Tiling and Patterns” (Grünbaum and Shephard 1987) with coloured tiles replacing numbered tiles, and initialisation somewhat simplified.
Simple Addition Using Wang Tiles
This example uses one quarter of the plane, bounded by grey tiles, it shows the addition of two positive integers, a and b, and for convenience it is assumed that 2 ≤ a < b.
In this slightly simplified presentation step 1 consists of placing tiles to indicate the numbers to be added together (5 and 9 in this case) and a start signal in the top left-most square.
Step 2 then consists of adding the only possible tiles next to those that have already been placed and step 3 shows the signal beginning to take a diagonal path downwards. This continues, using tiles from column B, until it meets the tiles descending from the first number, with tiles from column C. At the meeting point a series of horizontal tiles, from column D, is generated which changes direction when it meets the tiles descending from the second number. The signal then moves diagonally upwards, using tiles from column F, until the process terminates at the top edge where its position indicates the required answer.
The colour numbers above are those used by Grünbaum and Shephard and the tiles are the same except that a missing one has been added and the tiles have been arranged in a slightly different manner. Incidentally using coloured tiles rather than numbered ones meant that the missing tile was much easier to spot.
Generating the Fibonacci Sequence
The following example is presented without a complex narrative. It shows all the steps on one diagram, follows a similar method to the previous example and is otherwise I think self explanatory.
Diagram above corrected 08/05/2015
Generating Prime Numbers
The final example illustrates the ingenuity that can be required to carry out some computations, it is due to E. F. Moore and M. Fieldhouse and was communicated to Grünbaum and Shephard by H. Wang. Here the only change I have made is to use colours rather than colour numbers.
The tiling uses 30 prototiles and forces a tiling that places tiles marked P or C at the prime and composite positions in the top row. The tiles are marked with letters as well as being coloured and it can be seen that they build up blocks of squares which increase in size downwards. These square blocks are indicated by thickened lines.
The tiles marked by an asterisk are used to generate the blocks down the left boundary and the tiles with superscript C transmit a signal to the effect that the number is composite. These composite signals are generated by the tiles by B* (which is only used once) and D4 (which occurs on the top right corner of each square block that does not abut on the left boundary of the tiling). They are absorbed by the tiles C on the top line, and D6 on the bottom right corner of certain blocks. When the signal is absorbed in this way it is regenerated higher up by a D4.
The increasing blocks signal to the top row when a number has a proper divisor greater than 2. Divisibility by 2 is taken care of by alternating A and B tiles in the second row. Either can transmit the composite signal. The special tile B* is introduced simply to ensure that a prime tile P appears in position 2. This does however seem to introduce a degree of circularity.
The use of colours again revealed an error in the designation of one edge of the bottom right tile in the tile set.
grahamshawcross.com 
I think there is at least one more error in Grunbaum and Shephard. Your fix for D6c doesn’t fully correct the problem, since it allows tilings like:
D1 D2 D2 D4 D1 D4 D1
E F G D5 E D6c E
G E F D5 G Gc G
G G E D6 G Gc G
That is, your corrected D6c can appear anywhere there is an E to the left and a Gc rising from below. (The original is even worse: it can appear anywhere there is a G to the left and a Gc rising from below!) Once the D6c is placed, the ‘3’ color on its top allows D5* D4 to be placed above it, and the D4 will slot in anywhere on an existing D row. The basic problem seem to be that nothing constrains the D6 tiles to be anchored above the D row, so the E/F diagonal can be any length.
The simplest solution I can see is to introduce 2 more colors and 4 more tile types in order to anchor the “bottom” G/E/D6 row directly above the D1/D2/D4 row. We cheat a little bit and reuse color “8” because it is not otherwise used on the top/bottom of tiles, so we really need only to introduce one new color “12”. Tiles A, B and D6 now have 8 on the bottom, and D1, D2, and D4* have 8 on the top. Tile Ac and Bc have 12 on the bottom and D1c, D2c, D4, and D6c have 12 on the top. New tiles Eb and Gb are identical to E/G except they have 8 on the bottom. New tiles Ebc and Gbc are identical to Ec and Gc except they have 12 on the bottom. (Your fix for the left hand edge of D6c is also needed; it should be 4.)
This ensures that D6/D6c occur in a “bottom” row with Eb, and seems to fix the problem: at least my tile solver program doesn’t seem to be able to generate an incorrect assignment of primes and composites any more.
LikeLiked by 1 person
Small typo above: D6c has 12 on the *bottom*, 3 is on the top.
LikeLiked by 1 person
Scott, Thanks for your comments.
I am in the latter stages of submitting my PhD thesis so am very preoccupied with that at the moment but will make changes as soon as I have submitted. Your tile solver program sounds intriguing.
LikeLike
Pingback: New top story on Hacker News: Wang Tiles and Turing Machines – ÇlusterAssets Inc.,
Pingback: Wang Tiles and Turing Machines – posted at April 20, 2018 at 11:00PM by gwern – Startup News 2018
Pingback: New top story on Hacker News: Wang Tiles and Turing Machines – Technical Nair
Pingback: New top story on Hacker News: Wang Tiles and Turing Machines – Tech + Hckr News
Pingback: New top story on Hacker News: Wang Tiles and Turing Machines – Latest news
Thank you for the great article!
I can see how the above examples do computations, however I don’t believe they are still (simulating) Turing machines so was wondering if you could speak to that. If the top row is the initial state of the turing machine, and the machine evolves downward in time, it looks as though your turing machine is able to time travel and write values to the tape of previous points in time. For instance, note in your addition example that by the end of the execution, the answer is in the time = 0 row of data, even though it wasn’t present when the simulation really was at time = 0. Is this still somehow considered a Turing machine? If not, does this have any other names, as it obviously still does useful calculations?
And another question… are there any algorithms that you know of to place the tiles as you do the calculations? Doing it from top row to bottom row, left tile to right in each row, and only choose whatever tile fits the edge requirements, there are times when the tile to place is ambiguous (has more than one answer), however further down the line you will hit a situation where there is no valid tile placement so you will have to go back and try a different choice where the tile was ambiguous. It seems a bit like trial and error, and I’m wondering if you might ever have to go back quite a distance to rectify a situation, or if even you might ever have to go back to a previous row. If so, do you know of any better algorithms for making valid tiling? Or does this essentially come down to the halting problem so is unsolvable in general other than this systematic trial and error method.
Posted on behalf of Alan Wolfe
LikeLike
Hi Alan
Thanks for your email, which requires some more thought on my part.
The two parallel situations that I have immediately in mind are the Game of Life acting as a computer and Jacquard looms and weaving in general.
The Game of Life can be initialised to provide a Glider Gun that fires out Gliders that can move and be destroyed by a Glider Eater
These can be configured to create a computer that can perform in the same way as any conventional computer in particular with the following logical operators.
My admittedly rather weak argument is that if the Game of Life can be configured to create an all purpose computer then it has the same functionality as a Turing Machine and can be considered to be one. It does not need to use any of the specific mechanisms specified by Turing.
LikeLike
It has been pointed out by a few people that the Fibonacci example has some missing tiles between columns 5 and 8 where there should be a rising diagonal. This will be corrected shortly, thanks to your comments
LikeLike
You may find this interesting http://en.wikipedia.org/wiki/Cellular_automaton
LikeLiked by 1 person
Nate: This jogged my memory and introduced me to some new ideas, thank you
LikeLike
Pingback: 1 – Wang Tiles and Turing Machines (2012) | blog.offeryour.com
Pingback: 1p – Wang Tiles and Turing Machines (2012) | Profit Goals
Pingback: 1p – Wang Tiles and Turing Machines (2012) | Exploding Ads
Fascinating! Thanks for sharing this!
LikeLike
what’s up with all the missing tiies in the image for fibonacci?
LikeLike
Hi quintopia
I don’t think there are any missing tiles in the fibonacci example, but all the steps down and back up the page are shown on one diagram rather than in separate rows as in the addition example. The idea is to fill the top and left hand edges with grey edged tiles and then seed the two top left hand tiles (marked with black arrows) all the other placements are then automatic (forced). You might ask where the first 1 is in the series is though, that really should be 1,1,2,3,5,8,…….
The example was taken from Grünbaum and Shephard “Tilings and Patterns” page 606 where the tile edges are numbered rather than coloured. Their colour numbers are shown in the tile palette.
LikeLike
My belated apologies for not seeing the missing Fibonacci tiles. Following other comments I have corrected the image.
LikeLike
Graham. It’s all mathematical. I appreciate there can be beauty in numbers, its just I cannot see them.
How about some clever patterns which can be appreciated on an aesthetic level?
Too simple?
Good to see you are doing mind stretching stuff.
Phil
LikeLike
Hi Phil
Nice to hear from you.
There is a post called “Aesthetics of Aperiodic Tiling” which has some pretty (I think) pictures.
You are always welcome in Edinburgh.
Best Regards
Graham
LikeLike