2
votes
1answer
50 views

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

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,> ...
5
votes
1answer
859 views

Easy proofs of the undecidability of Wang's tiling problem?

Wang tiles are (by Wikipedia): "equal-sized squares with a color on each edge which can be arranged side by side (on a regular square grid) so that abutting edges of adjacent tiles have the same ...