Conway's Game of Life as a Turing Machine:
An amazing aspect of a game of life grid is that you can implement
Turing Machines using these simple rules. And people have actually done it! To see how this can be done, first we must know that there are certain
patterns that, if put in a game of life grid, will repeat themselves. A pattern that moves across the grid in a predictable course is called a
glider. These gliders can also
interfere with each other destructively. So one can program gliders so that when they hit another glider, both disappear.
These gliders can be generated by
glider guns. A
glider gun is simply a pattern that , while following the
rules to the game of life, spawns a glider off of itself in a set path every so often. So, for instance, say we have a glider gun in a game of life grid that shoots a glider off every second (think
clock tick). We could implement a
not gate very easily. If we shoot another glider into the path of the not gate, it will be
destroyed, and no gliders will emerge. However, if no glider interferes, a glider will emerge unharmed. This is the principle of a
not gate. Now it is trivial to implement an
and gate, an
or gate, etc. These are the building blocks of a modern
Von Neumann architecture.
Memory cells can be modeled using a series of glider guns as well, and they can be queried, or stream their output. It always amazes me when people go back to the primordial building blocks of
modern computers, and I think that it is extremely educational to look at cases like this.
Thanks go to
Damian Conway for his excellent talk on
Life, the Universe, and Everything, but all misunderstandings/inaccuracies are my fault. For an example of someone actually doing this, see
http://rendell.uk.co/gol/tm.htm