3 ms·

Wang Tiles and Turing Machines

52 points by gwern 9y ago

hinkley 9y ago
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.
- progval 9y ago
  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 https://dl.acm.org/citation.cfm?id=811303
- jamesrcole 9y ago
  Yes http://rendell-attic.org/gol/tm.htm http://rendell-attic.org/gol/tm.htm
diego898 9y ago
These are a very interesting part of Greg Egan's Diaspora: https://en.wikipedia.org/wiki/Diaspora_(novel) https://en.wikipedia.org/wiki/Diaspora_(novel)
- anonnel 9y ago
  Was going to mention this as well. Really fantastic book.
- jamesrcole 9y ago
  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/ https://www.amazon.com/gp/aw/d/B009ZVKQVS/
panic 9y ago
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/ https://moyix.wordpress.com/2012/04/06/computing-with-tiles/
ShannonAlther 9y ago
Magic: the Gathering is also Turing complete. https://www.toothycat.net/~hologram/Turing/ https://www.toothycat.net/~hologram/Turing/
agumonkey 9y ago
Got to see these used by Nicolas Schabanel, Damien Woodz and others for DNA (the molecule) computing. Quite mind blowing.

52 points by gwern 9y ago

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.

progval 9y ago
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 https://dl.acm.org/citation.cfm?id=811303
jamesrcole 9y ago
Yes http://rendell-attic.org/gol/tm.htm http://rendell-attic.org/gol/tm.htm

diego898 9y ago

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

anonnel 9y ago
Was going to mention this as well. Really fantastic book.
jamesrcole 9y ago
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/ https://www.amazon.com/gp/aw/d/B009ZVKQVS/

panic 9y ago

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/ https://moyix.wordpress.com/2012/04/06/computing-with-tiles/

ShannonAlther 9y ago

Magic: the Gathering is also Turing complete. https://www.toothycat.net/~hologram/Turing/ https://www.toothycat.net/~hologram/Turing/

agumonkey 9y ago

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