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”
These are a very interesting part of Greg Egan's Diaspora: https://en.wikipedia.org/wiki/Diaspora_(novel)
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/
Was going to mention this as well. Really fantastic book.
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.