Parallel Computing
597
Figure 305: The Fredkin automaton, after 8 transitions from the initial pattern
4 •••
For the Fredkin automaton, make a conjecture about the reproduction time as a
function of the number of cells to be reproduced.
5 ••
Show that any Turing machine can be simulated by an appropriate cellular
automaton.
6 •••• Write a program to simulate Life on an unbounded grid. This program will have
to dynamically allocate storage when cells become living that were never living
before.
7 ••••• A "garden-of-Eden" pattern for a cellular automaton is one that cannot be the
successor of any other state. Find such a pattern for Life.
Do'stlaringiz bilan baham: