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 
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 
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.
November 7, 2009 at 12:29 am |
Life evolved in an environment where there is low entropy energy flowing in and higher entropy energy flowing out. Observationally such systems thrash around looking for maximum entropy production (MEPP: Maximum Entropy Production Principle). We also note that life increases the entropy production of the Earth (intelligent life even more so). So it seems like life is a part of Earth’s search for maximum entropy production. At any rate I suspect you need something which produces a lot of chaotic but self-organizing behaviour on various scales. You also need something (like carbon chains) that can get complex when it finds itself in an area of usefully low entropy. I’d also guess that you need a fractal dimension more than 2, if not all the way to 3.
November 7, 2009 at 8:46 am |
This isn’t directly applicable but might give some inspiration:
“Crystal Nights” is a short story by Greg Egan (online at http://ttapress.com/553/crystal-nights-by-greg-egan/ ) that describes a computer simulation of the evolution of consciousness. He doesn’t talk about how the first replicator in the story was made, but the way he sets up biology is interesting:
“The basic units of biology here were ‘beads’, small spheres that possessed a handful of simple properties but no complex internal biochemistry.”
The creatures in the story go on to physically rearrange their own beads as part of reproduction:
“…reproduction involved two Phites pooling their spare beads and then collaborating to ‘sculpt’ them into an infant, in part by directly copying each other’s current body plans.”
Getting all the way up from Miller-Urey amino acids to whatever the first self-replicator was seems hard. However, maybe a way to approach the problem would be to have the building blocks be larger, and a little more functional, like Egan’s beads.
If they get too functional, to the point at which one of the built-in axiomatic functions of a bead is to make a replica of itself, then this is too much like cheating, but perhaps we can attempt to simplify the axioms down from such a system rather than complicating the axioms up from Conway’s game of life. As the axioms for the beads get less directly about replication, one would expect the numbers of beads needed for a replicator to go up, but perhaps not so far up that it becomes impossible to simulate.
November 7, 2009 at 9:42 am |
Douglas Hofstadter suggested a genetic model in Gödel, Escher, Bach.
The emergence of complex systems probably has to be handled at a range of descriptive levels to keep the computing under control.
eg at two levels –
(i) (atomic) does this system give rise to entities with genetic properties?
(ii) (genetic) are these genetic properties sufficient to produce self-replication, survival etc?
Such a multi-level description – if one is computing at the genetic level – creates the opportunity for events at the atomic level to intrude as apparently random fluctuation/disturbances at the genetic level. One can then ask ‘how robust is this system against such “random” events’.
I think the fractal idea may be misleading, since it invites the suggestion that the description of the system will be similar on different scales. It may be necessary for the description to be radically different on different scales.
One really interesting question which may arise is ‘how fine-tuned do the parameters have to be to make this work?’.
November 7, 2009 at 6:23 pm |
There are some interesting comments here about levels, and that is clearly something that needs to be thought about hard. Henry, your idea of a top-down approach is an interesting one that chimes with thoughts I have had about how one could in principle argue convincingly that computers can do maths. The idea in the latter context is that if you want to argue that computers could have thought of a proof of theorem T, you don’t actually have to show how they would do the whole thing. Rather, all you have to do is show how a computer could, in reasonable time, come up with a reduction of T to problems that are strictly simpler. Then induction does the rest. To put it contrapositively, to demonstrate that computers cannot do maths, you would need to find a statement and a proof of that statement and argue that there is no algorithmic process that could have come up with the general structure of the proof. (A simple example might be if there was some “magic lemma” L such that both L and the implication of T from L are easier than T, but there was no convincing way of explaining how to come up with L. But how does one come up with such an example …?)
Returning to the question at hand, perhaps the right thing to try to do is identify something that deserves to be called “the level just below life”, where you have fairly complicated chemistry, say, or even proto-biology, but you don’t quite have structures that reproduce themselves. You then try to show that life does, with high probability (perhaps only if certain parameters are within friendly ranges), emerge from the promising soup of not-quite-life.
Having done that, the task is reduced to explaining the emergence of the promising soup, which is a strictly easier question. (It might not be easy, but it should be easier.) And perhaps there would be several levels before one got down to something like simple cellular automata.
Returning to the top-level question, perhaps one would be trying to devise something a bit like a cellular automaton, but where the basic objects are not bits, but complicated structures that can combine and split up in interesting ways.
Mark, obviously what I’ve just said also relates closely to your comment. I agree with your view that one should be cautious about fractals, though it does seem that a lot of people jump from “fractals can appear in simple processes” to “biological complexity can be the result of simple processes”. What biology clearly does exhibit is interesting features at many different distance scales, but that is of course not the same thing as fractal structure.
November 7, 2009 at 6:56 pm |
It looks like a step along the top down approach might have already been made. From http://en.wikipedia.org/wiki/Digital_organism :
“In 1996, Andy Pargellis created a Tierra-like system called Amoeba that evolved self-replication from a randomly seeded initial condition.”
A quick descriptive writeup is here: http://www.cs.manchester.ac.uk/~toby/writing/PCW/life.htm
The ‘beads’ here have a lot of built in structure, but it doesn’t quite seem like cheating:
“The genetic code of each cell is a sequence of up to 30 computer instructions, chosen from a repertoire of 16 possible instructions. These are based on standard operations such as ‘jump to address’, ‘copy contents of memory location A into memory location B’, and ‘compare registers and skip next instruction’. Pergellis has carefully designed his instruction set such that it is possible to create a self-replicating cell with only 5 instructions”
Producing the soup might not be easier in this kind of case, when so much of the copying structure is built in.
There is something to think about here, in what combination of simplicity of soup and surprisingness that the soup produces a self-replicator would be a satisfying answer to the question.
November 7, 2009 at 7:40 pm |
That’s a very interesting pair of references. As you say, what Andy Pargellis did is at a very high level, but it is pretty similar to the kind of thing I was describing in my previous comment. So maybe the appropriate first challenge is not getting self-replicating code from randomish code, but getting any kind of code at all from something that is interesting but that does not yet deserve to be called code.
To put that more negatively, what is unsatisfactory about Paregellis’s simulation is that the he doesn’t just create life-forms but he also creates an environment that knows how to interpret the life-forms as instructions for doing things. But how does that situation arise? Perhaps the main goal, at least to start with, shouldn’t be self-reproducing beings but the more basic phenomenon of structures that in some sense encode implementable instructions.
It could be that some fundamental questions would need to be addressed. For instance, we like to think about computational models, and there is a temptation to make them rather efficient. But the computational structures that could emerge through natural chemical processes are probably very different and full of huge redundancies. (At a higher level, these redundancies appear in Pargellis’s self-reproducing life-forms, which I find very interesting.) So perhaps one would need to think hard about computational models and about what it means for a structure to encode a set of instructions that can be implemented.
November 7, 2009 at 7:57 pm |
[...] http://gowers.wordpress.com/2009/11/07/polymath-and-the-origin-of-life/ [...]
November 7, 2009 at 9:35 pm |
A few observations about stability and geometry:
It looks like Amoeba’s self replicators are something like combinations of up to 30 of the 16 instructions in a cell, which when run, copy themselves to other cells. They would therefore have reasonably good stability: their structure lives in one cell, and nothing much else in the environment will mess that structure up.
In contrast, meaningful structures in Conway’s game of life are very fragile. It doesn’t seem possible to create a “protective shell” around a structure, that can survive the kinds of random things that one might see in the environment. Similarly, if we move a small part of a structure a little, that change will generally destroy the entire structure.
This behaviour is very different from real life life (RLL), which has resilience and deals with lots of randomness. Everything happens probabilistically, and eventually the right protein and amino acid get together and the next step happens. Amoeba looks like it gets around this issue by having the cells generally protected from incursion from randomness: a cell with random code in it will be unlikely to do bad things to other cells.
Moving onto geometry: rigid geometric rules such as in Conway’s game of life would seem to be too fragile. Amoeba and other “code” life simulations work with only very basic geometric structure, perhaps the environment is a complete graph on some number of vertices, and in each vertex the structure is just a list of commands. In order to pare this back to a less code-like system we would have to break up the instructions, and with nowhere to “put” different parts of an instruction within one of the vertices, this seems difficult.
RLL has real 3d geometry of course, but the way that molecules combine has something of the features of the complete graph as well, in that it’s fine to just wait around until the right molecule bumps into the right receptor. Simulating millions of molecules bumping around is hard, but the effect is as if the receptor has a certain probability of meeting any of the “complete graph” of things sloshing around in the vicinity of it. Once however it does meet the right molecule the geometry of how the added molecule interacts with the existing structure really does matter.
This is connected somehow with the idea that there has to be different levels of “stickiness” of how different elements of the simulation interact: whether when two objects meet they glue together strongly, weakly, break apart some other connection or just bounce off. In Conway’s game of life there is only one level of this kind of interaction, which leads to the brittleness. In RLL there are a huge number.
November 8, 2009 at 5:38 am |
I have just a few quick, possibly disjointed, thoughts about this that are intended to be provocative.
Is an object a living thing if it is the only living thing in its environment? If so, what distinguishes it from a crystal? Certainly a crystal is self-organizing, even if passively so. I’ve always felt that the notion of a living thing requires a sub-notion of otherness, and that the duality of otherness is one of the most basic organizing principles in the soup of life we have on this planet. This is not philosophical speculation plucked out of thin air. Even a very young child realizes that virtually every other conscious being around them, whether other humans or the squirrel in the tree, has a sense of self and not-self. Indeed, without this sense of self and not-self we would probably experience severe hallucinogenic disorientation if we aren’t in fact quickly eaten by something else. But self/not-self is not exclusive to consciousness. Our entire immune system, from skin to cell walls to the highly complex set of cells and messaging cytokines that comprise the adaptive immune system, grapples with this every day in fending off viruses, bacteria, and parasites that degrade our self-integrity, possibly to death. Distinguishing between self and not-self is a tough problem for the immune system (and immunology), and failure is all too common when autoimmunity develops as an accidental byproduct of the adaptive immune system fighting infections. (One could also argue that the brain was originally an extension of the immune system, and inherited the self/not-self duality from the immune system.) Perhaps a living thing is that which actively maintains a stable morphology by playing the self/not-self game on many different levels.
I can’t leave without asserting that the self/not-self game does not imply that selfishness or super capitalism are the natural order of things; they are quite different things. My own immune system recently came to the fore of my thoughts when I wound up in the hospital at age 58 with a mystery infection that either looks, walks, and quacks like the measles I had fifty years ago, or was a biological warfare experiment.
November 8, 2009 at 12:57 pm |
Incidentally, I found quite a nice blog post on the origin of life and the various stages that might have been needed. The author of the post is very concerned to argue against creationists, but that argument isn’t a big feature of what he writes, which is mostly just interesting science. It can be found here.
November 8, 2009 at 1:55 pm |
[...] presentation of one possible near future polymath: the mathematics of the origin of life can be found on Gowers’s blog. Leave a [...]
November 8, 2009 at 4:37 pm
I’d just like to mention that if you click on the link of the pingback above (which was created by Gil Kalai), not only do you get a rather nice volcano graphic, but if you click on that graphic you are taken to another web page that has a useful summary of current thinking about how life may have arisen.
November 8, 2009 at 8:31 pm |
I thought I would make a small comment about self-replicating systems: There is an old theorem of Kleene (Kleene’s second recursion theorem), a corollary of which is that in any sufficiently rich, general purpose programming language, there exist arbitrarily complex `quines’, which are programs that reproduce their own output when run on empty input — i.e. they self-replicate… in a sense. If one could interpret interacting collections of atoms as a type of “computer program”, and if the possible interactions are sufficiently rich (so that the laws of physics restricted to the particular domain under consideration effectively constitutes a general-purpose programming language), then it seems to me that arbitrarily complex self-replicating systems are guaranteed to exist. Of course, the property of self-replication is only necessary, not sufficient, for the system to be deemed “alive”.
November 9, 2009 at 10:23 pm
This idea that sufficiently rich systems contain the capacity for self-replication had occurred to me, and I was going to look it up. (NB pretty much every ’sufficiently rich’ system can replicate some form of programming – albeit very inefficiently in some cases eg Conway’s Life).
Another version of programmed ‘life’ is seen in the repeated playing of the ‘Prisoner’s Dilemma’ – eg Axelrod’s “Evolution of cooperation” – which never really convinced me because the differences between good strategies are marginal – but it does show that there are robust survivors in a competitive environment.
Anyhow, there seem to me to be some ideas worth exploring:
(i) Conservation principles creating a competitive environment
(ii) Entropy – limiting the total order of the system
(the “Life” Glider Gun potentially produces unlimited order – good structure would perhaps avoid this)
(iii) And there is something less tangible about there being self-replicating systems which in some sense form open sets, rather than being isolated points. This would allow for the existence of resilient self-replicators.
November 8, 2009 at 8:31 pm |
I’m very intrigued by these ideas though concerned about “loose talk”. And speaking of loose talk, I have a few ideas I seldom voice to anyone (people look at me as though I am insane when I do). It concerns property 3 above…. If a system has some non-trivial randomness about the way it evolves, then for any fixed initial conditions the possible states at time N will be exponential in N (at least for a little while, until you run into constraints such as the ability of the system to harbor many distinct states). There will be so many states that even if the design is very bad, at least some of the states might be interesting, and look a lot like “life”. So the possibility of “life” doesn’t necessarily require a very good automaton. The only alternative I ever see discussed, though, is finding an automaton where “life” is inevitable, i.e. will arise with probability approaching 1. This seems to be what you are looking for here as well.
What if the physical universe isn’t like that, though? What if, in fact, the probabilities you get out of quantum mechanics produce life with a vanishingly small likelihood (albeit better than coin tossing, presumably)? You could think of all the states existing in parallel. Very few of them exhibit anything resembling life. But, the ones that do have life are the ones where the conscious entities (the “psychons”) are hanging out…because that’s where they want to be, where interesting things are going on–when wave functions collapse, they don’t divide, they go where things are more interesting.
The point about this is that if things did work this way, you wouldn’t run into any limitations in calculation resources….not existing in the physical universe and unbound by time constraints, psychons could in theory perform an enormous lookup or even cheat by being somewhat prescient…I suspect they could do this and still evade detection by suspicious experimenters; in brains for example the chaotic nature of the activity would make it virtually impossible to connect specific firings with their teleological import, so what on earth would you even test for?
A pessimistic viewpoint, but somewhat close to my viewpoint.
November 8, 2009 at 10:44 pm
I agree that what you call loose talk is a worry. One of the things I was hoping to discuss in this thread is whether there is any hope that a Polymath project could achieve anything. On the plus side, it does seem like a project where expertise of many kinds is required: knowledge of mathematics, chemistry, biology, programming, etc. But would it be possible to formulate questions that were precise enough for it to be clear when they had been solved? For example, one question that has already arisen is this: if it is correct to say that a biological system operates at many levels, then how many of those levels, and which ones, should one try to simulate? That seems like an important question, but can one do more than (i) discuss it in a loose way and express hunches about it, and (ii) experiment with some simulations and see what happens? If there is nothing in between — some kind of analysis of what is likely to work and why — then how might a project work?
I suppose one possibility might be that someone volunteers to write a program based on some ideas that emerge from the conversation, the program exhibits behaviour that one doesn’t completely expect, and then one attempts to understand the model well enough to explain why it behaves as it does, perhaps using that analysis to devise better models. But for that to work, we would need some skilled programmers, which I for one am definitely not.
November 9, 2009 at 2:08 am |
About which form of live we may find:
Many religions claim exsistence of spirits. Christianity tells about living spirits (in Bible the word spirit is literally translated “wind”). So Bible tells us that living winds exists.
BTW, I do not only believe in existence of spirits but also has seen some spiritual anomalies such as clouds taking form of some objects such as a cloud in the form of an airplane.
I assume that spirits are living creatures living in Navier–Stokes equations or in some variation of these equations. (But I may mistake, spirits could be alternatively bacteria living in clouds.) Further I will suppose that spirits are living solutions of Navier–Stokes equations.
Navier stocks equations are relatively simple to model. But if we search for spirits (living winds), we do not know what we are searching for. Do separate winds have geometrical shape? Are they “separated” from each other whatever this word means, or all spirits in one big organism? Are spirits small “fluctuations” on the ground of macroscopic wind structures? Do spirits communicate with each other trough sound waves? Or maybe electromagnetic waves in the ionosphere is a part of the life of spirits? After all in the current level of development of mathematics we know nothing about Navier–Stokes equations, how we could know anything about spirits?
Currenly the only way I know to find existence of a spirit is when it would show some intelligent sign, like the above mentioned airplane. Mathematically modelled spirits on current computers certainly cannot reach so high intelligence to understand what is an airplane and how to show it. So even if we will produce a spirit in a computer model, we do not know how to notice that it exists.
After all, if to believe Bible, spirits reached (or it was always so after big bang) the level of development so high that they may create protein life.
November 9, 2009 at 11:45 am |
A small thought I have is that a simulation might be something like this. You start off with a large number of extremely primitive “basic objects”, which one might think of as molecules. When I say “extremely primitive” I don’t mean that they are just single bits — either on or off. Rather, they have some very basic structure to them that affects how they interact. This is supposed to be some analogue of “chemistry”. They move about in a Brownian sort of way (as real molecules might), and when they get close they sometimes combine to form larger objects. The bonding rules, which I see as being randomized, depend on the internal structure of the objects. It is also possible for larger objects to split up into smaller ones: whether that happens would probably be partly dependent on some external temperature that could be one of the parameters that is to be set. (Incidentally, it occurs to me that rather than fine-tuning the external parameters, one might simply allow them to fluctuate, so that they would at least sometimes be in the right range.)
What I don’t yet see is how molecules themselves would form groups that were not themselves huge molecules. It seems as though there would have to be bonding rules corresponding to chemical reactions and different bonding rules that cause distinct molecules to stick together.
At the moment, it seems to me that the big leap is getting to the point where molecules can act as a kind of code that is “understood” by the rest of the system. But this shouldn’t be impossible, as Ernie Croot points out. After all, the whole point of computation is that it reduces complicated algorithms to a series of very simple mechanical steps. So perhaps if one had a “soup” of extremely primitive machines (things like, “If I see a particle of type B, I convert it into a particle of type A and become myself a particle of type C”) together with some mechanism for such machines to hook up with each other, they might combine (given the right selection pressures) to form much more complicated machines.
November 13, 2009 at 2:07 am
Catalysis seems to be a very important example of such a code in real systems. Effectively:
if catalyst present
then X and Y combine to form Z
else X and Y stay the same
November 13, 2009 at 2:50 am
And, of course, the reverse reaction can also be catalysed, e.g., Z disassociates to produce X and Y.
Much more complex reactions can also be catalysed, but to produce computational universality, these two simple types might come especially in handy.
November 11, 2009 at 11:44 am |
[...] 11, 2009 Hold your breath … Tim Gowers proposes a poymath project to answer the question about the origin of life scientifically [...]
November 12, 2009 at 6:26 pm |
Cosma Shalizi has done some interesting work on the topic of self organization and attempting to come to a more formal understanding of what self-organization is. I’m not sure whether this is the same sort of life as people are thinking, but its certainly closely related. One idea that he discusses is thinking about the complexity of a time series in terms of the amount of information needed to predict future states. This could provide an interesting starting point.
intro-link plus lots of references towards the end:
http://cscs.umich.edu/~crshalizi/notebooks/self-organization.html
talk:
http://cscs.umich.edu/~crshalizi/Self-organization/soup-done/
phd thesis:
http://cscs.umich.edu/~crshalizi/thesis/
paper:
http://arxiv.org/abs/nlin.AO/0409024
November 12, 2009 at 7:08 pm |
(I meant to include this part in the original comment)
Self-organization, then is defined in terms of a dynamical system whose “statistical complexity” (measured in terms of the information required to infer future states) is increasing without outside intervention.
Intuitively, this seems a lot like life: for any living thing we need a tremendous amount of data and information to predict future states of the organism. One thing (among many) that is lacking in this sort of definition though, is a notion of homeostasis and self-reproduction.
I’m curious as to whether self-organizing systems merely become self-reproducing once they reach a particular point.
November 13, 2009 at 1:42 am |
On whether there are living organisms in the real world that could be simulated in full, let me add a remark qualifying my earlier comment: the smallest organisms that I know of which self-replicate autonomously are bacteria which are a few hundred nanometers on a side. (Viruses can be smaller, but don’t self-replicate without additional machinery). That’s a volume of tens of billions of cubic angstroms. Assuming conservatively that an atom occupies about a cubic angstrom, that means the total number of atoms will be at most tens of billions, and probably far less.
Now, to what extent it’s possible to simulate that depends on how much you’re willing to build in. My understanding is that first principles simulation even of, e.g., very simple proteins is well beyond us now. But if one took as given many of the empirically observed properties of the molecules involved (not to mention the surface physics, and so on), then the interesting point to take away is that the sheer number of particles is not itself prohibitive.
November 13, 2009 at 3:23 am |
I have been interested for a long time in this question so I can’t resist to comment.
First of all many comments indicate the need of some randomization to make the model less rigid. But what is the minimal complexity of a probability space that is enough for the formation of life?
(life itself is a low probability event if we look at life/space ratio in the universe)
Already in quantum mechanics the probability space seems to be of a higher complexity then just a bunch of independent events, let’s says, at the vertices of a certain grid.
But here is an even more drastic speculation:
Quantum mechanics is consistent with a branching model of the universe.
Such a model increases the probability enormously that in one branch interesting life forms appear. So the branching model is a much more complicated probability space, but it is almost impossible to model on computers.
This is of course just crazy speculation. I am also optimistic that a simple linear time model with local rules and randomization can produce surprising structures. An interesting try would be to allow some kind of “evolution” of the local rule itself.
November 13, 2009 at 5:56 am |
It seems to me that momentum conservation is perhaps not so essential for being “realistic”. After all, organisms living (walking) on the surface of the Earth do not see momentum being conserved; you can basically start moving from rest without needing to throw stuff in the opposite direction for propulsion. Of course this is because Earth is huge and you do not observe the momentum it gains when you start moving by pushing it with your feet. One may also argue that inter-organism interactions (collisions!) should be enforced to conserve momentum, even if “Earth-organism” interactions seemingly don’t. I guess my point (without going too much into these detailed issues) is, if you somehow end up with an artificial world with “interesting” “beings”, the violation of certain laws of physics may not necessarily be reason to discard it as unrealistic, and ignore the insights that can be gained from it. In other words, we certainly will do away with *some* laws of physics in the artificial world, and it may be worth thinking hard before deeming a law essential.
November 13, 2009 at 4:25 pm
I think that the main importance of conservation laws (in real life) is that they don’t let the system go “crazy”. But I agree that in computer simulations this can be controlled in other ways as well.
November 13, 2009 at 11:54 am |
[...] Polymath and the origin of life « Gowers’s Weblog [...]
November 13, 2009 at 7:57 pm |
Shouldn’t you at least take a glance at the work of Manfred Eigen or Stuart Kauffman?
November 14, 2009 at 12:32 am
Absolutely. I’ve got Kauffman’s book (origins of order) and plan to read it before I’m too much older. I have to confess that I hadn’t heard of Manfred Eigen, though the name somehow rings a bell, so thank you for that and I will look into it. Obviously, one important preliminary is to come up with a goal that was not too close to things that have already been done.
November 13, 2009 at 8:32 pm |
I seriously doubt it, but maybe Gregory Chaitin has some useful thoughts in the subject here: http://www.cs.umaine.edu/~chaitin/jack.html
November 14, 2009 at 2:12 am |
[...] Polymath and the origin of life « Gowers’s Weblog (tags: math bio evolution complexity cellular-automata self-organisation self physics) [...]
November 14, 2009 at 5:35 am |
3 Definition of Life
by
Jonathan Vos Post
Annotated text version with citations of graphic PDF Venn Diagram of September 2009
Version 1.0 of 9 Nov 2009, 4 pp., 1400 words
My graphic is a Venn Diagram. The three overlapping circles contain text summarizing these 3 main definitions: The diagram as whole gives my tentative “original” composite definition of life which combines the main 3 definitions given:
“A self-assembled, self-contained negentropic chemical system network of feedback mechanisms capable of undergoing Darwinian evolution.”
There was also a polygonal box with the following text, as the cited article initiated my composition of the diagram: “see pp.56 ff ‘What is Life’ of ‘Origin of Life’ by Alonso Ricardo & Jack W. Szostak, Scientific American, September 2009.”
I. Cybernetic Definition
“A network of inferior negative feedbacks (regulatory mechanisms) subordinated to a superior positive feedback (potential of expansion, reproduction).” [Korzeniewski, 2001]
Summarized for the graphic [by JVP] as: “A network of feedback mechanisms”
I had an arrow from the word CYBERNETICS pointing to this part of the circle, and an arrow pointing from it to a box containing the text: “Best fit to theory of ‘Metabolism First’ as opposed to ‘RNA First’ Biogenesis, network of catalysts which process energy.”
II. Schrödinger’s Physics Definition
Summarized for the graphic [by JVP] as: “Self-assemble against nature’s tendency towards entropy (disorder) (i.e. negentropy). [Note: this was historically the first of these]
I had an arrow from the word PHYSICS pointing to this part of the circle, and under the arrow the text: “Schrödinger also predicted before DNA structure known : 1-dimensional aperiodic crystal.”
I drew an arrow pointing to it to a box containing the text: “Self-assemble” as opposed to assisted self-assembly on mineral substrate such as Clay (Jim Ferris et al.)”
III. Chemistry Definition
“Life is a self-sustained chemical system capable of undergoing Darwinian evolution.” [Joyce]
Summarized for the graphic [by JVP] as: “Gerald Joyce’s ‘working definition’ adopted by NASA: ‘self-sustained chemical system capable of undergoing Darwinian evolution.’ Note: Panspermia allows the Darwinian evolution to have started on another planet or body.”
I drew an arrow pointing to it to a box containing the text: “If we leave out Gerald Joyce’s ‘chemical system’ we cannot simply exclude software ‘artifical life’ in silico — or more exotic substrates.
I drew an arrow pointing from that box to a box wit the text: “Questions: in regions combining only 1 or 2 of these definitions, what counterexamples are possible?”
There was also a rectangular box in the upper right hand corner which read: “Venn Diagram copyright © 2009 by Jonathan Vos Post.”
The overlapping areas of the Venn Diagram
I/II. Cybernetics + Physics
Summarized for the graphic [by JVP] as “self-assembled negentropic network of feedback mechanisms”
II/III. Physics + Chemistry
Summarized for the graphic [by JVP] as “self-assembled, self-sustained negentropic chemical system capable of undergoing Darwinian evolution.”
I/III. Cybernetics + Chemistry
Summarized for the graphic [by JVP] as “self-contained network of feedback mechanisms capable of undergoing Darwinian evolution.”
I/II/II. Cybernetics + Physics + Chemistry
“A self-assembled, self-contained negentropic chemical system network of feedback mechanisms capable of undergoing Darwinian evolution.”
Further clarifications and discussions.
To clarify Schrödinger’s Physics definition, although many non-physicists persist in stating that life’s dynamics somehow go against the tendency of second law (which states that the entropy of an isolated system tends to increase), the definition assuredly does not in any way conflict or invalidate this law. This is because the principle that entropy can only increase or remain constant applies only to a closed system (i.e. one which is adiabatically isolated, so that no heat can enter or leave). Whenever a system can exchange either heat or matter with its environment, both of which apply to the planet Earth and its ecosystem, an entropy decrease of that system is entirely compatible with the second law.
In more modern terminology, life is a dissipative system. A dissipative system is characterized by the spontaneous appearance of symmetry breaking (anisotropy) and the formation of complex, sometimes chaotic, structures where interacting particles exhibit long range correlations. The term dissipative structure was coined by Russian-Belgian physical chemist Ilya Prigogine, who was awarded the Nobel Prize in Chemistry in 1977 for his pioneering work on these structures, some of which rediscovered my research on what I call “enzyme waves.”
As chemist John Avery explains in his 2003 book Information Theory and Evolution, we find a presentation in which the phenomenon of life, including its origin and evolution, as well as human cultural evolution, has its basis in the background of thermodynamics, statistical mechanics, and information theory. The (apparent) paradox between the second law of thermodynamics and the high degree of order and complexity produced by living systems, according to Avery, has its resolution “in the information content of the Gibbs free energy that enters the biosphere from outside sources.” The process of natural selection responsible for such local increase in order may be mathematically derived directly from the expression of the second law equation for connected non-equilibrium open systems
The “Ferris et al” and clay text summarizes the fact that when free nucleotides are combined in water solution, they do not react at all. Hence various teams of scientists have searched for what types of activating groups and inorganic catalysts must have been involved in the polymer bonding process. Dr. Ferris, of Rensselaer Polytechnic Institute in Troy, New York, discovered one inorganic material which facilitates this reaction, namely montmorillonite clay. The specific structure of this clay can provide a medium on which the individual activated RNA units combine to form larger chains.
REFERENCES:
Avery, John (2003). Information Theory and Evolution. World Scientific. ISBN 981-238-399-9.
.
Dr. James P. Ferris. “Montmorillonite Catalysis of RNA Oligomer Formation in Aqueous Solution. A Model for the Prebiotic Formation of RNA.” Journal of the American Chemical Society. 1993, 155, 12270-12275.
James P. Ferris is Director, New York Center for Studies on the Origins of Life
Gerald Francis Joyce, “The RNA World: Life Before DNA and Protein”.
Professor Gerald Francis Joyce (born 1956) is a researcher at The Scripps Research Institute. His primary interests include the in vitro evolution of catalytic RNA molecules and the origins of life. He was elected to the National Academy of Sciences in 2001.
Joyce received his Bachelor of Arts from the University of Chicago in 1978, completed his M.D. and Ph.D. at the University of California, San Diego in 1984, and joined Scripps in 1989. Joyce, quoted in commentary in Science (1992): “Obviously, Harry [Noller]’s finding doesn’t speak to how life started, and it doesn’t explain what came before RNA. But as part of the continually growing body of circumstantial evidence that there was a life form before us on this planet, from which we emerged – boy, it’s very strong!”
Korzeniewski, Bernard (2001). “Cybernetic formulation of the definition of life”. Journal of Theoretical Biology. 2001 April 7. 209 (3) pp. 275–86.
Prof. Bernard Korzeniewski’s home page,
http://awe.mol.uj.edu.pl/~benio/
Faculty of Biochemistry, Biophysics and Biotechnology, Jagiellonian University, ul. Gronostajowa 7, 30-387 Kraków (Krakow), Poland
e-mail: benio@mol.uj.edu.pl
Alonso Ricardo and Jack W. Szostak, , “Origin of Life”, Scientific American, September 2009.
Schrödinger, Erwin (1944). What is Life – the Physical Aspect of the Living Cell. Cambridge University Press. ISBN 0-521-42708-8.
in the famous 1944 book What is Life?, Nobel-laureate physicist Erwin Schrödinger theorizes that life, contrary to the general tendency dictated by the Second law of thermodynamics, decreases or maintains its entropy by feeding on negative entropy. In a note to What is Life?, however, Schrödinger explains his usage of this term:
“Let me say first, that if I had been catering for them [physicists] alone I should have let the discussion turn on free energy instead. It is the more familiar notion in this context. But this highly technical term seemed linguistically too near to energy for making the average reader alive to the contrast between the two things.”
November 14, 2009 at 6:37 am |
More possibly relevant references are the books by Cairns-Smith,”Seven Clues to the Origin of Life”, and by Freeman Dyson, “Origins of Life”. I haven’t read the latter, and don’t know how useful it is. Cairns-Smith’s book was stimulating (but non-mathematical).
November 14, 2009 at 8:16 am |
I cite the mineral substrate theory elaborated by Cairns’Smith in my long submission. Also, to be historical:
Jonathan Vos Post
Charles Darwin’s famous passage in a letter he mailed to his close friend Joseph Dalton Hooker on March 29, 1863, in which he wrote that “…it is mere rubbish thinking, at present, of origin of life; one might as well think of origin of matter”. But yet, in a now famous paragraph in the letter sent to the same addressee on February 1st, 1871, he stated that “it is often said that all the conditions for the first production of a living being are now present, which could ever have been present. But if (and oh what a big if) we could conceive in some warm little pond with all sort of ammonia and phosphoric salts,—light, heat, electricity present, that a protein compound was chemically formed, ready to undergo still more complex changes, at the present such matter would be instantly devoured, or absorbed, which would not have been the case before living creatures were formed [...]“.
Darwin, C. Written in 1871, published in 1887. The Life and Letters of Charles Darwin, including an autobiographical chapter, vol. 3. London: John Murray, 18.
November 14, 2009 at 8:09 pm |
Michael Nielsen made a very interesting comment about catalysis and its potential to be used as an element of code. It’s clear that very simple elements like that would be extremely useful.
Suppose, then, that we had a number of such elements that could enable us to simulate AND, OR and NOT gates, say. What would cause these basic computational operations to occur in a given order? Does anyone have any knowledge of how this happens in the biological world? (This may not be a very good question: perhaps the computational model that you get in biology is so different from the one we normally use — even if in theory of equal power — that we shouldn’t be thinking in terms of a long sequence of simple operations. But how in that case should the question be formulated?)
November 14, 2009 at 9:42 pm |
“Does anyone have any knowledge of how this happens in the biological world?” Well, my PhD dissertation included this question, and I have been presenting paperts at conferences on Complex Systems, where I listen to, and chair sessions on, Biologists, Chemists, Physicists, Mathematicians alike.
Short answer: I think that it is a philosophical category error to refer to the logic in a catalytic, autopoeitic, metabolic, or genetic regulatory network as ANY of {Analog, Digital} as it is very different from either. Hence it is Not Even Wrong to claim that AND, OR and NOT gates occur in living cells. However, as discussed in my Dissertation, one can BUILD AND, OR and NOT gates into a slightly modified living cell or even simpler system, which is part of what Synbio (Synthetic Biology) is about. The latter field being very active, with hundreds of teams of thousands of people, and parts kits available as trays of samples of dry DNA that is used to make the suite of hundreds of available parts, out of which people can build real (not simulated) wet biochemistry systems, which can indeed perform AND, OR and NOT gate functions in useful ways.
November 14, 2009 at 11:31 pm |
Your answer rather confirms my suspicions, and I think that means that one can begin to identify a subgoal that a Polymath project along these lines would have to have. It ties in with the question of how such a project would differ from what Andy Pargellis did. (See this comment for a link to a description of Pargellis’s work.) The way I see it, one would like to have some notion of a molecule encoding a set of instructions and those instructions being obeyed. One would also like these types of instructions to be powerful enough to simulate any computation. However, almost certainly the model of computation should be quite different from usual models, in stark contrast with Pargellis’s organisms, which were explicitly set up to be conventional (if primitive) computers.
The subgoal I was thinking of was to describe a computational model that was “biologically realistic”. From what you say, there may already have been important work along those lines, in which case I’d be interested to know of references.
If one could come up with such a model, then devising a process that led, with high probability, to implementations of the model emerging, would be an obvious next subgoal. I think only after those two subgoals had been achieved would it even make sense to think about trying to get to the stage of self-reproducing organisms, though Pargellis’s work suggests to me that maybe getting any sort of computation going is the more fundamental challenge, and that self-reproduction can be expected to emerge sooner or later once you have a set-up where the computations that take place can potentially increase in complexity.
Added later: I’ve just spotted this blog post. It doesn’t seem to be exactly what I’m talking about, but it’s certainly interesting and I think some of it is in the same ball park.
November 15, 2009 at 8:31 pm |
Identifying criteria of success for this project requires identifying what is characteristic of life. I would argue that it is *not* necessarily natural selection acting on self-replicating entities. The simplest self-replicating entities may be so complex that they could not have arisen by chance in a finite universe. If so, then an alternative mechanism is required to explain their emergence. Granted, success in simulating life’s origins might always be recognized by the eventual emergence of self-replicating entities, but it may be that the path to such emergence is quite long. So it might be wise not to insist too strongly on property 7.
I would argue that a more generic view of what is characteristic of life is *the emergence of complexity from simple laws acting over long periods of time*. From this perspective, the first order of business would be to determine what precise notion of complexity is at work here. One can then evaluate the performance of any given model of life’s origins by whether and in what manner the appropriate measure of complexity increases. In other words, I’m proposing that property 2 should be emphasized and should be cashed out in terms of a measure of complexity.
It would be useful if someone who knows this field better than I do could provide the key references. The chapter entitled “Complexity and Evolution” in “Complexity, Entropy and the Physics of Information” edited by Wojciech Zurek is one.
November 15, 2009 at 8:40 pm |
One would like a measure of complexity that respects the following rough assessments: living objects are more complex than nonliving, Boeing 747s are more complex than mounds of dirt, and human beings are more complex than bacteria. What are some candidates for such a measure? Here are a few that I can think of, together with an assessment of their appropriateness. (I’ll consider the complexity of objects in a cellular automaton world rather than physical objects in the real world in order to sidestep the problem of providing a digital description of physical objects.)
i) Algorithmic complexity of the object
The algorithmic complexity of a binary string is the length of the shortest program that generates that string. More precisely, it is the shortest binary input which causes a particular universal Turing machine to produce that string as output. It was proposed by Solomonoff and independently by Kolmogorov and by Chaitin. One could obtain an associated measure of complexity for an object in a cellular automaton world as follows: draw a line around the object and calculate the algorithmic complexity of the pattern within the boundary. Repeating patterns will have low complexity, algorithmically random patterns will have high complexity, while the interesting objects that exhibit some order (the organisms and artefacts) will have an intermediate degree of complexity. So algorithmic complexity does not fit the bill. One would like a notion of complexity for which random patterns are not deemed the most complex.
ii) Algorithmic complexity of an equivalence class of objects
A possible solution to the problem outlined above is to define complexity for a class of objects that have the same function, rather than for a particular object. After all, one isn’t really interested in the relative complexity of a particular Boeing 747 and a particular pile of dirt, but rather of the set of things that function like a 747 and the set of things that function like a pile of dirt. There is a demarcation problem here — what counts as functioning like a 747 or a pile of dirt? This may be a difficult problem or it may be that the relative complexity is not so dependent on where the boundary is placed. In any case, let’s leave the demarcation problem aside for the moment. How should we define the complexity of an equivalence class of objects? A natural choice is to take the infimum of the algorithmic complexity of its members (this was first suggested to me by Robin Blume-Kohout). It may well be that the equivalence class containing random patterns contains pseudo-random patterns with low algorithmic complexity, while equivalence classes containing organisms and artifacts with specialized functions have no elements with low algorithmic complexity. In this case, the resulting measure of complexity would be of the sort one wants.
iii) Logical depth
Charlie Bennett has proposed a different way of trying to do justice to our intuitive notion of biological complexity. He defines a measure of complexity for a string, called “logical depth”, as the execution time of the shortest program that generates that string. Noting that one might achieve shorter running times with longer programs, Bennett also defines a more refined notion of logical depth: an object’s “s-significant depth” is the execution time of a program that generates the string and is no more than s bits larger than the shortest program. The idea here is that an object is complex in proportion to the amount of computational work required to generate it. This measure judges both repeating and random patterns to be of low complexity, because programs generating these run quickly. An ephemeris (a table indicating where planets and stars will be found in the sky on various dates) has small algorithmic complexity (because it can be deduced from initial conditions and simple laws of motion) but large logical depth (because it embodies a large number of calculations). An organism having a long evolutionary history is likely to embody more computational work than ones with a short history and consequently organisms on the branches of the evolutionary tree will be more complex, by this measure, than organisms on the roots. Bennett attributes the idea of logical depth to Chaitin and specifies a number of other related references. See http://www.research.ibm.com/people/b/bennetc/utmx.ps.
Unfortunately, none of these measures are computable, but they may motivate some computable measures that could be used to assess models.
November 15, 2009 at 10:02 pm |
The general question of coming up with a measure of complexity that assigns low complexity both to regular repeating patterns and to random patterns is one that has always interested me, and even has something of a tie-in to the questions I have worked on in additive combinatorics (where highly structured objects and highly random objects are easy to deal with and the problems come in between).
When it comes to static patterns of pixels, one can do things like taking some kind of transform (such as the Fourier transform, a wavelet transform, or something along those lines), truncating it, and looking at the algorithmic complexity of what remains. I’m not saying that that kind of idea is relevant here, but just that there are things one can imagine doing that are basically along the lines of what you suggest in (ii). (Here, the equivalence relation would be “is equal, when you truncate the ***** transform, to”.)
But I think that the real equivalence relation of interest is, as you suggest, something more like “does roughly the same as”.
Another problem that would bedevil any attempt to come up with a good definition is the same one that bedevils attempts to prove lower bounds in circuit complexity: there seems to be no observable difference between random and pseudorandom phenomena. This is, I think, a problem with any notion of algorithmic complexity. For example, a highly random arrangement of particles will behave very like (and therefore be equivalent to, according to the relation quasi-defined above) an extremely simple pseudorandom arrangement. Hang on … maybe that’s good news rather than bad, as we want it to count as having low complexity. But in some funny way it appears to have low complexity “for the wrong reason”.
I still think that a fundamental question is the following basic one: what would cause one to pick out some part of the model and say that it was “doing something”? At the lowest level one might build that in (e.g. one might have simple molecules that could react with one another) but the problem would then appear at the higher level of collections of molecules. If one is not clear about this, then it is hard to see how one can even get started with defining a useful measure of complexity.
November 16, 2009 at 4:08 am |
See also this link to an integer sequence I posted which is related to “Artificial Chemistry”
http://www.research.att.com/~njas/sequences/A101145
A101145 List of molecules in Hintze-Adami artificial chemistry (see comments for definition).
Arend Hintze and Christoph Adami, “Evolution of complex modular biological networks.”
PDF of latter is
http://arxiv.org/ftp/arxiv/papers/0705/0705.4674.pdf
November 16, 2009 at 5:46 am |
one reference potentially worth considering, although largely unrelated to every other comment, is michael thompson’s recent book entitled, “Life and Action: Elementary Structures of Practice and Practical Thought.” in it, the author expounds on the difficulty of defining life in a meaningful and non-tautological way. it seems to generally be regarded amongst philosophical folk as revolutionary. i haven’t finished it yet, so i’m withholding judgement. it is entirely non-mathematical (at least, so far), but might be helpful with regard to defining our desiderata here for this project. anybody else have any thoughts on this?
November 19, 2009 at 2:16 am |
I’m part way through writing a monograph on complexity of biological networks. Specifically, neural networks (not just in the brain, my first example is the 1% of your neurons that are in your gut — could that be conscious?) and genetic regulatory networks and immune system networks and metabolic networks. In that light, and some of the discussion on this thread so far, I’ll note that this was just posted about 10 minutes ago and seems very on-topic.
arXiv:0911.3482 [ps, pdf, other]
Title: Complexity of Networks (reprise)
Authors: Russell K. Standish
Subjects: Information Theory (cs.IT)
Network or graph structures are ubiquitous in the study of complex systems. In a previous paper [arXiv:nlin/0101006], a complexity measure of networks was proposed based on the {\em complexity is information content} paradigm. The previously proposed representation language had the deficiency that the fully connected and empty networks were the most complex for a given number of nodes. A variation of this measure, called zcomplexity, applied a compression algorithm to the resuling {JVP: resulting} bitstring representation, to solve this problem. Unfortunately, zcomplexity proved too computationally expensive to be practical. In this paper, I propose a new representation language that encodes the number of links along with the number of nodes and a representation of the linklist. This, like zcomplexity, exhibits minimal complexity for fully connected and empty networks, but is as tractable as the original measure. This measure is extended to directed and weighted links, and several real world networks have their network complexities compared with randomly generated model networks with matched node and link counts, and matched link weight distributions.
November 19, 2009 at 4:50 pm |
What a great polymath project to cooperate if i had free time !!
I just can suggest one reading wich is a must regarding this matter: “The origins of life: from the birth of life to the origin of languaje” from Maynard-Smith and Szathmary. The whole thing is explained from a biological point of view but giving to the informational issues the attention they deserve. Also Kauffman ´s, wich was a pioner in biological theory is worth reading (e.g .auto-catalysis networks)…And add some quick comments:
1 If you want the model to be realistic the concept of level is fundamental. As a principle, no agent in a higher level can contradict the restrictions of the lower level (i.e. biological systems can not contradict physical laws). If not you can end with models wich are more game than life.
2 There is a consensus that the unit of life is the cell (and as it has been already pointed the simplest of cells are bacteria).
3 Cells are embedded in an environment and what they do is to extract energy from this environment and use this energy to self-mantain and replicate.
4 So any model for the origin of life must start with an input wich represents an inert physico-chemical environment with physical and chemical elements containing energy and end with an ouput wich are cell-like units.
5 Let´s see more concretelly what one would expect as ouput of the model. Let´s see a cell as a computational-robot system: the membrane would be the tape where the inputs are represented, the chemical and physical elements of the environement would be the inputs, the DNA is the memory where the inputs, the RNA are the processors and the proteins are the actuators. So the cell can be seeing as a parallel computing system. Computations are energy extraction from the environment.
6 I do not see replication per se as important. Non living flexible 3D·membranes duplicate naturally when you inject more fluid inside.·So the more energy an efficient cell gets from the environment the, quicker it will grow and naturally divide. Of course the dificult task for the cell and what must be explained by observers as us is how the cell controls this replication keeping the complex DNA-RNA-Proteins etc…machinery alive in both copies. As an aside commment, regarding duplication, one thing remains unexplained by some current biological theories: if the aim of the gene is maximize self-replication how is it the case that no cell has been found yet that effects multiplication i/o duplication ?
To conclude once you find the correct model to formalize the environment and the cells within it you will realise that the only possible path to understand the origins of life is to explain the main biological invariant wich is the non arbitrary four letters code and its semantics. And the the clue for this was already foresee by Darwin as J. Vos Post quotes: “…it is mere rubbish thinking, at present, of origin of life; one might as well think of origin of matter” (and i add of mind and of society).
November 19, 2009 at 6:03 pm |
I agree with proaonuiq. John Maynard-Smith’s books influenced me since my Caltech days (1968-1973) and through my PhD work. He was instrumental in the application of game theory to evolution and theorized on other problems such as the evolution of sex and signalling I also appreciated Szathmary’s work. Eörs Szathmáry (born 1959) is a Hungarian theoretical evolutionary biologist. Wikipedia summarizes:
Professor Szathmáry’s main achievements include:
* a mathematical description of some phases of early evolution;
* a scenario for the origin of the genetic code;
* an analysis of epistasis in terms of metabolic control theory;
* a demonstration of the selection consequences of parabolic growth;
* a derivation of the optimal size of the genetic alphabet;
* a general framework to discuss the major transitions in evolution.
I attended lectures early in grad school (i.e. 1973 and 1974)by Stuart Alan Kauffman (born 28 September 1939) who is an American theoretical biologist and complex systems researcher concerning the origin of life on Earth. My coauthors and I cite him and quote him frequently in our refereed papers not only in Mathematical Biology, but also in Mathematical Economics. We have told him that we expect him to win a Nobel prize.
I also agree and have spent consderable time dealing with the point that
“If you want the model to be realistic the concept of level is fundamental.” This raises extreme problems in computational effort, as there are on the order of 20 orders of magnitude in both time and space of systems and subsystems modeled. I have a long paper on quantifying these challenges, and literature survey on how they are being tackled by various research institutions.
There were some other points raised in proaonuiq’s comment which I find interesting, but do not feel impelled to explore tangentially at this time. However, I am not convinced at all that there is a unique “non arbitrary four letters code and its semantics” because we only have in vivo data from one planet sofar. The value of Theoretical Computational Biogenesis and Evolution is to be:
(1) inclusive enough to fit data from Life as We Know it (as John Holland did in his original Genetic Algorithm book which I “beta tested” and coded in grad achool, as I was the first to use GA to evolve working software in semantic space which solved existing unsolved problems in scientific literature);
(2) exclusive to the extent as being not so abstract as to be “more game than life”;
(3) allowing discovery of life-like systems which are unquestionably “Life As We Do Not Know It” — i.e. in a very different part of phase space from terrestrial life.
(4) The above applies at every level
(5) one can study “artificial Physics” (i.e. toy Quantum Mechanics, life embedded in higher deimensions and nonEuclidean spaces and the like, such as my work with Conway Game of Life in hyperbolic planes;
(6) One can study “artificial chemistry” as I cited earlier;
(7) One can study “artificial biochemistry” with analogues of enzymes and membranes;
(8) one can study artificial cells with different organelles and architrtectures;
(9) One can study artificial tissues;
(10) one can study artificial organs;
(11) One can study artificial organisms (i.e. the global race to completely simulate a sing;e E coli cell);
(12) One can study artificial ecosystems.
The vast problems associated with doing combinations of the above suggest that it is very important to focus the Polymath project at something that needs considerably less resources than all the computers in the world for a century.
The must-read fiction is by Greg Egan. Check his own web site. He is monumentally adept at dealing with these issues in fiction, and also coauthors Mathematical Physics with John Baez, and also makes wonderful interactive color 2-D and 3-D graphics.