Interesting Properties
Among the 88 possible unique elementary cellular automata, Rule 110 is the only one for which Turing completeness has been proven, although proofs for several similar rules should follow as simple corollaries, for instance Rule 124, where the only directional (asymmetrical) transformation is reversed. Rule 110 is arguably the simplest known Turing complete system.
Rule 110, like the Game of Life, exhibits what Wolfram calls "Class 4 behavior", which is neither completely stable nor completely chaotic. Localized structures appear and interact in various complicated-looking ways.
Matthew Cook proved Rule 110 capable of supporting universal computation. Rule 110 is a simple enough system to suggest that naturally occurring physical systems may also be capable of universality— meaning that many of their properties will be undecidable, and not amenable to closed-form mathematical solutions.
Read more about this topic: Rule 110
Famous quotes containing the words interesting and/or properties:
“What is most interesting and valuable in it, however, is not the materials for the history of Pontiac, or Braddock, or the Northwest, which it furnishes; not the annals of the country, but the natural facts, or perennials, which are ever without date. When out of history the truth shall be extracted, it will have shed its dates like withered leaves.”
—Henry David Thoreau (1817–1862)
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)