Comp. Sci. / Eng.

Avida’s EQU in 18 instructions

Spread the love

The evolutionary model, Avida, is best known for evolving the EQU function. In the supplementary materials for the 2003 Nature paper, the authors presented the shortest known program to compute EQU taking 19 instructions. They note that it hasn’t been proven that it was the shortest program. In fact it is not, and I present a program that computes EQU only using 18 instructions.

  1. IO
  2. IO
  3. nop-C
  4. push
  5. pop
  6. nop-A
  7. nand
  8. push
  9. nand
  10. swap
  11. nop-C
  12. swap
  13. nand
  14. nand
  15. pop
  16. nop-C
  17. nand
  18. IO

 

36 Replies to “Avida’s EQU in 18 instructions

  1. 1
    Roy says:

    Winston,
    AFAICT instructions 4/5/6 don’t do anything so can be dropped, leaving a 15-instruction algorithm. But AFAICT neither algorithm works. If the first input is “1” and the second input is “0”, the final output is “1” when it should be “0”. AFAICT the algorithms work for the other three possible input combinations, so maybe the test input contained only those.

    Roy

  2. 2
    Winston Ewert says:

    Roy,

    Instructions 4, 5, 6 have the result of copying register BX to register AX.

    4 pushes a copy of register BX onto the stock, the 5 pops it, but because 6 is nop-A it gets popped onto register AX.

    So the instructions are needed, and it does appear to me to work correctly for the case you mention.

  3. 3
    The Karaite Heretic says:

    Hello, I am a total ignoramus when it comes to informatics. Winston Ewert, I have read your article on ENV on this subject. I must say I still don’t understand what Avida has accomplished. Can you, or someone else here, dumb it down a bit for me? Thanks.

  4. 4
    johnnyb says:

    Karaite –

    The goal of Avida was to demonstrate experimentally that Irreducible Complexity is false. Therefore, the goal is to show that a complex algorithm can evolve by mutation and natural selection.

    The authors of Avida were able to evolve a function that they believe to be complex, the EQU function.

    Unfortunately, the Avida team didn’t really have a very good definition of “complex”. In addition, they inserted design into the environment by creating a step-by-step pathway to the EQU function. That is, the researchers knew each part that needed to be in EQU, so they made sure that every step on the way to EQU would remain selectable. This would seem to disqualify it from Irreducible Complexity to begin with.

  5. 5
    Roy says:

    Winston,
    you’re right, it does work – I was misinterpreting the swap instructions. Congratulations.

    I wonder if it can be made shorter still?

    Roy

  6. 6
    Roy says:

    I think this 17 instruction version will work. I’ve run it by hand, but haven’t tested it in Avida. It’s basically the same as Winston’s but uses the stack differently to reduce the number of nops (register references).

    1. IO
    2. IO
    3. nop-c
    4. push
    5. nand
    6. push
    7. nand
    8. swap
    9. pop
    10. nop-a
    11. pop
    12. nand
    13. nand
    14. swap
    15. nop-c
    16. nand
    17. IO

    Roy

    P.S. Avida programs would be so much easier to understand if the language designer had specified the nops as being before the instruction they affect.

  7. 7
    Eric Anderson says:

    The Karaite Heretic @3:

    johnnyb has answered well @4.

    Here is my short summary:

    Avida is a program that bears no relationship to biological reality, but that “demonstrates” that if a relatively easy, cumulative pathway to a function exists, then that final function can be found by trial and error through such cumulative pathway (with some encouragement in the form of reward pathways along the way). This, it is lost on many, has nothing to do with the situation irreducible complexity is addressing, so the alleged refutal of irreducible complexity fails.

    Furthermore, and perhaps more interesting, when the 2003 authors used a more realistic set of parameters the EQU function failed to evolve, thereby inadvertently confirming Behe’s point. This was, rather quietly, slipped in as a side note late in the paper where (the authors no doubt hoped) few would take notice.

  8. 8
    johnnyb says:

    A little self-promotion —

    Here is a paper I wrote a while back on applying theoretical computer science to the question of irreducible complexity.

    Irreducible Complexity and Relative Irreducible Complexity: Foundations and Applications

  9. 9
    Thomas2 says:

    I should appreciate some assistance in understanding Avida:

    On my first reading of the Nature 2003 paper, Avida purports to specifically demonstrate the evolution (developmental increase) of functional complexity in the first place (and irreducible complexity as a spin-off from that).

    Also on my first reading of that paper, Avida appears to positively correlate fitness with functional complexity, and also rewards fitness in proportion to total (!) complexity. If this reading should be correct then Avida would be a question-begging ratchet model in which increase in complexity is almost inevitable (where any potential pathway exists) – am I reading the paper correctly in understanding the Avida algorythm to positively correlate fitness with functional complexity and reward it in this way?

  10. 10
    The Karaite Heretic says:

    Thanks once again, Johnnyb and Eric Anderson. Means a lot to me. May YHWH be with you.

  11. 11
    Mung says:

    In the summer of 1993, Charles Ofria and C. Titus Brown joined Adami to develop a new digital life software platform, the Avida system.

    This was before DBB was published and before IC was even a blip on the screens of Darwinists.

    johnnyb:

    The goal of Avida was to demonstrate experimentally that Irreducible Complexity is false.

    anachronism:

    1. The representation of someone as existing or something as happening in other than chronological, proper, or historical order.

    We do ourselves a disservice by making things up. What’s the evidence for the claim you make johnnyb?

    I don’t think that Winston makes that claim in his paper either and iirc may even have disavowed such right here at UD (in his response to r hoppe?).

    Right now I am in lazy mode, tough day at work, but if I have to I will look it up. hey, maybe i will even be wrong!

  12. 12
  13. 13
    rhampton7 says:

    Mung,

    The concept of IC was outlined before Darwin’s theory:

    The most famous design argument is of course that propounded by William Paley, who argued thus: even if we had never seen a watch before, an inspection would lead us to conclude that it was designed and made for a purpose. Observe the world and we see once again an intricate interplay of parts and contingent, complex physical laws arranged together and achieving a collective end (intelligent life forms). The world is analogous to the watch. The watch had a designer, so it is reasonable to think that the world had a designer. Modern knowledge has only increased the strength of this analogy:

    ‘Cells swim using machines, copy themselves with machinery, ingest food with machinery . . . highly sophisticated molecular machines control every cellular process.’

    Popular summaries of Paley notwithstanding, his argument goes well beyond mere analogy. Although he didn’t employ this precise terminology, Paley pointed out that a watch is irreducibly complex. Not only is the purpose carried out by the sum of the watch’s parts, but that purpose could not be carried out: ‘if its different parts had been differently shaped from what they are, or placed after any other manner or in any other order than that in which they are placed. . .’ Irreducibly complex systems, like a watch, are composed of a number of mutually interdependent parts, each of which is functionally useless on its own. This means that such a system cannot evolve by natural selection, because until the whole system is functional there is nothing of advantage in existence to be selected. (Indeed, manufacturing individual components of irreducibly complex systems would be a drain on resources, therefore constituting an evolutionary disadvantage.)

    Intelligent Design, Aesthetics and Design Arguments, Peter S. Williams

  14. 14
    johnnyb says:

    Mung –

    There was a talk, that I think has been taken offline (or perhaps there were only oral reports to begin with), where Pennock explicitly mentions Behe’s Irreducible Complexity as an animating motivation behind Avida. If they say they also worked on it before hand, I don’t doubt that either. But much of the development of it for their Nature paper was motivated by Behe, and I know this because they said so.

  15. 15
    johnnyb says:

    Mung –

    I cannot find the particular talk I am thinking of, but here are some similar statements by Adami:

    Reducible Complexity

    The Bridgham et al and Lenski et al studies are of particular scientific interest, given the political attention given to intelligent design lately. Although these authors have not directly addressed this controversy in the discussion of their work – because the work itself is intrinsically interesting to biologists – such studies solidly refute all parts of the intelligent design argument. Those ‘alternate’ ideas, unlike the hypotheses investigated in these papers, remain thoroughly untested. Consequently, whatever debate remains must be characterized as purely political.

    In other words, ID was the motivating factor, we found the ID ideas interest and wanted to test them, but we can’t say so for political purposes, and refer all criticisms of our work back to politics.

    Then there is a Zimmer article:

    “What we show is that there are irreducibly complex things and they can evolve,” says Adami.

    And PLoS biology:

    The research confronts evolutionary theory’s long-standing challenge to explain how an organism can develop complex features simply as a result of random mutation and natural selection. The challenge remains a controversial one, too. Supporters of intelligent design, a branch of the creationist movement, promote the notion of ‘irreducible complexity’ as evidence that Darwinian evolution is a flawed theory. The notion purports that a complex feature cannot evolve sequentially from its elements, and must have been designed in one step by some higher intelligence.

    Traditional investigations, based on molecular biology and palaeontology, have yielded much evidence about the incremental evolution of the eye or the brain, for instance. But continuing ignorance about many developmental processes and the absence of key fossil records mean that accounts without missing links, to endorse the theory, may never be realised.

    Which is what tempted Lenski and Adami to examine the challenge in their virtual world.

    So, as rhampton7 pointed out, even if it wasn’t Behe personally that they were targeting, it certainly was something at least very similar to Irreducible Complexity, even if they refused to give it that name.

  16. 16
    johnnyb says:

    Ah, yes, here it is. It is not Pennock, but Adami’s talk from 2005 AAAS that I was thinking of.

    First of all, the nature paper itself says,

    A long-standing challenge to evolutionary theory has been whether it can explain the origin of complex organismal features. We examined this issue using digital organisms — computer programs that self-replicate, mutate, compete, and evolve.

    What else do you need?

    Anyway, from Paul Nelson’s Review of Adami’s Talk:

    While the Nature paper doesn’t specify the relevant actors, Adami did in his AAAS talk: Mike Behe, at least. Several slides showed, and Adami carefully explained, that the Avida simulations were intended to test Behe’s arguments about the origin of irreducibly complex structures.

    Another overview of Adami’s talk:

    A quick summary of the problem and its recent solution goes like this: Intelligent Designists say that certain biological features are far too complex to have been evolved using Darwin’s algorithm. They (especially Lehigh University biochemistry professor Michael Behe) have claimed that since very complex structures (say, for example, the eye) rely on the simultaneous activation of many (tens, hundreds, thousands) of genes, they could not possibly evolve by successive single mutations. This is known as “irreducible complexity”, because the complex nature of the structure is not thought to be reducible into a series of single mutations. Adami and Avida have shown otherwise.

    Apparently the lecture used to be available for free online, but it has been taken down. The original URL was http://www.aaas.org/spp/dser/s.....202005.mp3 as you can see here.

  17. 17
    johnnyb says:

    Also forgot to mention Casey Luskin’s reporting on this and similar items.

  18. 18
    Thomas2 says:

    Winston Ewert, Eric A, &/or Johnnyb –

    On my reading of the second page of the Nature 2003 paper, Avida appears to positively correlate fitness with functional complexity, and then also rewards fitness in proportion to total (!) complexity.

    Am I reading the paper correctly in understanding the Avida algorythm to positively correlate fitness with functional complexity and reward it in this way?

    thx.

  19. 19
    Eric Anderson says:

    Mung @11:

    This was before DBB was published and before IC was even a blip on the screens of Darwinists.

    Yes, I noticed johnnyb’s statement as well, but let it slide because the topic of the OP was the 2003 paper that got all the notoriety.

    It is quite clear, both from the 2003 paper itself, as well as other comments from the team and the Darwinian circling-of-the-wagons attitude subsequently, that the 2003 paper was aimed squarely at Mike Behe and irreducible complexity.

    johnnyb said:

    The goal of Avida was to demonstrate experimentally that Irreducible Complexity is false.

    To be scrupulously accurate and avoid any misunderstanding, he perhaps should have said:

    The goal of the 2003 Nature paper that brought notoriety to Avida was to demonstrate experimentally that Irreducible Complexity is false.

  20. 20
    Eric Anderson says:

    Thomas2 @18:

    Yes, essentially that is correct. Avida (again, we’re talking the 2003 instantiation for the Nature paper) essentially flogged the “organisms” up the back of Mount Improbable.

    Supporters will point out that not every single step needed to produce a fitness advantage. They will mention that some pathways to EQU even took a step backwards, losing fitness temporarily in order to get around a block, before continuing. They will harp on the fact that different pathways and “genotypes” were able to arrive at EQU.

    All of that may be true enough. But the fact remains that the process was generally one of more fitness as they proceeded along the pathway.*

    Furthermore (and in addition to the fact that the program bears no relation to biotic reality), the fact that there even was a pathway makes the whole project an exercise in irrelevance. No-one doubts that if (i) you have a large enough population, (ii) the complex function can be built up in a series of smaller steps, (iii) there is a relatively flat functional landscape in which new steps are easily reached, (iv) intermediate steps are functional, and (v) rewards are doled out along the way as the organism approaches the “goal”, then it is possible to cumulatively build a complex function by the trial-and-error process of Darwinian evolution. No-one has ever doubted that and it hasn’t been at issue; Behe certainly never claimed it couldn’t be done.

    But the questions remain. In the real world, is it the case that complex functions can be built up piece by piece? Is the functional landscape relatively flat? Are intermediates functional, and do they provide a meaningful fitness advantage? Are there fitness rewards that would move the organisms up the path of increasing complexity and functionality?

    Avida, unfortunately, does not answer any of these questions because it assumes them.**

    —–

    * The “goal” was built into the program. Not inevitably, meaning that not every single run would produce the EQU result. Some supporters make much hay of this fact, claiming that because the result was not inevitable in any particular case that, therefore, Avida didn’t build in the final result. But that is simply a failure to understand how programs work and that goals can be built into a program inevitably or stochastically. With Avida, it was built in stochastically, meaning that (given the assumptions built into the program) there would be a distribution, with a subset of the organisms reaching the goal.

    ** Note the authors’ simplistic dismissal of this fatal issue in the two sentences in the middle of the second full paragraph on page 4, starting with “Some readers might . . .”

  21. 21
    Thomas2 says:

    Eric A @20 –

    Thank you for your detailed and helpful answer to my query. On that basis –

    1. It seems to me then that because Avida positively correlates fitness with functional complexity (rewarding complexity accordingly), as a probalistic model it will almost inevitably build a functionally complex target (even if the target is not prescriptively specified), and therefore it thoroughly begs the whole question of the evolution of “organised complexity”.

    2. This would be in addition to begging the question of “irreducible complexity” by building-in potential pathways – since it also provides (it appears) a relatively obstruction-free (and apparently ravine-free?) “fitness landscape”, as identified by Winston Ewert (and others).

    However, do I infer from your comment that the first point above, though present in the 2003 Nature paper version of Avida, is not present in all versions of Avida (whereas the second point is)?

  22. 22
    Mung says:

    Eric, yes. It’s important, I think, to distinguish between Avida and the propaganda about Avida.

    If someone published a paper claiming Avida was designed to refute Irreducible Complexity but that it fails to do so because it makes assumptions not permitted under Irreducible Complexity I wonder what the response would be.

  23. 23
    Mung says:

    The problem with partial rewards is identifying the partial solutions to reward. Avida has nicely demonstrated that it can be done if you already know what the partial solution looks like. A naturalistic evolutionary process does not have that luxury.

    – Winston Ewert

  24. 24
    Mung says:

    This should bring back memories, right johnnyb?

    The Avida software program has been used as a refutation of the notion of irreducible complexity (Pennock 2005). Therefore, it is useful to analyze both the results of Avida simulations and the Avida code itself according to this framework. Avida works by evolving digital “organisms,” where the Avida organisms are programs that perform logic functions and replicate themselves. Avida has been used to show that evolution can evolve new functions as exaptations from previously-existing functions (Lenski et al.2003).

    IRREDUCIBLE COMPLEXITY AND RELATIVE IRREDUCIBLE COMPLEXITY: FOUNDATIONS AND APPLICATIONS

    Therefore, if we were to analyze Avida based on the creation systematics outlined above (modified slightly since we are dealing with IC instead of RIC), we would find that the replication loop was Irreducibly Complex, and therefore part of the original creation. The code for the logic functions, since they do not have open-ended loops contributing to the result, can be explained in terms of historical contingency. As supportive of this framework of irreducible complexity, this is precisely the case for Avida-the logic functions develop as a historically contingent process while the replication loop was implanted by Avida itself in the initial population of organisms.

  25. 25
    Winston Ewert says:

    Roy,

    Congratulations on your shorter program! I’ve run it through Avida and confirmed that it works. Also, agreed on the obnoxiousness of the instruction set design there. I think it was inspired by Tierra on that point.

  26. 26
    Mung says:

    Winston, if you would be so kind, save me some research, I beg!

    The goal of Avida was to demonstrate experimentally that Irreducible Complexity is false.

    Do you agree, disagree, or abstain?

  27. 27
    Winston Ewert says:

    It is quite clear, both from the 2003 paper itself, as well as other comments from the team and the Darwinian circling-of-the-wagons attitude subsequently, that the 2003 paper was aimed squarely at Mike Behe and irreducible complexity.

    The paper doesn’t mention Behe or IC, and Pennock explicitly disclaimed the idea that the paper presented an argument against irreducible complexity. It’s certainly possible that they are attempting to attack IC without mentioning it, but its not clear why they would want to do that since they were quite open about attacking IC using the research afterwards.

  28. 28
    Winston Ewert says:

    Mung,

    Do you agree, disagree, or abstain?

    Disagree leaning towards abstain.

    I can’t determine the motives of Avida’s authors, nor is their motive relevant to the implications of the model. But based on the explicit testimony of the authors, the attempt to counter irreducible complexity did not arise until after the 2003 paper.

  29. 29
    johnnyb says:

    Mung –

    Thanks for highlighting my favorite parts of my paper!

    I found it highly interesting that Avida did, in fact, have an IC system within their organisms, and it was one that was designed!

  30. 30
    Eric Anderson says:

    Winston:

    Good thoughts and good cautions, thank you.

    It does seem a little suspect though, after the height of the irreducible complexity issue had been brought to the forefront by Behe (and received a tremendous amount of attention, both in the evolutionary community and more broadly), that the authors would write a paper dealing with the irreducible complexity issue (origin of complex features by RM+NS which require multiple parts to work together simultaneously for function) and not realize they were talking about irreducible complexity? And then they realized later on (as acknowledged by Adami at least) that their work in fact challenges irreducible complexity, and Behe in particular?

    Let’s also keep in mind that at that time, and for some time later (perhaps softening a bit in recent years), there was a “pirate’s code” kind of attitude of not giving any ID proponent any visibility — even going so far as to refuse to debate in order to not give ID proponents the dignity of a forum. (In an interesting parallel situation, this attitude and specific approach by the “consensus” science crowd was rampant in the climate change debate for years.)

    The Avida authors clearly knew about Behe’s argument (unless they had been living under a rock). They clearly understood that their paper was relevant to the issue. They specifically stated that their paper was challenging the issue Behe had raised (even if they didn’t want to use Behe’s terminology — nod, nod, wink, wink). And after the fact they did little to counteract the widespread acclaim they received and proclamations by the Darwinist community that they had “refuted” Behe and stricken a blow against intelligent design.

    It is certainly possible for an author to say, very possibly even truthfully, that at the time they were not primarily out to refute Behe, just out to prove that Darwinian evolution was capable of producing complex organismal features through a step-by-step process of RM+ NS.

    You know, refuting Behe’s argument. 🙂

    At the end of the day, tither their Avida paper addresses the irreducible complexity issue or it doesn’t. If it doesn’t, then great, let’s hear an acknowledgement from the authors that it doesn’t refute Behe’s irreducible complexity. But they claim it does, and they have said as much after the fact.

    All that said, you are right, of course, that we can’t assume motives, so we should soften the statements. I’ll try to be more cautious in the future.

    So rather than saying the researchers “set out to refute Behe” (original motive), we could say that the researches “have pointed to Avida as a refutation of Behe” (what in fact has happened).

  31. 31
    OldArmy94 says:

    This is a bit off-subject and science “fictiony”, but I have wondered why we do not see true computer organisms that are evolving, multiplying and adapting. After all, haven’t we set-up a virtual environment for them to exist and thrive? Some OOL researchers claim that there isn’t really a difference between life and non-life. Therefore, given that there is “universe” for this life to form and evolve, why is it that we see nothing but guided models like Avida? If we cannot see a digital world of organisms emerging, then why should we expect our real world of living creatures to be here as a result of unguided processes? I am not sure I am making any sense, but I think I know what I am trying to say. 🙂

  32. 32
    Eric Anderson says:

    OldArmy94:

    Actually, it is a perfectly reasonable question. The proof of how much evolutionary algorithms can do, as they say, is in the pudding. And the answer is: Not much.

    Why don’t we have armies of evolutionary algorithms writing new code or creating new products or writing great works of literature? Where are all the wonderful results of this “evolutionary” process? Perfectly reasonable questions.

    The most anyone can point to is a few examples of algorithms that have been used for very discreet and focused purposes (the antenna one being probably the most famous, though certainly not the only example).

    And, indeed, a trial-and-error process can be facilitated through a fast machine to come up with some useful results . . . if, that is, the parameters are narrowly specified and an overall goal or direction is included. In that case, yes, iterative trial-and-error algorithms can be a useful tool to quickly sample numerous options in that well-defined space and help guide a designer toward an optimal solution.

    But take away the carefully-crafted parameters, remove the specifications, eliminate the built-in goal, and the search space quickly overwhelms anything that even our fastest computers can deal with. The truly Darwinian system — one without purpose, goal, or direction — flails about endlessly, to paraphrase Berlinski, “not knowing where it is going, unsure of where it has been.”

  33. 33
    Mung says:

    johnnyb,

    So you can evolve IC using Avida, or not?

    The code for the logic functions, since they do not have open-ended loops contributing to the result, can be explained in terms of historical contingency. As supportive of this framework of irreducible complexity, this is precisely the case for Avida-the logic functions develop as a historically contingent process

    I see two possible responses.

    Avida cannot evolve any IC logic function.

    Avida can evolve an IC logic function, but only because of a pre-existing IC function.

  34. 34
    johnnyb says:

    I didn’t delve too deep into this in the paper since Avida wasn’t actually a primary target (if I remember correctly, I actually stumbled onto the result when the paper was near completion). But, in short, here are the answers to your questions.

    1) None of the functions Avida tests for are IC because none of them require open-ended loops to solve.
    2) There is an IC function in Avida, and that is the replication loop. However, it is pre-existing.
    Additionally, (3) None of the organisms which Avida evolves even uses open-ended loops to assist in solving the functions. Occasionally, a loop arises which is irrelevant to solving the function, but not where the loop itself contributes.

    Now, just like they did with EQU (which I don’t consider to be irreducibly complex), it might be possible that the selection environment is fine-tuned enough to be exactly right to evolve something that requires an open-ended loop. But I think that would require something a lot more ridiculous-looking and obviously tinged with investigator bias.

  35. 35
    johnnyb says:

    What would be interesting, and I would like to do this but don’t have the time, is to expand the available tests within avida to test for functions such as factorial. If someone could evolve the factorial function via a modified Avida, without making ridiculous path-tuning of the environment, I will be duly impressed.

  36. 36
    Roy says:

    Now that we have both multiple designed EQU programs and multiple evolved EQU programs, is there an opportunity to use intelligent design theory to differentiate them?

Leave a Reply