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”
9 comments
[ 1.7 ms ] story [ 48.2 ms ] threadWasn't Conway's Game proven to be Turing Complete much later? I find that a little surprising if so.
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
Wang's Carpets, by Greg Egan https://www.amazon.com/gp/aw/d/B009ZVKQVS/
https://www.toothycat.net/~hologram/Turing/