Wang Tiles and Turing Machines

grahamshawcross.com

52 points·gwern··9 comments

These are a very interesting part of Greg Egan's Diaspora: https://en.wikipedia.org/wiki/Diaspora_(novel)

Was going to mention this as well. Really fantastic book.

FWIW the short story that that part of the book is based on is available for under a dollar

Wang's Carpets, by Greg Egan https://www.amazon.com/gp/aw/d/B009ZVKQVS/

Here's another post which goes into more detail about the mapping from Turing machines to sets of Wang tiles: https://moyix.wordpress.com/2012/04/06/computing-with-tiles/

Wang tiles remind me quite a bit of the Game of Life. From the article, tiles were found to be Turing Complete in the '70s.

Wasn't Conway's Game proven to be Turing Complete much later? I find that a little surprising if so.

Yes, with a right set of Wang tiles, once you set a row, there is only one solution for each of the other row, and they can be built using local rules. So it's really like a 1D cellular automaton if you put each time step of the automaton on top of each other.

I can't find an early proof of Turing-completeness of Life. there is a paper from 1974 has all the building blocks [1], but the authors got lazy: “From here on, it is just a matter of engineering to construct an arbitrarily powerful (albeit slow) computer. Our engineer has been given the tools - let him finish the job”

[1]: https://dl.acm.org/citation.cfm?id=811303

Yes http://rendell-attic.org/gol/tm.htm

Magic: the Gathering is also Turing complete.

https://www.toothycat.net/~hologram/Turing/

Got to see these used by Nicolas Schabanel, Damien Woodz and others for DNA (the molecule) computing. Quite mind blowing.

Reply on news.ycombinator.com