I wanted to play with cellular automata for a while. When I saw the post about the contest, it finally got me into gear and I had some fun with rule 30:

https://brunni.de/findings30/

From the abstract:

The usual pattern starting from a single cell with state 1 / black is examined. It is contructed from a richer structure which yields a progression of polynomials for diagonals from the right. It is shown that each diagonal from the left can be expressed by the progression of polynomials for diagonals from the right and how the connection between left and right diagonals forces the diagonals from the left to eventually become periodic.

The necessary and sufficient condition for period doubling of diagonals from the right is established. It is also shown that periods cannot decrease. The result suggests that predicting period doubling is computationally expensive.

I suppose there is nothing new in there?

Hi Graham,

it seems that one needs a LinkedIn account to access that document. I suggest to change that.

Michael

It's hard to tell if it's new, Michael. Can you explain here a little more about what you've done?

Usually there will at least be a part of something like this that's new.

Thanks!

hi Todd,

what do you need to calculate a cell in a diagonal? The previous cell in that diagonal and two cells from the previous two diagonals. This enables one to define diagonals recursively. For diagonals from the right, the recursive definition leads to a simple picture: The previous two diagonals are combined with OR and the resulting values are combined with XOR - basically a summation over the combination up to the cell you need. It is this summation modulo 2 that causes the period doubling. I show that it will either double the basic period of the combination or leave it untouched. But combining the previous two diagonals with OR may decrease the basic period - so I also show that this cannot happen in diagonals from the right.

This is what may be new - I don't know. The rest should be well known stuff - maybe looked at from a different viewpoint. Using a richter structure by replacing A OR B with A+B+A*B did not yield any really interesting results IMO but I left it in the article because it was my starting point.

Thanks, yes, that sounds familiar from a talk Eric Rowland gave. It is pretty neat though, and yeah, a little hard to explain in words.