Hacker News new | ask | show | jobs
by OscarCunningham 1291 days ago
There are still plenty of open problems! Here are some of my favourites:

* Is there an oscillator of every possible period? (We have them all except 19 and 41.)

* If you start off the entire plane in a random starting state, does its density tend to a limit as time goes to infinity?

* Is there a 'phoenix' oscillator, in which every live cell dies every generation, of period greater than 2?

* Can every pattern be destroyed by bombarding it with gliders?

* Is there an indestructible pattern?

At the moment people are working on building a spaceship which is only 1 cell tall in its starting state: https://conwaylife.com/forums/viewtopic.php?f=2&t=2040.

1 comments

I'd be surprised if there was a computable density limit for the random plane, just because the system is Turing complete so the answer could easily end up being like Chaitin's contant where it depends on halting problems. For example, note that an infinite random plane will contain, with probability 1, purely-by-chance prebuilt artificial intelligences with goals like "maximize number of blinkers in the plane". Though I guess it's also an open question if such a system could even survive and spread, as opposed to just getting eventually crushed by the surrounding noise.
Right, but I'm hoping it might be possible to prove that the limit exists (even if it's an uncomputable number), as opposed to some oscillating behaviour where the density infinitely often goes up to 70% and then back down to 30% for example.
If it can be proven that there are no indestructible patterns, your AI can clean up everything around it!

(... and encounter other AIs that act as hegemonising swarms, eg. that populate the plane with copies of themselves)