4 ms·

Self-Reproducing Cellular Automata

72 points by chmaynard 6y ago

ganafagol 6y ago
If our universe is just one big cellular automaton (that's what Stephen Wolfram claims in his physics project) then one would wonder if we see a similar effect in real life. Maybe the universe just doesn't use the right rule though.
- LegitShady 6y ago
  > If our universe is just one big cellular automaton (that's what Stephen Wolfram claims in his physics project) then one would wonder if we see a similar effect in real life. We ourselves and everything around us would be that evidence...it's finding out if everything is made up of cellular automata that's the hard part.
  - ganafagol 6y ago
    I'm talking about this self-replicating effect in particular. In some distance far far away, there'd be some instance of me exactly identical and behaving exactly identically including writing these words right now. Or, more generally, some superimposed versions of me partially overlapping, as can be seen with those overlapping Es in the original article.
    - maze-le 6y ago
      This effect also happens with continuous models, as there is only a finite number of quantum states in any finite subset of space. In fact, any notion of infinite space will virtually guarantee that there are exact copies (infinite copies) of you and me doing what we do now. But it's basically only a philosophical question since we only have access to our observable universe.
    - tiborsaas 6y ago
      DNA copying is kinda similar. Also look into fractals, since they are self similar.
    - LegitShady 6y ago
      >I'm talking about this self-replicating effect in particular. In some distance far far away, there'd be some instance of me exactly identical and behaving exactly identically including writing these words right now. Maybe. >Or, more generally, some superimposed versions of me partially overlapping, as can be seen with those overlapping Es in the original article. Maybe - it depends on the complexity of not just you but everything around you. There may be billions of similar yous around you, with some variation based on their history, but it's not close enough 'you' for your arbitrary definition. I guess what I'm saying is, it really depends on how it all works. The interactions of different cellular automata can still give rise to incredible complexity that might make identical yous very difficult or impossible. Twins have similar circumstances to a high degree but even they can be different physically and are always different experimentally. It's complicated.
    - bopbeepboop 6y ago
      > In some distance far far away, there'd be some instance of me exactly identical and behaving exactly identically including writing these words right now. From the perspective of your cells, this is (almost) true. There’s a whole tree of them branching since replicators originated here, and they’re surrounded by near clones of themselves amid many, many more distant copies. There are even interference patterns of lines that collide, eg gut bacteria and human cells.
- mseepgood 6y ago
  > If our universe is just one big cellular automaton Aren't cellular automata deterministic, but the universe is non-deterministic at the quantum level?
  - thewakalix 6y ago
    Depends on who you ask. In the Everett interpretation, quantum mechanics is deterministic, and uncertainty about quantum mechanical measurements arises from indexical uncertainty (“which observer am I?”) rather than fundamental randomness.
  - pelorat 6y ago
    Just like life in a cellular automata world could figure out the rules behind cell replication and destruction, they could never peer underneath at the mechanism driving it all. For us, is there a level underneath the quantum level? We can speculate (i.e. string and m-theory), but we may never find out because we're made of matter constrained by three spatial dimensions and our sensing equipment is similarly constrained. For an outside entity observing the universe, it may very well be deterministic, and what we see as quantum probabilities and non-determinism are simply limitations in our ability to build better testing equipment, because we can only work with what the universe provides to us (atoms and particles).
    - SuchAnonMuchWow 6y ago
      your comment made me think of this comic: http://english.bouletcorp.com/2011/12/08/pixel-quantum/ http://english.bouletcorp.com/2011/12/08/pixel-quantum/
  - SigmundA 6y ago
    Why can't cellular automata rules contain a quantum_rand()? [1] Most games and simulations contain RNG's to make things interesting, quantum uncertainty seems to look very similar to my naive self. 1. https://content.wolfram.com/uploads/sites/34/2020/07/random-sequence-generation-cellular-automata.pdf https://content.wolfram.com/uploads/sites/34/2020/07/random-...
- newdude116 6y ago
  Stephen Wolfram did not invent this https://en.wikipedia.org/wiki/Calculating_Space https://en.wikipedia.org/wiki/Calculating_Space
  - deleted 6y ago
    [deleted]
max_ 6y ago
Not an expert here but what is the relationship between by this and Von Neumann's "Self Replicating Machines"? [0] [0]: https://en.m.wikipedia.org/wiki/Self-replicating_machine https://en.m.wikipedia.org/wiki/Self-replicating_machine
- chriswarbo 6y ago
  von Neumann's approach was to define a "universal constructor", with a programmable "arm" for altering cells. He came up with a complicated set of cellular automaton rules which allow such a universal constructor. Then he came up with a "program" for the constructor which, when executed, would create a copy of the universal constructor and of the program. This was all meant to be in analogy to the physical world, where such a constructor could be used to build almost anything, perhaps operating at the atomic-scale. It turns out that we can get much simpler self-replicators if we (a) ignore the "universal constructor" ability, and only focus on self-replication; and (b) choose cellular automaton rules which make self-replication easier, rather than using cells to encode "programs". This approach gives things like Langton's Loops https://en.wikipedia.org/wiki/Langton%27s_loops https://en.wikipedia.org/wiki/Langton%27s_loops The self-replicating property described in the article seems like an extreme form of this approach: the rules are so tailored for replication that they can't do anything else. Of course, making such simplifications sort of defeats von Neumann's original purpose, since such highly-tailored rules are less "realistic", and hence don't particularly help us build physical self-replicators; and even if we could, they wouldn't be particularly useful without the "universal constructor" ability.
  - eternalban 6y ago
    Happy to see Chris Langton mentioned. He is often strangely neglected. Here is the transition table for Langton Loops: https://github.com/GollyGang/ruletablerepository/blob/gh-pages/downloads/Langtons-Loops.table https://github.com/GollyGang/ruletablerepository/blob/gh-pag...
  - Syzygies 6y ago
    > Of course, making such simplifications sort of defeats von Neumann's original purpose Yes. In von Neumann's last book "Theory of Self-Reproducing Automata", he thought about machines having viable offspring. This was more than a trick with patterns. He had invented the architecture of working computers, and was now moving on. As a math grad student at Harvard around 1980, the wine flowed freely on Friday afternoons. I nevertheless headed over to the biology department, where cannabis-fueled discussions centered on work like von Neumann's.
wolfium3 6y ago
(not directly related to the article) The cellular automata in the article is a discrete one. For those interested, there are also "continuous" automata https://www.youtube.com/watch?v=KJe9H6qS82I https://www.youtube.com/watch?v=KJe9H6qS82I.
joehartshorn 6y ago
Obligatory mentions: https://playgameoflife.com/ https://playgameoflife.com/ https://www.decisionproblem.com/paperclips/ https://www.decisionproblem.com/paperclips/

72 points by chmaynard 6y ago

If our universe is just one big cellular automaton (that's what Stephen Wolfram claims in his physics project) then one would wonder if we see a similar effect in real life. Maybe the universe just doesn't use the right rule though.

LegitShady 6y ago
> If our universe is just one big cellular automaton (that's what Stephen Wolfram claims in his physics project) then one would wonder if we see a similar effect in real life. We ourselves and everything around us would be that evidence...it's finding out if everything is made up of cellular automata that's the hard part.
- ganafagol 6y ago
  I'm talking about this self-replicating effect in particular. In some distance far far away, there'd be some instance of me exactly identical and behaving exactly identically including writing these words right now. Or, more generally, some superimposed versions of me partially overlapping, as can be seen with those overlapping Es in the original article.
  - maze-le 6y ago
    This effect also happens with continuous models, as there is only a finite number of quantum states in any finite subset of space. In fact, any notion of infinite space will virtually guarantee that there are exact copies (infinite copies) of you and me doing what we do now. But it's basically only a philosophical question since we only have access to our observable universe.
  - tiborsaas 6y ago
    DNA copying is kinda similar. Also look into fractals, since they are self similar.
  - LegitShady 6y ago
    >I'm talking about this self-replicating effect in particular. In some distance far far away, there'd be some instance of me exactly identical and behaving exactly identically including writing these words right now. Maybe. >Or, more generally, some superimposed versions of me partially overlapping, as can be seen with those overlapping Es in the original article. Maybe - it depends on the complexity of not just you but everything around you. There may be billions of similar yous around you, with some variation based on their history, but it's not close enough 'you' for your arbitrary definition. I guess what I'm saying is, it really depends on how it all works. The interactions of different cellular automata can still give rise to incredible complexity that might make identical yous very difficult or impossible. Twins have similar circumstances to a high degree but even they can be different physically and are always different experimentally. It's complicated.
  - bopbeepboop 6y ago
    > In some distance far far away, there'd be some instance of me exactly identical and behaving exactly identically including writing these words right now. From the perspective of your cells, this is (almost) true. There’s a whole tree of them branching since replicators originated here, and they’re surrounded by near clones of themselves amid many, many more distant copies. There are even interference patterns of lines that collide, eg gut bacteria and human cells.
mseepgood 6y ago
> If our universe is just one big cellular automaton Aren't cellular automata deterministic, but the universe is non-deterministic at the quantum level?
- thewakalix 6y ago
  Depends on who you ask. In the Everett interpretation, quantum mechanics is deterministic, and uncertainty about quantum mechanical measurements arises from indexical uncertainty (“which observer am I?”) rather than fundamental randomness.
- pelorat 6y ago
  Just like life in a cellular automata world could figure out the rules behind cell replication and destruction, they could never peer underneath at the mechanism driving it all. For us, is there a level underneath the quantum level? We can speculate (i.e. string and m-theory), but we may never find out because we're made of matter constrained by three spatial dimensions and our sensing equipment is similarly constrained. For an outside entity observing the universe, it may very well be deterministic, and what we see as quantum probabilities and non-determinism are simply limitations in our ability to build better testing equipment, because we can only work with what the universe provides to us (atoms and particles).
  - SuchAnonMuchWow 6y ago
    your comment made me think of this comic: http://english.bouletcorp.com/2011/12/08/pixel-quantum/ http://english.bouletcorp.com/2011/12/08/pixel-quantum/
- SigmundA 6y ago
  Why can't cellular automata rules contain a quantum_rand()? [1] Most games and simulations contain RNG's to make things interesting, quantum uncertainty seems to look very similar to my naive self. 1. https://content.wolfram.com/uploads/sites/34/2020/07/random-sequence-generation-cellular-automata.pdf https://content.wolfram.com/uploads/sites/34/2020/07/random-...
newdude116 6y ago
Stephen Wolfram did not invent this https://en.wikipedia.org/wiki/Calculating_Space https://en.wikipedia.org/wiki/Calculating_Space
- deleted 6y ago
  [deleted]

max_ 6y ago

Not an expert here but what is the relationship between by this and Von Neumann's "Self Replicating Machines"? [0] [0]: https://en.m.wikipedia.org/wiki/Self-replicating_machine https://en.m.wikipedia.org/wiki/Self-replicating_machine

chriswarbo 6y ago
von Neumann's approach was to define a "universal constructor", with a programmable "arm" for altering cells. He came up with a complicated set of cellular automaton rules which allow such a universal constructor. Then he came up with a "program" for the constructor which, when executed, would create a copy of the universal constructor and of the program. This was all meant to be in analogy to the physical world, where such a constructor could be used to build almost anything, perhaps operating at the atomic-scale. It turns out that we can get much simpler self-replicators if we (a) ignore the "universal constructor" ability, and only focus on self-replication; and (b) choose cellular automaton rules which make self-replication easier, rather than using cells to encode "programs". This approach gives things like Langton's Loops https://en.wikipedia.org/wiki/Langton%27s_loops https://en.wikipedia.org/wiki/Langton%27s_loops The self-replicating property described in the article seems like an extreme form of this approach: the rules are so tailored for replication that they can't do anything else. Of course, making such simplifications sort of defeats von Neumann's original purpose, since such highly-tailored rules are less "realistic", and hence don't particularly help us build physical self-replicators; and even if we could, they wouldn't be particularly useful without the "universal constructor" ability.
- eternalban 6y ago
  Happy to see Chris Langton mentioned. He is often strangely neglected. Here is the transition table for Langton Loops: https://github.com/GollyGang/ruletablerepository/blob/gh-pages/downloads/Langtons-Loops.table https://github.com/GollyGang/ruletablerepository/blob/gh-pag...
- Syzygies 6y ago
  > Of course, making such simplifications sort of defeats von Neumann's original purpose Yes. In von Neumann's last book "Theory of Self-Reproducing Automata", he thought about machines having viable offspring. This was more than a trick with patterns. He had invented the architecture of working computers, and was now moving on. As a math grad student at Harvard around 1980, the wine flowed freely on Friday afternoons. I nevertheless headed over to the biology department, where cannabis-fueled discussions centered on work like von Neumann's.

wolfium3 6y ago

(not directly related to the article) The cellular automata in the article is a discrete one. For those interested, there are also "continuous" automata https://www.youtube.com/watch?v=KJe9H6qS82I https://www.youtube.com/watch?v=KJe9H6qS82I.

joehartshorn 6y ago

Obligatory mentions: https://playgameoflife.com/ https://playgameoflife.com/ https://www.decisionproblem.com/paperclips/ https://www.decisionproblem.com/paperclips/