On April 2, 2000 (I am sure that many people thought it was a joke), Paul Rendell assembled a huge set of cells (the grid is 1714 x 1647) in
Conway's Life that performed as a
Turing Machine. The three major parts of the Turing Machine are a
finite state machine and tape that are linked together by a large group of cells called the 'signal detector'.
The one designed is a rather simple one (as Turing Machines go) that has 3 states and 3 symbols (though he does note it would be fairly easy to expand to a 16 state and 8 symbol machine - this is large enough to implement a Universal Turing Machine).
a b c
0 aR2 cR1 cL0 # find next 'b'
1 cL0 XXX cR1 # write 2x 'c'
2 +++ XXX bR2 # convert 'c' to 'b'
This state table is stored in an array of memory cells with 8 spots in each memory cell which are decoded as 'DWWWSSSS' - Direction (1 = right), WWW as the value to write, and SSSS as next state.
The tape of the Turing Machine is implemented as two stacks. This is conceptually easier to work with in the confines of Conway's Life rather than a single tape that can moved. Instead of "move the tape to the left", the Turing Machine does "push memory to the left stack" and "pop from right stack to memory". The actual part of the 'tape' that is being read doesn't exist in either stack and is instead copied into the reading head of the finite state machine (the program described above).
After the symbol under the tape head has been processed, the value in the signal detector (one of the many parts of the machine) is then copied into each stack's control conversion logic. The logic in the stacks mirror each other so the same instruction (Left, push a) will cause a "push a" to be done in the left stack, while a pop is done on the right stack. What do is done by looking at the 'D' part of the DVVVSSSS message stream which is then sent to two the push control and pop control of each stack.
It takes 1040 generations of the cellular automaton to complete one cycle of the Turing Machine (read, state change, write, and move). Much of the loops within the various components have a cycle of 240 generations long and are synchronized to this. Occasionally, a delay is used to get two otherwise slightly out of sync glider streams together.
While this is interesting for a CA junkie, the implications of it can be quite surprising. Such things as trains at a switching yard or ants in an ant hill have been shown to be cellular automaton, along with even smaller and simpler components such as actual biological cells. If Conway's Life can implement a Turing Machine - then so can an ant hill. If a computer program can ever attain the title of artificial intelligent, then that program on an Turing Machine is too - and also the ant hill (or train yard).
Anything that is capable of being modeled as a cellular automaton has the possibility of preforming the same tasks as any computer.
http://www.rendell.uk.co/gol/tm.htm
(contains the complete pattern and detailed descriptions of every part of the Turing Machine)