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

488 Views Asked by At

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?