- This week's soup shows a reversible CA discussed by Toffoli and Margolus in
Chapters 6 and 14 of their book Cellular Automata Machines, MIT
Press, 1987. The idea goes back to Ed Fredkin, one of the pioneers of the
field. A CA is reversible if it admits inverse CA dynamics that run time
backwards. The recipe for our 4-color soup, one of the standard CAM8 demos, starts
from a Red Square on a black background, evolving elaborate kaleidoscopic
patterns reminiscent of San Francisco's Fillmore Auditorium ca. 1968. The
dynamics act independently on the inside and outside of the square, so its
boundary remains discernible over time.
- As a dramatic CAM8 demo one can run the light show for several minutes,
then reverse time to recover the original red square. Then one can repeat
the forward run, modify one pixel in the 512 by 512 array, reverse time
again, and no longer detect any trace of the red square. This sequence
of forward and backward updates argues convincingly that CAM8 can compute
at its breakneck speed without error, while also showing that Fredkin's
rule enjoys sensitive dependence on initial conditions.
- The folks at MIT and elsewhere use reversible CA dynamics as toy models
for physics. Applications to image processing and cryptography also come to
mind. If you try to construct such an update rule on your own, you'll be in
for quite a challenge. But see the CAM book for an extremely simple yet clever
construction that generates a large family of so-called 'second order'
models.
|
