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.

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