Automatas are turing-complete grid-based systems with progression rules on which we can encode arbitrarily complex structures. For example, this is a "glider gun" on Conway's Game of Life:


Due to turing-completeness, with enough efforts, one could encode fully-featured structures, such as machines that claimed territories on the grid and defended those against intrudes. As much as that is possible by human design, the system will not emerge complex structures on its own. That is, you can't start a Game of Life with random initial conditions, leave it running for years and hope that, when you come back, you'll be able to observe gliders and other complex structures emerged naturally.

My question is: is there any known computing system in which complex structures emerge naturally from just running it for long enough?

  • $\begingroup$ I'm asking for a turing-machine/automata/λcalculus like system that I can simulate and that has that property. I don't understand exactly how it wouldn't relate to computer science since that is all I'm doing, could you elaborate? $\endgroup$ – MaiaVictor Aug 5 '15 at 20:14
  • $\begingroup$ The issue is that I don't really know the CS words that apply to the question - that is basically what I'm asking. Sorta like if I've came here asking what is a system that encapsulates what our brain does - a partially correct answer could be "neural network", so it is a CS question although it looks like a biology one - but I couldn't know that word beforehand. $\endgroup$ – MaiaVictor Aug 5 '15 at 21:49
  • $\begingroup$ I've edited the question with what I believe is the best iteration of itself now. I hope this one is actually final! $\endgroup$ – MaiaVictor Aug 5 '15 at 23:14
  • 3
    $\begingroup$ Thanks for the edit! That raises a new question. You write that "you can't start a Game of Life with random initial conditions, leave it running for years and hope that, when you come back, you'll be able to observe gliders and other complex structures emerged naturally." How do you know? Do we know for sure that this premise is true? I have no intuition into whether this should be true or not -- it seems plausible to me that it might be false (that such complex structures might well emerge naturally, with non-negligible probability, given a random starting state). $\endgroup$ – D.W. Aug 5 '15 at 23:50
  • 2
    $\begingroup$ svrm, to the best of my knowledge, if I correctly understand what you're asking for, I don't believe it has been demonstrated. I would love to be the first. (By which I mean I have actually put several months of serious research effort into it - but no luck yet!) Nevertheless, you might look into simulated evolution (AKA genetic algorithms, AKA genetic programming, AKA evolutionary robotics) for a methodology that has been successful in generating complex things without human design. The keywords "Artificial Life" might be helpful to you, as the name of a community who work on things like this $\endgroup$ – Nathaniel Aug 6 '15 at 5:37

It seems very hard to define the phrase "internal structures that defend their own existences" in a rigorous or precise way, so it is not clear that the question is well-defined. However, some very simple systems can admit behavior that might be described in these terms.

For instance, consider Conway's game of life. It is known to allow for replicators: i.e., there are self-replicating patterns which create a complete copy of themselves. Replication can be thought of as a "strategy" for "defending your own existence"; if you spawn many copies of yourself, then even if someone messes up one of the copies, the other copies will still exist.

So, to the extent that the phrase "internal structures that defend their own existence" is well-defined, self-replicators in Conway's game of life might be considered a form of internal structure that will defend its own existence.

Conway's game of life is very simple. Another very simple example is Rule 110, which is an extremely simple cellular automaton. It is known that Rule 110 is Turing complete, which means that it is possible to simulate Conway's game of life in a Rule 110 cellular automaton, which means that a Rule 110 cellular automaton can be argued to allow for "internal structures that defend their own existence". It's probably going to be hard to find a system that's much simpler than a Rule 110 cellular automaton.

In general, we should probably be careful about anthromorphicizing the behavior of computational systems like this. Just because they behave in ways that resemble the behavior of people or animals doesn't necessarily mean it's necessarily going to be super-meaningful to describe them as acting with a 'purpose' (like self-defense). Ascribing human motivations or emotions to them runs the risk of misleading our intuition.

  • $\begingroup$ Conway's game of life won't keep evolving more and more complex "lifeform" as time passes, though. It reaches a point where the same structures are present and nothing else emerges. This, for example, can be run forever and it will never get more complex than that. It will always be 2 glider guns + the shots. For the fact it is something really hard to define, I guess I'll just give up of this question. $\endgroup$ – MaiaVictor Aug 5 '15 at 20:23
  • $\begingroup$ But if you consider duplicators to be lifeforms, this, by all means, answers the question as asked, so I'll just accept it. /sighs $\endgroup$ – MaiaVictor Aug 5 '15 at 20:40
  • $\begingroup$ @srvm There's no hurry to accept. You can always wait to see if you get an answer that's closer to what you were looking for. (OTOH, accepting this answer now doesn't stop you from accepting some other answer later on.) $\endgroup$ – David Richerby Aug 5 '15 at 20:58
  • 1
    $\begingroup$ To stress that point: every Turing-complete system can simulate Game of Life, so they all exhibit the property, after a fashion. For Turing machines, note how the tape (content) can become arbitrarily large and complicated during a computation. $\endgroup$ – Raphael Aug 6 '15 at 9:50
  • 1
    $\begingroup$ @srvm Is there any evidence that we see nature to "keep evolving more and more complex lifeform"? It doesn't seem that way; insects and many other lifeforms have been around for millions of years with few changes; mammals are much the same since they've been around; there's not even that much difference between dinosaurs and us. $\endgroup$ – Raphael Aug 6 '15 at 9:53

It might be worth having a look at Turmites (https://en.wikipedia.org/wiki/Turmite ).

They are state machines on an n-dimensional grid that alter their direction and output based on the current cell. Many configurations of them build 'highways' (repeating structures) and if interrupted many will find a way back to the 'highway' and continue again.

  • $\begingroup$ That is very interesting. Thank you very much! $\endgroup$ – MaiaVictor Aug 5 '15 at 21:47

as another answer states, this is a tricky question, but heres another "lead" for you that roughly fits your criteria. solitons are studied in physics and are "persistent wave patterns" that can occur in any dimension (incl physically realistic ones like 3d), based on simple energy dynamics on a lattice. they are composed out of emergent properties of a combined nonlinear propagating and dispersive effects that cancel to leave the patterns. while the study originated in analog systems, it was eventually realized the overall system can be modelled by a (digital) cellular automata with fairly simple local rules.

there is significant study of solitons in physics, where they arise in many different specialized contexts, and there are some major parallels with particle physics, but far less study from a CS orientation. while much research has accumulated over decades, there is not a lot of active work, possibly due to their interdisciplinary/ scientifically crosscutting nature. hence they may be somewhat understudied wrt their importance and there are likely significant undiscovered phenomena in this area. heres an example paper along these lines:

  • 1
    $\begingroup$ re one of the other question criteria of behavior wrt time evolution, solitons are also self-organizing and "persistent/ resilient" in various senses. eg if a soliton lattice starts with random energy levels, solitons of various sizes will coalesce after time. $\endgroup$ – vzn Aug 6 '15 at 1:24

Sorry, cannot comment - this should be one :-/ http://rendell-attic.org/gol/tm.htm Full Universal Turing Machine in Game of Life.

And after reading your question I think that answer will be dissapointing but true. Any system that emerges on its own should be considered "evolving", but instead of giving some recombinations or modification all we include are constraints. Furthermore when we see some "really" evolving system, we would prefer to speed process up, and disable even more randomness in it. Things you have described are random occurences of complicated structures or patterns, but if we treat it as we should - it is fully deterministic but out of reach to expect it in mind or via programming. It looks awesome, but it was already there, so this is not new form, new generator or quality on its own. Every such system has to obey rules. Every truly evolving system that I know of failed. The most beautiful was AI cat with number of neurons equal to real alive cat - and even environment was technically good, well it did not learned any behaviour... There were examples of generators of programs - random but grammatically correct source codes were generated, compiled until they could do something (well, anything that basic program can do), many cpu hours passed as it generated some trivial calculations. What I wanted to add: if you want something to emerge you have to allow it to change its rules, and take enormous amount of time (unfortunatelly for that reason also define rules to decrease failure rate) to observe evolution, which is not practical so it is not popular task. Otherwise, you are looking for very rare occurence of some pattern on machine that could do something unexpected. But if you consider this from deterministic point of view, as continuum theory says, what I added is already the same pointless predetermined process. On the other hand, there is bigger probability that there will be some new quality added if selfmodification of machine is enabled.


I choose to write this as an answer rather than a comment because my feeling is that all answers are rather long comments, and this is going to be too long for a comment. No one is actually saying yes or no to your question. I will not either (I do not know whether there is such a structure that is known as such, but I believe that such a structure can exist, though I have no proof for it).

To begin with, I expect you looked at the wikipedia page on cellular automata, where your animation comes from. But you do not seem to have drawn any other information from that page.

Your question is about order and stability of complex patterns emerging from some chaos based on simple (?) rules. Indeed, one answer comments that you look for complex structures that "behave in ways that resemble the behavior of people or animals".

Emergence of order from chaos, and of (more or less) stable complex structures immediately rings a bell in real physical systems: thermodynamics. So my first move was to call Google with the words: automata theory thermodynamics, and the second answer was the wikipedia page on cellular automata.

Indeed it seem that some researchers (including Stephen Wolfram) have investigated the issue in relation with the thermodynamics aspects found in nature. This is not very detailed, and I guess one would have to analyze thermodynamics of cellular automata models, whatever that may be. This has been done to some extent with reversible cellular automata.

There is probably more to it. The wikipedia page alludes to the creation of large stable structures (class 4 cellular automata), "reminiscent of the phase transition in thermodynamics".

That is all I can say about this line of thought, though I believe it should be an important one for the kind of question asked. The work on trying to understand physics and biology from cellular automata model is obviously also relevant.

This said, the page also mentioned the work of John von Neumann who proved the existence of a self replicating system based on cellular automata."This design is known as the tessellation model, and is called a von Neumann universal constructor." Replicators were found more recently fr Conway's game of life.

Building on this, one can imagine that some type $A$ of such structures could have an ability to clear up space to let other $A$ structures find space to reproduce. As you remark yourself, this is to be expected from the Turing completeness of cellular automata.

So one can imagine that the structure you suggest could exists. Which probably means that infinitely many different such structures could exist.

However your question is whether it could emerge spontaneously, if one waits long enough. But you do not specify an initial state.

Given an "infinite" cellular universe, and a random initial configuration, I do not see why not, at least for some types of celluler automata. It may take some 13 billion years though (just a randomly chosen duration). But maybe the most interesting pointer in that direction is the class 4 cellular automata of Wolfram classification. See also this reference.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.