|
|
Rule 110 cellular automaton
The rule 110 cellular automaton is a one-dimensional two-state cellular automaton with the following rule table:
| current pattern | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 | | new state for center cell | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Rule 110, like the Game of Life, exhibits what Stephen Wolfram calls "Class 4 behavior," which is neither completely random or completely repetitive. Localized structures appear and interact in various complicated-looking ways. In the course of the development of A New Kind of Science, Wolfram's research assistant Matthew Cook proved that these structures were rich enough to support universal computation. This is an interesting result because Rule 110 is an extremely simple system, simple enough to suggest that naturally occurring physical systems may also be capable of universality—and hence questions about them will often be undecidable. This means they may not be amenable to closed-form mathematical solutions.
Matthew Cook presented his proof before the publication of A New Kind of Science at a Santa Fe Institute conference, which Wolfram Research claimed was a violation of Cook's nondisclosure agreement. The proof was stripped from the proceedings by court order. Nevertheless the proof's existence became known. However, the interest it generated was primarily about the technical details of its construction, rather than the significance of its existence--and hence of a considerably different character from its treatment in the book NKS.
Since the publication of A New Kind of Science, Matthew Cook has been preparing a paper giving the complete proof, whose publication is pending.
http://upload.wikimedia.org/wikipedia/en/f/fa/CA_rule110s.png
An example run of a rule 110 cellular automaton
Explanation of Universality Proof
This article is licensed under the GNU Free Documentation License at http://www.gnu.org/copyleft/fdl.html
You may copy and modify it as long as the entire work (including additions) remains under this license.
You must provide a link to http://www.gnu.org/copyleft/fdl.html
To view or edit this article at Wikipedia go to http://www.wikipedia.org/wiki/Rule_110_cellular_automaton
|
©
2005 Music
Entertainment Network. A Cyprus
Roussos Music Entertainment Company. All Rights Reserved.
Articles
from
Wikipedia
Encyclopedia
are licensed under the GNU Free Documentation License. You may copy and
modify it as long as the entire work (including additions) remains under
this license. You must provide a link to http://www.gnu.org/copyleft/fdl.html.
All text is available under the terms of the GNU Free Documentation License.
All trademarks and service marks including Napster,
Rio
MP3 Player, iRock,
Creative
MP3 Player, iRiver,
Apple iPod
Portable
MP3 Players + iTunes,
eMusic,
Guitar
Center Musicians
Friend, Zzounds
Musical Instrument Equipment Store, BMG
Music Service, Columbia
House DVD Club, eBay,
Amazon,
Netflix,
Jamster,
Gamefly,
Friendster,
Music123
Musical Instruments, Billboard,
MTV,
Yahoo
Launch, Overture
Yahoo Search Marketing, MusicMatch,
Kazaa,
Kazaa
Lite, Morpheus
software, Real
Rhapsody, Bose,
Sheet
Music Plus, Billboard
Magazine, Rolling
Stone Magazine, Walmart
Downloads, Barnes
and Noble book store, CDUniverse,
Tower
Records, MSN
Music, MySpace,
Limewire,
WinMX,
Google
Adsense, Alibris,
TicketsNow,
MusicSpace,
uBid
are property of their respective owners. Music.us has no affiliation with
MySpace
or Friendster,
but offers alternative services. Disclaimer: Uploading or downloading
of copyrighted works without permission or authorization of copyright
holders may be illegal and subject to civil or criminal liability and
penalties. Please buy
music and refrain from any illegal downloading activity. User
submitted free content, including Wikipedia encyclopedia or modification
thereof by end users, do not reflect the views and opinions of Music.us
and are for educational and research development purposes. Our website
offers advanced search for bands and artists bio and albums and browse
options for artist band biographies resources and information. We offer
blogs and community building tools for authors, bands and users. The Music.us
Entertainment Network is web's most comprehensive one-stop shopping, community
networking and education site. Find song lyrics, guitar tablature, posters,
ring tones, free MP3 downloads and hourly updating news feeds on musicians
and any genre style including rock,
pop,
hip
hop, country,
christian,
rap,
classical,
folk,
dance,
latin,
R
and B, blues,
punk,
heavy
metal, alternative,
guitar,
bass,
drums,
gospel,
wedding,
arabic,
jazz,
soundtrack,
world,
reggae,
soul
and more. Privacy Policy
- Site Map
- MP3 - Music Downloads
- Song Lyrics
| |
