Description: Wolfram offers $30,000 in prizes for the answers to three basic questions about the complexity of cellular automaton rule 30. Does the center column always remain non-periodic? Do black and white occur on average equally often? Does computing the nth cell require at least O(n) computational effort?
How can something that simple produce something that complex ? It’s been nearly 40 years since I first saw rule 30 —but it still amazes me. Long ago it became my personal all-time favorite science discovery, and over the years it’s changed my whole worldview and led me to all sorts of science, technology, philosophy and more .
But even after all these years, there are still many basic things we don’t know about rule 30. And I’ve decided that it’s now time to do what I can to stimulate the process of finding more of them out. So as of today, I am offering $30,000 in prizes for the answers to three basic questions about rule 30.
The setup for rule 30 is extremely simple. One’s dealing with a sequence of lines of black and white cells. And given a particular line of black and white cells, the colors of the cells on the line below are determined by looking at each cell and its immediate neighbors and then applying the following simple rule: