4. Parallel Computing 14. Introduction

Figure 304: The Fredkin automaton, with an initial pattern

---

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.