$30,000 For Rule 30
Written by Mike James   
Wednesday, 02 October 2019

Stephen Wolfram has just announced a prize for three proofs concerning Rule 30. What is Rule 30 and why is it so interesting?

Cellular automata are very simple computing systems. You have a set of rules that are applied at each step and you watch initial configurations evolve. The best known example is the 2D Conway's Life, but Stephen Wolfram studied and classified a simpler 1D set of rules.

The idea of a 1D CA is no different from a 2D one, but we start off with a line of cells and at the next tick the line is replaced by a new line determined by the rule that is being followed.

As this is only a 1D arrangement, we don’t actually have to replace the existing line, just display the new line underneath, so building up a complete pattern of the development of the CA. It’s also possible to specify the rule in terms of the color of the cell, its two neighbors and the color of the new cell just below.

For example the pattern:

fig3

specifies a rule that if a cell is white and has two black neighbors then the cell below should be black.

As there are only eight possible arrangements of neighbors, a complete rule that specifies exactly what should happen in any situation only has to list if the result of each of the eight is black or white.

By thinking of black as 1 and white as 0 you can give each neighbor pattern a number between 0 and 7 and then read off the resulting black or white cell on the next row as a set of eight zeros or ones, i.e. a binary number. This can be used as an index to specify the rule.

fig4

This means you can refer to any of the 256 rules that are possible in a 1D CA by number. This in itself is something of a conceptual breakthrough, because now you can begin to think about classifying the behavior of each of the possible rules.

Of all of the rules that we can look at, the most interesting is Rule 30, yes I know it is a shame it wasn't rule 42.

rule30

Rule 30 seem to produce a pseudo random pattern. Why is this interesting? Because complex behavior from such a simple rule is unexpected. This is what you get starting from a single black cell:

rule30output

Yes there is regularity on the left, but on the right the pattern looks complex and it continues to evolve without repeats as the the number of generations increases.

There are so many things we don't know about cellular automata and Wolfram has picked three theorems that need proofs for Rule 30. The prize is $10,000 for each one:

Problem 1: Does the center column always remain non-periodic?

In other words, can you prove that the center column never repeats or prove that it is eventually periodic. Computer simulation has already indicated that it doesn't become periodic after one billion steps.

Problem 2: Does each color of cell occur on average equally often in the center column?

If you compute the ratio of black to white cells this seems to converge to 1 as the number of generations increases, but is it exactly 1?

Problem 3: Does computing the nth cell of the center column require at least O(n) computational effort?

The direct way of computing the nth cell by simulation is O(n2), but is there a shortcut?

It is surprising that not only isn't it clear how to even approach these problems, it also seems that we have little idea how difficult they are. It may take the invention of some new mathematical or computer techniques to even get a start. It might be that the solutions are obvious and all we need is some genius to look at the problems in a new way.

You might not think that $10,000 is a lot for such a problem. It certainly isn't up there with the $1 million offered for the P=NP problem, but solve any of the rule 30 problems and people are going to take notice of you. Cellular automata have been proposed as the basis for a new physics, but the problem is we can't work with them. Answers to questions like these may push math and physics on to the next important theory.

Details of the the prize and exactly what you have to do  is on its web page and Wolfram has a blog post which fills you in on his thoughts on the matter and this makes essential reading if you are thinking about trying any of the problems.

 rule30site

More Information

Announcing the Rule 30 Prizes

https://www.rule30prize.org/

Related Articles

Cellular Automata - The How and Why

The Universe as a Computer

A New Computational Universe - Fredkin's SALT CA

A Computable Universe - Roger Penrose On Nature As Computation

A New Kind of Science Is Ten

The Meaning of Life

Spreadsheets are special

SmoothLife - A Continuous Conway's Life       

Life in Silverlight 4

Life in WPF

It's life but not ...

Brain-like computing?

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

 

Banner


SnapCode: A Java IDE for the Web
27/02/2024

Thanks to CheerpJ and WebAssembly you can now run a Java IDE inside your browser and local first.This is SnapCode, and while lightweight and in-browser, is to be not underestimated.



100 Episodes of 5mins of Postgres
08/03/2024

The popular PostgreSQL explainer series is celebrating its 100th release and beyond. Let's take a look at what it makes it so special.


More News

raspberry pi books

 

Comments




or email your comment to: comments@i-programmer.info

Last Updated ( Thursday, 03 October 2019 )