CELLULAR-AUTOMATON GROWTH ON Z2 - THEOREMS, EXAMPLES, AND PROBLEMS

We survey the phenomenology of crystal growth and asymptotic shape for two-dimensional, two-state cellular automata, in the most tractable c ase of Threshold Growth, a detailed rigorous theory is available. Othe r less orderly examples with recursively computable updates illustrate the broad range of behavior obtained from even the simplest initial s eeds and update rules. Still more exotic cases seem largely beyond the scope of exact analysis, but pose fascinating problems for experiment alists. The paper concludes with a discussion of connections between d eterministic shape theory and important corresponding questions for sy stems with random dynamics. (C) 1998 Academic Press.