Stephen Wolfram's: A New Kind of Science | Online
Jump to Page
Look Up in Index

Chapter 9 Notes > Section 10 > Page 1035 > Note (b) Previous note-----Next note
Notes for: Fundamental Physics | The Sequencing of Events in the Universe

*"Firing squad" synchronization

By choosing appropriate rules it is possible to achieve many forms of synchronization directly within cellular automata. One version posed as a problem by John Myhill in 1957 consists in setting up a rule in which all cells in a region go into a special state after exactly the same number of steps. The problem was first solved in the early 1960s; the solution using 6 colors and a minimal number of steps shown on the right below was found in 1988 by Jacques Mazoyer, who also determined that no similar 4-color solutions exist. Note that this solution in effect constructs a nested pattern of any width (it does this by optionally including or excluding one additional cell at each nesting level, using a mechanism related to the decimation systems of page 909). If one drops the requirement of cells going into a special state, then even the 2-color elementary rule 60 shown on the left can be viewed as solving the problem--but only for widths that are powers of 2.


Page image


Pages related to this note:


All notes on this page:

* Sequential cellular automata
* Intrinsic synchronization in cellular automata
* "Firing squad" synchronization
* Distributed computing
* String transformations
* Parallel universes
* Many-worlds models
* All notes for this section
* Downloadable programs for this page
* Downloadable images
* Search Forum for this page
* Post a comment
* NKS | Online FAQs
From Stephen Wolfram: A New Kind of Science [citation] Previous note-----Next note