# How to convert a Turing Machine program to a tiling using Wang Tiles?

This is a cross-post from a post on MathSE due to lack of answers.

To illustrate my question I provide the following example.

The website Online Turing Machine provides a Turing Machine simulator. The following program adds 1 to any binary number.

q0,1  =>  q0,1,>
q0,0  =>  q0,0,>
q0,_  =>  q1,_,<
q1,0  =>  q3,1,>
q1,1  =>  q1,0,<
q1,_  =>  q3,1,>


A program line has the following format:

state, character read => new state, character written, direction tape


In the program above q0 is the initial state and q3 is the accepting state.

In Tilings and Patterns by Gruenbaum and Shephard, 11.4 "Computing By Tiles" I read that it is possible to convert any turing machine program to a tiling of the plane using Wang tiles. The book contains an example tiling which calculates the Fibonacci numbers. The procedure, recipe, to convert a Turing machine program to a set of Wang tiles is not entirely clear to me.

Question: What is the algorithm to convert a Turing Machine program line by line to a set of tiling of the plane using Wang Tiles? And how does it work on the Turing machine in the given example?

Update:

Image is that of a Wang tile that adds 1 to a binary: 111 + 1 = 1000 where 1 is red, 0 is cyan. Aiming to generate tiles like this from any Turing Machine. First row 111, last row 1000.

• You can first try to build a simpler tile program that simulates a Turing machine that converts all 1s in the tape to 0s, return to leftmost symbol and halt. – Vor Feb 2 '14 at 10:35
• It's just that the examples given in the book aren't entirely clear to me. It's not really explained how to get from a line of tape ( of the TM ) to a row of ( Wang ) tiles. – nilo de roock Feb 2 '14 at 12:27
• You can take a look to this paper: Computing with Tiles or this site: Computing with tiles. If you still have doubts, let us know. – Vor Feb 2 '14 at 23:17
• I read the paper and am familiar with the website, I did my searches. The first does provide what I am looking for on page 5. ( They refer to and extend Grunbaum/Shephard. ) I tried to convert the program in my post using the page 5 rules but it's where I get lost. I don't understand their example on page 7 either. The example on page 8 comes straight from Grunbaum/Shepherd Chapter 11.4. - On the website they also use an exact example from GrSh but rotated it somehow. Again, I can't reproduce it from the rules. – nilo de roock Feb 3 '14 at 8:14
• TO @Raphael who edited the post: I provided the Turing Machine program in such a way that it can be copy/pasted in the Turing Machine Simulator for immediate viewing / demonstration of the program. – nilo de roock Feb 3 '14 at 8:33