6 ms·

Theory of self-reproducing automata (1966)

80 points by HNLurker2 8y ago

no_gravity 8y ago
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.
- nabla9 8y ago
  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.
  - Isamu 8y ago
    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.
- whatshisface 8y ago
  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.
  - deleted 8y ago
    [deleted]
  - no_gravity 8y ago
    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.
DonHopkins 8y ago
Page 312 has the sexy playboy centerfold spread of John von Neumann's 29 state transition rule: https://archive.org/details/theoryofselfrepr00vonn_0/page/312 https://archive.org/details/theoryofselfrepr00vonn_0/page/31... Ordinary, Confluent: C<ee'>, Number: 4, Received conjunctively from T<0ae> directed toward it; emits with double delay to all T<uae> not directed toward it. Killed to U by T<1a1> directed toward it; killing dominates reception. https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton https://en.wikipedia.org/wiki/Von_Neumann_universal_constructor https://en.wikipedia.org/wiki/Von_Neumann_universal_construc...
MattConfluence 8y ago
I have an anecdote about this book! I wrote my master's thesis about some cellular automata experiments. This was in 2016, so in the 50th anniversary year of the book. While doing background research I checked my university library's online database and found they had a copy of this book in storage off-site. So I had it retrieved and checked it out. Perfect condition. On the little card on the inside of the cover that shows previous borrowers there was one name and date, some time in the 70's, around the time my dad attended the same university. While it is possible there were more borrowers of the book that just weren't noted on the card (I myself was registered in a digital system of course), there can't have been many, since there was so little wear and tear. Made me wonder what other "treasures" are lying around libraries around the world, waiting generations between each time someone checks them out.
deleted 8y ago
[deleted]
deleted 8y ago
[deleted]
cellular 8y ago
https://youtu.be/gaFKqOBTj9w https://youtu.be/gaFKqOBTj9w A new kind of automata.
- thecupisblue 8y ago
  Oh shit. Love that paper. Wonder what it would end up looking like in a 4D torus.
ericsoderstrom 8y ago
Is there any finite initial condition for Conway's game of life that will expand to fill an arbitrarily large area of the plane with density that does not approach zero?
- Isamu 8y ago
  The spacefiller is what you are looking for I think. https://en.m.wikipedia.org/wiki/Spacefiller https://en.m.wikipedia.org/wiki/Spacefiller
- OtterCoder 8y ago
  Yes, Puffers: http://www.conwaylife.com/wiki/Category:Puffers http://www.conwaylife.com/wiki/Category:Puffers

80 points by HNLurker2 8y ago

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.

nabla9 8y ago
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.
- Isamu 8y ago
  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.
whatshisface 8y ago
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.
- deleted 8y ago
  [deleted]
- no_gravity 8y ago
  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.

DonHopkins 8y ago

Page 312 has the sexy playboy centerfold spread of John von Neumann's 29 state transition rule: https://archive.org/details/theoryofselfrepr00vonn_0/page/312 https://archive.org/details/theoryofselfrepr00vonn_0/page/31... Ordinary, Confluent: C<ee'>, Number: 4, Received conjunctively from T<0ae> directed toward it; emits with double delay to all T<uae> not directed toward it. Killed to U by T<1a1> directed toward it; killing dominates reception. https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton https://en.wikipedia.org/wiki/Von_Neumann_universal_constructor https://en.wikipedia.org/wiki/Von_Neumann_universal_construc...

MattConfluence 8y ago

I have an anecdote about this book! I wrote my master's thesis about some cellular automata experiments. This was in 2016, so in the 50th anniversary year of the book. While doing background research I checked my university library's online database and found they had a copy of this book in storage off-site. So I had it retrieved and checked it out. Perfect condition. On the little card on the inside of the cover that shows previous borrowers there was one name and date, some time in the 70's, around the time my dad attended the same university. While it is possible there were more borrowers of the book that just weren't noted on the card (I myself was registered in a digital system of course), there can't have been many, since there was so little wear and tear. Made me wonder what other "treasures" are lying around libraries around the world, waiting generations between each time someone checks them out.

deleted 8y ago

[deleted]

deleted 8y ago

[deleted]

cellular 8y ago

https://youtu.be/gaFKqOBTj9w https://youtu.be/gaFKqOBTj9w A new kind of automata.

thecupisblue 8y ago
Oh shit. Love that paper. Wonder what it would end up looking like in a 4D torus.

ericsoderstrom 8y ago

Is there any finite initial condition for Conway's game of life that will expand to fill an arbitrarily large area of the plane with density that does not approach zero?

Isamu 8y ago
The spacefiller is what you are looking for I think. https://en.m.wikipedia.org/wiki/Spacefiller https://en.m.wikipedia.org/wiki/Spacefiller
OtterCoder 8y ago
Yes, Puffers: http://www.conwaylife.com/wiki/Category:Puffers http://www.conwaylife.com/wiki/Category:Puffers