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/

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top