This is the first of a few posts I plan (one other of which is written and another of which is in draft form but in need of a few changes) in which I discuss various Polymath proposals in more detail than I did in my earlier post on possible projects.
One of my suggestions, albeit a rather tentative one, was to try to come up with a model that would show convincingly how life could emerge from non-life by purely naturalistic processes. But before this could become a sensible project it would be essential to have a more clearly defined mathematical question. By that I don’t mean a conjecture that Polymath would be trying to prove rigorously, but rather a list of properties that a model would have to have for it to count as successful. Such a list need not be fully precise, but in my view it should be reasonably precise, so that the task is reasonably well defined. It would of course be possible to change the desiderata as one went along.
In this post I’d like to make a preliminary list. It will undoubtedly be unsatisfactory in many ways, but I hope that there will be a subsequent discussion and that from it a better list will emerge. The purpose of this is not to start a Polymath project, but simply to attempt to define a Polymath proposal that might at some future date be an actual project. For two reasons I wouldn’t want this to be a serious project just yet: it seems a good idea to think quite hard about how it would actually work in practice, and someone who I hope will be a key participant is very busy for the next few months and less busy thereafter.
As a starting point, let me mention two ideas that are already out there and have attracted a lot of attention. One is the idea of cellular automata. A fairly general type of cellular automaton can be defined as follows. You have a graph (usually something like an infinite two-dimensional lattice), and at some points you have 1s and at other points you have 0s. You then let the system evolve in rounds according to some simple rule that is usually the same for every vertex. It might be something like this: if at least two of my neighbours are 1s then I will become a 1, and otherwise I will become a 0. It turns out that very simple rules can lead to extremely complicated and interesting behaviour.
What counts as complicated and interesting? Well, perhaps it is better to say what counts as dull. One possible form of dullness is if a system evolves to some state such as the all-1s state, or perhaps a big rectangle full of 1s with 0s outside, or an oscillation between two configurations. Another form of dullness is a system that tends to disperse the 1s until they form some fairly random looking bunch of 1s that never stops looking fairly random. But in between, there are systems that tend to evolve towards some kind of criticality, where you get fractal structures with organization at many different distance scales. One thing that interests people about cellular automata is that there are very simple rules that seem to want to evolve towards these nice “edge of chaos” patterns.
The second idea is self-organized criticality, which is a phenomenon exhibited by certain models in statistical physics — notably the so-called sandpile models. These are supposed to model what happens if you drop grains of sand one by one on to a pile. They will start to build up into a conical shape, but if the sides get too steep there are avalanches. The sizes of these avalanches vary, and if you plot the frequency of avalanches of various sizes, you find (experimentally at least) that they obey a power law. And power laws get people excited because they are what you find associated with critical phenomena. A typical sandpile model is something like this. You have a big square divided into a grid of small squares. You then set all squares equal to 0 except a few randomly chosen ones that you give small integers to. You then add 1 to the central square (let’s assume there is one), and after you have done so you have a rule that says that if any square has value at least 4 it must give 1 to each of its neighbours. This procedure you iterate until no square has value at least 4. (It can be shown that the order in which you do these operations doesn’t matter.) You then add 1 to the central square again, and keep going.
It turns out that the sizes of the “avalanches” that take place here (that is, how many iterations you have to do of the simple rule before all squares have value 0 to 3) also obey a power law, and also that systems such as these have a tendency to evolve towards interesting (that is, not too random and not too structured) configurations. That is, you can get critical phenomena without having to fine-tune some parameter. Again, this has got people excited as it seems to promise an explanation of how the complexity in nature could have started.
In the above description, I made the starting configuration random but after that the way the model evolved was deterministic. There are of course many different possible models, and in some of them the new “grains of sand” are dropped in random places. Again you get interesting critical behaviour.
Now as far as I know, with both cellular automata and sandpile models you get nice critical phenomena appearing, but while they give you pretty patterns they do not give you anything resembling an ecosystem. Yes, Conway’s game of life gives you glider guns and configurations that can reproduce themselves, but you have to set them up carefully in advance, and they don’t seem to do anything all that exciting. They also support universal computation, but again if you want to program the game of life to create an artificial-life simulator, you might as well use a much more powerful computer to do so. What a Polymath project would be looking for is a very simple system with the property that, regardless of the starting configuration, it would tend to develop and eventually produce something that looked like a complex ecosystem.
This brings me to a point that is worth making. The idea of this Polymath project would not be to produce yet another artificial life program, fascinating though those programs can be. One could think of it more like this: can one come up with a very simple model that almost always “self-organizes” and produces something that looks a bit like what you get with artificial life programs? In other words, we would be trying to model abiogenesis rather than evolution.
After that discussion, I think I can have a stab at saying what the properties are that would make a truly interesting and new model. (I am much less sure about the “new” part, and would be interested to hear from people with more knowledge about this kind of topic what the state of the art is.) Some of the properties below seem to be more important than others, but for now I won’t bother to distinguish between those that I regard as essential and those that are merely desirable.
1. It should be a dynamic model that evolves according to simple rules.
2. It should have a tendency to evolve towards patterns with a “critical” character — not too random and not too simple, with interesting features at many distance scales.
3. Probably it should be a somewhat randomized model (to give it a certain robustness). Here I am referring to the rules by which the model develops rather than the initial conditions, but perhaps the initial conditions should be randomized as well.
4. It should have a tendency to produce identifiable macroscopic structures.
5. It should be possible to classify these macroscopic structures in interesting ways. (That is, we would like to be able to say that certain structures look more or less the same as certain others, and ideally this similarity would be a bit more flexible than one just being a translation of another.)
6. These structures should interact with one another, and the interaction should sometimes be destructive (thereby providing some selection pressure).
7. With high probability, self-reproducing structures should eventually emerge. (Before posting this I showed it to Michael Nielsen, who made some interesting points. One of them is that experience in the actual universe suggests that perhaps there should be some fine tuning of parameters before the probability becomes high: after all, life does not evolve on all planets.)
I could go on, but the idea is that once you’ve got 6 and 7, and perhaps a few other properties (for instance, one might decide to have major environmental changes from time to time just to stimulate the development of the system), then natural selection can begin to operate.
Of course, the major challenge is 7. The most plausible route I can see to 7 is a purely probabilistic one: almost all configurations are not self-reproducing, but if a self-reproducing one ever does arise, then it will reproduce itself and start appearing all over the place. But in that case 5 is also a huge challenge. The kinds of structures one would ideally like are not things like the bullets from Conway’s glider guns, but larger configurations that can move about and that are defined more topologically. Indeed, that could be a huge and general problem: the geometry of \(\mathbb{Z}^3\) just isn’t the same as the geometry of \(\mathbb{R}^3\), but a continuous model would be very difficult to design and simulate (or would it?). But perhaps there could be some cleverly chosen simple rule that would tend to protect “clumps” of 1s and allow them to move, and to do complicated things like rotating (whatever that can be made to mean in \(\mathbb{Z}^3\)). Or perhaps a complicated ecosystem could develop that was more \(\mathbb{Z}^3\)-like than \(\mathbb{R}^3\)-like.
Here, incidentally, is a paragraph from the Wikipedia article on Conway’s game of life, which shows that it is not already an example of what I am talking about:
From a random initial pattern of living cells on the grid, observers will find the population constantly changing as the generations tick by. The patterns that emerge from the simple rules may be considered a form of beauty. Small isolated subpatterns with no initial symmetry tend to become symmetrical. Once this happens the symmetry may increase in richness, but it cannot be lost unless a nearby subpattern comes close enough to disturb it. In a very few cases the society eventually dies out, with all living cells vanishing, though this may not happen for a great many generations. Most initial patterns eventually “burn out”, producing either stable figures or patterns that oscillate forever between two or more states; many also produce one or more gliders or spaceships that travel indefinitely away from the initial location.
We would be looking for something a bit like the Game of Life, possibly randomized, with the important difference that it almost always got more and more complicated and more and more interesting.
Physics
There is one other property that I think would make a model more convincing as an argument for the probability of life arising out of non-life without any magic processes operating. I partly owe this thought to Michael Nielsen, who included the following two questions in a comment he made on the post where I originally mentioned this problem.
(1) How would you go about recognizing self-replicating beings?
(2) What sort of models are “reasonable”, in the sense of both reflecting what we know of physics, and being simple enough to be tractable? The Game of Life isn’t very physical, in that it disobeys many basic physical principles, like conservation of energy, conservation of mass, conservation of momentum, and so on.
One of the things that people often say about life, evolution, biological systems and the like is that they are ways of locally combatting the second law of thermodynamics. So perhaps one could add the following property as one that it would be very nice to have.
8. The general tendency for the model is to become more and more disordered, and eventually to end in heat death, but for there to be many local increases in order.
Of course, one would need to be clear what that meant. The other physical principles that Michael mentioned would also be good to have.
Here is a subproblem that occurs to me as I am writing this. It is connected with the thought that one would like macroscopic structures to have some tendency to survive. In the Game of Life, it seems that structures that survive do so almost by accident — they settle down into some sort of periodicity, say. But structures in the biological world are held together by physical forces, and they have identifiable boundaries and things like that. So one might try to develop a model that captures just this behaviour. As with the main problem, I’m not sure how to formulate this subproblem precisely, but let me have a go. Does there exist a model with the following properties?
(i) If you draw some large-scale shape (think of the 0s and 1s as black and white pixels, say, so the shape is on a much larger distance scale than the distance between two neighbouring points of the grid), it has a tendency to move “continuously”.
(ii) There is a tendency for mass and momentum to be conserved.
To give an idea of the kind of thing I mean here, let’s suppose that “mass” is represented by 1s, and you take a large annulus, place it over \(\mathbb{Z}^2\), and put a 1 at every grid point that lies in the annulus. Then in the interior circle of the annulus put a random scattering of not too many 1s. And then slightly move the annulus part, and slightly move all the little particles inside. If the first position of the annulus represents where some very simple structure is at time 1 and the second where it is at time 2, then conservation of mass and momentum would tell us to expect it to continue moving in the same direction (so it would be more sophisticated than a cellular automaton of the kind described earlier because its behaviour would depend not just on how it behaved an instant earlier), and to stay the same size. We might also have “forces” between neighbouring 1s that encouraged them to stay together somewhat, and so on.
Of course, as with Conway’s Game of Life, the idea would be to devise the simplest possible set of rules that did what one wanted (in this case preserve macroscopic shapes at least to some extent and allow them to move about reasonably flexibly but without distorting themselves too much). It would not be to try to create the most realistic model one could of the actual world.
Since writing the above paragraphs I’ve found out the following relevant facts. First this from the Wikipedia article on Life-like cellular automata:
Larger than Life is a family of cellular automata studied by Kellie Michele Evans. They have very large radius neighbourhoods, but perform `birth/death’ thresholding similar to Conway’s life. The LtL CA manifest eerily organic `glider’ and `blinker’ structures.
RealLife is the “continuum limit″ of Evan’s Larger Than Life CA, in the limit as the neighbourhood radius goes to infinity, while the lattice spacing goes to zero. Technically, they are not cellular automata at all, because the underlying “space” is the continuous Euclidean plane R2, not the discrete lattice Z2. They have been studied by Marcus Pivato.
Secondly, here is the paper by Marcus Pivato mentioned above.
Chemistry and the problem of scale.
By far the most famous contribution to our understanding of how life started is the Miller-Urey experiment, in which Miller and Urey attempted to simulate the chemical conditions that might have prevailed early on in the life of the Earth. They used electrodes to create lightning-like sparks that passed through a vapour that was formed of water, methane, ammonia and hydrogen, and found that they produced complex amino acids, which are essential building blocks of life.
What relevance would this experiment have for a computer simulation? My view is that one should not necessarily try to produce a virtual Miller-Urey experiment (complete with virtual lightning, virtual ammonia, etc.) but that the experiment does raise a couple of questions that it is essential to address.
A fundamental fact about life as it exists in the physical world is that it is carbon based. The great virtue of carbon is that its particular bonding properties allow it to combine with other atoms to form molecules that are large and complicated enough to encode highly sophisticated information. So an obvious question is this.
Question 1: Should one design some kind of rudimentary virtual chemistry that would make complicated “molecules” possible in principle?
The alternative is to have some very simple physical rule and hope that the chemistry emerges from it (which would be more like the Game of Life approach).
This is just one example of a general tension. The more features you design into a model, the less “universal” it becomes and the less convincing it is as a demonstration of the inevitability of life. However, one can also argue for at least some designed features. After all, if we want to explain the origin of life, it is not necessary to start with a virtual Big Bang and get from there to the possibility of complex molecules. It may be that designing rules to make complex molecules possible (and then arguing that with probability 1 this possibility is actually realized) is attacking the problem at the correct level.
I do not have a strong view about what the right answer to this question is. Obviously I would prefer the chemistry to emerge as if by magic, but that may be an unrealistic hope.
The second question does not arise directly out of the Miller-Urey experiment, but it is related.
Question 2: How large and how complicated should we expect “organisms” to be?
A real-world organism, even a micro-organism, is made out of more atoms than one could hope to simulate on a computer. (I am not certain that that last sentence is correct, but I would be very surprised if it wasn’t. Added later: Michael Nielsen tells me that there are rudimentary organisms that are so small that they could perhaps be simulated in full.) Moreover, although it has many levels of complexity, there will also be distance scales at which it is relatively simple. For example, if I look at my hand from a distance of about a yard, my skin looks smooth. Similarly, if I were to look through a powerful microscope at one of the cells of my hand, then the boundary of that cell would be reasonably smooth, rather than fractal-like. In general, it seems that if you look at a typical organism, it is not equally complicated at all distance scales, but is more like this: you take some small objects and put them together in a reasonably simple way to form bigger objects; you then use these bigger objects as building blocks for yet bigger objects; continuing this process for eight or nine (??) levels (perhaps if I knew more biology I would revise this number up considerably) you end up with a complex organism.
If that picture is roughly correct, then the number of “atoms” in a complex multicellular organism might be prohibitively large for a simulation. Is this a problem?
I think it shouldn’t be too problematic. Just as we are not trying to start with the Big Bang, neither are we trying to end with mammals. The main aim is to get to the point where evolution can take over. In particular, if a readily identifiable micro-organism appeared that could reproduce itself with small modifications, then the simulation would surely be declared a success.
Nevertheless, the question of scale remains. Would we want such a micro-organism to consist of a small handful of “pixels” that by some magic local rule gives rise to a copy of itself? Or would we want something much larger that had “smooth boundaries” at some distance scales and was composed of “complex molecules”? My inclination at the moment is to prefer the second for two reasons: it is less like the Game of Life (and therefore more likely to be novel and interesting) and it is closer to the life forms that we actually observe.
Added later: I haven’t quite made clear that one aim of such a project would be to come up with theoretical arguments. That is, it would be very nice if one could do more than have a discussion, based on intelligent guesswork, about how to design a simulation, followed (if we were lucky and found collaborators who were good at programming) by attempts to implement the designs, followed by refinements of the designs, etc. Even that could be pretty good, but some kind of theoretical (but probably not rigorous) argument that gave one good reason to expect certain models to work well would be better still. Getting the right balance between theory and experiment could be challenging. The reason I am in favour of theory is that I feel that that is where mathematicians have more chance of making a genuinely new contribution to knowledge.
This entry was posted on November 7, 2009 at 12:01 am and is filed under polymath. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.