Wang Tiles and Turing Machines

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.

 
/Users/grahamshawcross/Documents/blog_drafts/Wang Tiles and Turi

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.

Bibliography

Grünbaum B., Shephard G. C. (1987)
Tilings and Patterns
W.H. Freeman and Company
New York
 
Wang H. (1975)
Notes on a class of tiling problems
Fundamental Mathematics 82(1975) Pages 295-305
 
Robinson R. (1971)
Undecidability and nonperiodicity for tilings of the plane
Inventiones mathematicae Vol 12, Pages 177-209

About Graham Shawcross

Architect PhD student at Edinburgh University Interested in order, rhythm and pattern in Architectural Design
This entry was posted in Aperiodic Tiling, Architecture, Geometry, Tiling, Turing and tagged , , , , . Bookmark the permalink.

14 Responses to Wang Tiles and Turing Machines

  1. 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

    Like

    • 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.

      Like

  2. 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

    Like

  3. Pingback: 1 – Wang Tiles and Turing Machines (2012) | blog.offeryour.com

  4. Pingback: 1p – Wang Tiles and Turing Machines (2012) | Profit Goals

  5. Pingback: 1p – Wang Tiles and Turing Machines (2012) | Exploding Ads

  6. Jakob Thomsen says:

    Fascinating! Thanks for sharing this!

    Like

  7. quintopia says:

    what’s up with all the missing tiies in the image for fibonacci?

    Like

    • 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.

      Like

    • My belated apologies for not seeing the missing Fibonacci tiles. Following other comments I have corrected the image.

      Like

  8. Phil says:

    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

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s