[7373737373]

Two of the most fascinating open questions about the Game of Life are in my opinion:

1. What is the behavior of Conway's Game of Life when the initial position is random? Paraphrasing Boris Bukh's comment on the post linked below, the Game of Life supports self-replication and is Turing-complete, and therefore can support arbitrarily intelligent programs. So, will a random initial position (tend to) be filled with super-intelligent life forms, or will the chaos reign?

There exist uncountably infinitely many particular initial configurations out of which a random one may be drawn, which makes this more difficult (a particular infinite grid configuration can be represented as the binary digits (fractional part) of a real number, spiraling outwards from a given center coordinate cell: 0.0000... represents an empty infinite grid, 0.1111... a fully alive infinite grid).

https://mathoverflow.net/questions/132402/conways-game-of-li...

2. Relatedly, does a superstable configuration exist? One that continues to exist despite any possible external interference pattern on its border? Perhaps even an expanding one?

https://mathoverflow.net/questions/132687/is-there-any-super...

[jmsgwd]

Your first question is discussed in the book The Recursive Universe by William Poundstone (1984).

One of the chapters asks "what is life?". It considers (and rejects) various options, and finally settles upon a definition based on Von Neumann-style self-replicating machines using blueprints and universal constructors, and explains why this is the most (only?) meaningful definition of life.

Later, it talks about how one would go about creating such a machine in Conway's Game of Life. When the book was written in 1984, no one had actually created one (they need to be very large, and computers weren't really powerful enough then). But in 2010 Andrew J. Wade created Gemini, the first successful self-replicating machine in GoL, which I believe meets the criteria - and hence is "alive" according to that definition (but only in the sense that, say, a simple bacteria is alive). And I think it works somewhat like how it was sketched out in the book.

Another chapter estimated how big (and how densely populated) a randomly-initialized hypothetical GoL universe would need to be in order for "life" (as defined earlier) to appear by chance. I don't recall the details - but the answer was mind-boggling big, and also very sparsely populated.

All that only gives you life though, not intelligence. But life (by this definition) has the potential to evolve through a process of natural selection to achieve higher levels of complexity and eventually intelligence, at least in theory.

[Legend2440]

One problem is that, even though it is turing-complete, many practical operations are very difficult. Patterns tend towards chaos and they tend towards fading out, which are not good properties for useful computation. Simply moving information from one part of the grid to another requires complex structures like spaceships.

You might have better luck with other variants. Reversible cellular automata have a sort of 'conservation of mass' where cells act more like particles. Continuous cellular automata (like Lenia) have less chaotic behavior. Neural cellular automata can be trained with gradient descent.

[jameshart]

‘Random’ configurations are going to be dominated by fixed scale noise of a general 50% density, which is going to have very common global evolutionary patterns - it’s almost homogenous so there’s little opportunity for interesting things to occur. You need to start with more scale free noise patterns, so there are more opportunities for global structures to emerge.

[Someone]

> the Game of Life supports self-replication and is Turing-complete, and therefore can support arbitrarily intelligent programs.

I think people will disagree about whether “Turing-complete” is powerful enough for supporting intelligence but let’s assume it does.

> So, will a random initial position (tend to) be filled with super-intelligent life forms, or will the chaos reign?

Even if it doesn’t, it might take only one intelligent life form for the space to (eventually) get filled with it (the game of life doesn’t heave energy constraints that make it hard to travel over long distances, so I don’t see a reason why it wouldn’t. On the other hand, maybe my assumption that all intelligent life would want to expand is wrong), and in an infinite plane, it’s likely (¿certain?) one will exist.

On the other hand it’s likely more than one exists, and they might be able to exterminate each other.

[jmsgwd]

> it might take only one intelligent life form for the space to (eventually) get filled with it

It wouldn't need to be intelligent to do this; it could be a self-replicating machine with no intelligence at all - which is orders of magnitude simpler and therefore more likely.

Chaotic initial state -> self-replicating machine -> intelligence is much more likely than chaotic initial state -> intelligence.

(See my other reply to the GP comment about The Recursive Universe, where all this is discussed.)

[NuclearPM]

What’s up with the upside down question mark?

[qnleigh]

An interesting thing related to these questions in the context of physics: there was an interesting discussion on Scott Aaronson's blog a few years ago about why the universe should be quantum mechanical. One idea that was brought up is quite related to the open questions you name here.

Here's an excerpt from a comment of Daniel Harlow (a prof at MIT):

> In order for us to be having this discussion at all, the laws of physics need to have the ability to generate interesting complex structures in a reasonable amount of time starting from a simple initial state. Now I know that as a computer scientist you are trained to think that is a trivial problem because of Turing completeness, universality, blah blah blah, but really I don’t think it is so simple. Why should the laws of physics allow a Turing machine to be built? And even if a Turing machine is possible, why should one exist? I think the CS intuition that “most things are universal” comes with baked-in assumptions about the stability of matter and the existence of low-entropy objects, and I think it is not so easy to achieve these with arbitrary laws of physics.

Scott replies:

> Multiple people made the case to me that it’s far from obvious how well

(1) stable matter,

(2) complex chemistry,

(3) Lorentzian and other continuous symmetries,

(4) robustness against small perturbations,

(5) complex structures

being not just possible but likely from “generic” initial data,…can actually be achieved in simple Turing-universal classical cellular automaton models.

See comments 225 and 261

https://scottaaronson.blog/?p=6244

[iamgopal]

in an infinite plane, if we keep adding random points ( similar to sun continuously giving earth low entropy energy ) , eventually, it will reach to intelligent life form, which are very efficient at converting low entropy energy to high entropy energy.

[7373737373]

This would require patterns to emerge that are "radiation-hardened", like https://en.wikipedia.org/wiki/Quine_(computing)#Radiation-ha...

[pontifier]

The thing that blows my mind is: say you start filling the plane with pi. Pi has been proven to contain every finite sequence. That means that somewhere in the plane is a full physics simulation of YOU in the room you are in right now.

Does that you exist any less fully because its not currently in the memory of a computer being evaluated?

[7373737373]

> Pi has been proven to contain every finite sequence

This has not been proven yet: https://math.stackexchange.com/a/216348/575868

(or more generally: https://en.wikipedia.org/wiki/Disjunctive_sequence)

Depending on the infinite grid filling scheme even these properties may not be sufficient to guarantee that every two dimensional pattern is initially generated because the grid is two-dimensional, but the number property is "one-dimensional". A spiral pattern for example may always make it line up in a way such that certain 2d patterns are never generated.

[fsflover]

https://news.ycombinator.com/item?id=36357466

[triggercut]

3. Could it generate it's own GoL forum asking these very questions?