Wang tile turing machine tile placement

Question

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/

Answer 1

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.