1
$\begingroup$

I've read numerous links on the fact that wang tiles are turing complete, and details about them (links at end).

However there is little talk of how to actually place the tiles. One place i read mentioned (paraphrasing) "by placing tiles only where they are uniquely able to fit, you'll evaluate the program", but I'm finding there is actually ambiguity in what tiles can fit where.

Another link mentions that they personally place tiles in a spiral pattern, and when they hit a spot that needs a tile which doesn't exist (isn't valid) they backtrack and make a different choice earlier on.

Does anyone know if there's any reliable algorithm for placing the wang tiles when simulating turing machines with wang tiles?

I first believed that i could just go tile by tile, systematically matching empty spots to tiles that would fit there, but there are times when it is ambiguous which tile should go there.

Please let me know if more information is needed, such as a specific case when it's ambiguous, and I will provide it. Thanks!

Links I've read include: http://www.math.oregonstate.edu/~math_reu/proceedings/REU_Proceedings/Proceedings1989/2_Michie89.pdf

https://moyix.wordpress.com/2012/04/06/computing-with-tiles/

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

http://grahamshawcross.com/2012/10/12/wang-tiles-and-turing-machines/

https://because0fbeauty.wordpress.com/2014/02/28/wang-tiles-1/

$\endgroup$
1
$\begingroup$

Any proof that the Wang tiling problem is undecidable by reduction from undecidability of the halting problem of Turing machines will contain instructions on how the Wang tiles simulate the operation of the machine, and indeed a proof that a tiling exists if and only if the machine doesn't halt.

There is more than one such proof. If you look at different proofs, you will see different reductions. There is absolutely no reason to expect that different reductions correspond to the same tiling placements. Indeed, there is no canonical way of converting Turing machines to tiling problems. Therefore there is no "reliable algorithm" for the problem; any specific proof should include such an algorithm that works for the specific proof.

I suggest you try to look up a technical paper with such a proof. Perhaps you can find a university library with Berger's original paper, or one of the later papers cited in the Wikipedia article.

$\endgroup$
3
  • $\begingroup$ just to verify, the algorithm of PLACING the tiles depends on the algorithm that the tiles are simulating? I think that's what you've said but just want to verify that there is no general algorithm for placing the tiles, once you have the specific tiles needed worked out. Thanks! $\endgroup$ – Alan Wolfe Mar 13 '16 at 23:12
  • $\begingroup$ That's right, the algorithm of placing the tiles, though I wouldn't necessarily call it an algorithm. $\endgroup$ – Yuval Filmus Mar 13 '16 at 23:14
  • $\begingroup$ That is super disappointing but thanks for the info and I'll read up on what you suggest. $\endgroup$ – Alan Wolfe Mar 13 '16 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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