News for hackers. Stuff that matters.
Re:Theory of self-reproducing automata (1966) by no_gravity on Sunday March 10, 2019 @03:59PM (#19354045)
I wonder if there are estimates out there about how long a randomly generated game of life instance of NxN cells will take until a self-reproducing structure appears. An event that we have not witnessed so far.

Somehow I feel it is related to the question how likely it is for a planet/galaxy/universe to breed life. An event that we have "witnessed" just once so far.

One way to divide it into two estimates:

c = Number of cells of the smallest possible self-reproducing structure

i = Number of new structures that are created on average for each iteration

Then a rough guess could be that it takes 2^c/i iterations.

Re:Theory of self-reproducing automata (1966) by nabla9 on Sunday March 10, 2019 @04:51PM (#19354409)
It's rule dependent.

In Conway's game of Life, known replicators are very large (gliders that destroy the original don't count as replicators) and randomly generating one of those would be take astronomical timescales. It's possible that there are smaller replicators.

In Highlife (slight rule variation) there is replicatior withing in 6×6 box. There are only 2^36 different states in 6x6 box. With random sampling it would take some time but would eventually emerge.

Re:Theory of self-reproducing automata (1966) by Isamu on Sunday March 10, 2019 @08:49PM (#19355830)
Funny enough I found the HighLife replicator just by browsing through some randomly initialized runs. I think it is small enough to arise from random junk fairy often.

But I was deliberately browsing variants of Conway’s rule that supported the glider at least and maybe some of the other familiar objects.

Re:Theory of self-reproducing automata (1966) by whatshisface on Sunday March 10, 2019 @04:53PM (#19354421)
Randomly initialized life quickly collapses into stable structures, most of the time. Modeling it as if it continually permuted randomly though possible states does not fit how it really tends to work in practice.
Re:Theory of self-reproducing automata (1966) by no_gravity on Monday March 11, 2019 @06:30AM (#19357893)

    Randomly initialized life quickly collapses
    into stable structures, most of the time.
Is this true? That would be a very profound finding. Any papers that discuss this?

Looking at a random game of life with 10^6 cells, I get the feeling that it will not loop for a long time.

Maybe it is a misunderstanding. I do not mean to find a self-replicator of size c in a field of size c. I would expect that the field is big. Very big. Let's say 10^80 cells. That is the estimate for the number of atoms in the universe. The self replicator would be way way smaller. One manually constructed replicator (Gemini) is just 10^7 cells. And that is certainly not the smallest replicator possible.