Rule 30 automat - live as problem 254
Back to General discussions forum
I solved about life game and read wikipeadia. I found here simple "cell automats" and this Rule 30 game It is like "life" but 1 dimention. It have line of cells each can be 1 or 0 and next status for each cell is defined by it and its left and right neibor.
If write status of left-it-right as 3 bits, we make binary number from 000 to 111 and the rule is this: if
number is betwen 001 and 100 (x >= 1 && x <= 4) then cell is next generation 1, otherwise is 0.
I don't knew what problem exactly to make. I tried game on "circuler" line, I mean ends on right and left are
concatanete. Exemple with line is 8 cells and random fill, make such change:
-XX---X- - init
XX-X-XXX - step 1
---X-X-- - step 2
--XX-XX- - step 3
-XX--X-X - step 4
-X-XXX-X - step 5
-X-X---X - step 6
and so if I not mistaked. And it become situation can return itself after some steps.
I like the idea. It can also be expanded on by making the problem more complex. For instance, instead of simulating one specific ruleset, we can make the problem for instance ask you to simulate any of the Rule 0-255 variants (The original Rule 30 game is so called because as in the wikipedia article you linked, you can define a rule with an 8-bit binary number).
Also just as a remark, Game of Life can be interpreted in this truth table view as well, except it looks at its neighboring 8 cells plus its own state, making a truth table with 2^9=512 rows, so Game of Life could also be assigned some "rule number" from 0 to 2^512 - 1.
Pearl, Vadim, Hi!
Please, excuse me for delay with answer. Yep, I recently learned about this "automaton" too - and even more, few days ago
I found there is prize of $30k supposed for solving some problems about it - perhaps Vadim can try cracking this? :)
Now, there were few suggestions of problems recently and I'm investigating all this. General idea is that I want to avoid adding "too straightforward" tasks to this site (just to keep less or more constant level of difficulty for reaching "stargazer" rank), so usually I'm trying to figure out some more puzzling version.
On the other hand we have (somewhat forgotten) OpenAbbey site wanting more tasks (of any level). So I think I should revive efforts on it :)
we can make the problem for instance ask you to simulate any of the Rule 0-255 variants
As I understand, most of rules lead to fast degradation of population or some less or more constant changes. And also changing the rule doesn't make problem much more difficult, I'm afraid :) But the idea of looking for loops etc probably is interesting, especially if loop has verly long period... So I just need to put some more efforts into investigation...
Game of Life could also be assigned some "rule number" from 0 to 2^512 - 1
Oh yes, but this is typical example of function which seems to be ok for mathematician but not ok for programmer, right? :)
This reminds me of various engineering cases when we need to create optimized logical function... Like function with 4 inputs and 7 outputs which converts binary number to seven-segment representation :)
Well, it's almost 2 years, but the problem is live now - to implement the algorithm in Turing's Machine (curiously, TM itself was suggested by Vadim in some other post unless I'm mistaken).
I tried to retail the automaton description less or more closely to suggested above.