5
$\begingroup$

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.

Wang Tile

Improve this question
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – Vor
    Feb 2, 2014 at 10:35
  • $\begingroup$ 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. $\endgroup$
    – nilo de roock
    Feb 2, 2014 at 12:27
  • $\begingroup$ 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. $\endgroup$
    – Vor
    Feb 2, 2014 at 23:17
  • $\begingroup$ 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. $\endgroup$
    – nilo de roock
    Feb 3, 2014 at 8:14
  • $\begingroup$ 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. $\endgroup$
    – nilo de roock
    Feb 3, 2014 at 8:33

1 Answer 1

Reset to default
3
$\begingroup$

(partial answer) via wikipedia, the conversion/reduction of TMs to Wang tiling was 1st proven in this paper, & there are possibly later simplifications:

  • Berger, R. (1966). "The undecidability of the domino problem", Memoirs Amer. Math. Soc. 66 (1966). (Coins the term "Wang tiles", and demonstrates the first aperiodic set of them).
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.