The Cook Book

Recipe for the week of June 19 - 25

Fredkin's Reversible Cellular Automata

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.

Take me higher...
Introduction to the PSK PSK Search Recent Additions CA Archive CA Links Feedback Appreciated !