Jonathan Bartlett’s “open-ended loop” argument

In the “Evolving complex features” thread, TristanM asks:

I’m curious what the group’s thoughts are on Jonathan Bartlett’s (AKA “JohnnyB”) argument about open-loops in the AVIDA program?

I haven’t studied Jon’s argument yet, but I think some of you have. What did you think?

Why I Love AVIDA – Detecting Design in Digital Organisms

Thoughts on Parameterized vs. Open-Ended Evolution and the Production of Variability

Irreducible Complexity and Relative Irreducible Complexity: Foundations and Applications

141 thoughts on “Jonathan Bartlett’s “open-ended loop” argument

  1. Patrick: There are still four random strings I provided to you waiting to be assessed, if I remember correctly….

    A little progress report, I just finished coding the standard tool. It’s inelegant as all get out but it was fun to get my feet wet in programing. Now I need to imbed the program in a web page and share it with the world.

    As soon as that is done I’ll get to work on a modified tool to perhaps work with your binary strings

    peace

  2. Neil Rickert: I hadn’t noticed that it was the short version.

    Try this link

    A bit longer, but same lack of biological relevance as far as I can see. A couple of different biology references, though — different popularizations.

  3. I do hope that johnnyb will, when he returns, deign to identify at least one extant instance of a biological structure which qualifies as one of those “open-ended loops” he’s gone on about, and I further hope that, should he deign to identify an extant example of a biological “open-ended loop”, he will also explain how he came to identify that biological structure as an “open-ended loop”.

  4. “Redcode includes three instructions that could be used to implement iteration, JMZ (jump if zero), JMN (jump if not zero), and DJN (decrement and jump if not zero). Would you consider those too “designed” for evolution of a loop to be difficult?”

    I presume these operate on a specific register/accumulator. I would prefer the register/accumulator to be selectable, rather than fixed. DJN is definitely too “designed’ for the task, but if JMN operates on a selectable register, then I think it works fine. Even if it operated on an accumulator, I would be interested in seeing loops built out of it. Of course, this presumes that the rest of it is also open to Turing-ish things (like being able to operate on larger spans of memory rather than only on a small, fixed set of registers). The other thing is to make sure there isn’t some sort of supervisory function that keeps it from running away (it’s okay for a supervisor to kill it and deem it non-selectable, but not to finish the computation on its own).

    “Another possibility is genetic programming (GP). Unlike genetic algorithms, GPs operate on the abstract syntax tree directly. Much of the GP work is done in Lisp variants for that reason.”

    My search included AST GP stuff. Lisp itself includes too many helper constructs to be usable, but being Lisp-like is not a problem. I should note that a friend of mine thought he found one in Genetic Programming: On the Programming of Computers by Means of Natural Selection in chapter 18. (bok available here – http://www.ru.lv/~peter/zinatne/ebooks/MIT%20-%20Genetic%20Programming.pdf ) However, on further inspection, it appears that DU (do-until) actually auto-terminates after a fixed number of steps, even if the conditional expression never returns true. It has other problems (it has a ridiculously small set of functions/terminals geared for the specific problem, and I don’t think it is Turing-complete either).

    So, if you find something, let me know! I’d love to hear about it. If you post them here, please also email me at jonathan@bartlettpublishing.com.

  5. BruceS: A bit longer, but same lack of biological relevance as far as I can see.

    Agreed. That was pretty much my point when I said that he looks at it as a logic problem rather than a real world interaction problem.

  6. cubist – I did, earlier, but you may have missed it. Read section 3.1 of the paper referenced for an example and explanation. The super-short version is that it is the FleQ/FleN pathway in the development of the flagellum. It is an open-ended loop because it is a negative feedback loop – a downstream product of FleQ (which is FleN) is what turns FleQ off.

  7. johnnyb,

    Redcode includes three instructions that could be used to implement iteration, JMZ (jump if zero), JMN (jump if not zero), and DJN (decrement and jump if not zero). Would you consider those too “designed” for evolution of a loop to be difficult?

    I presume these operate on a specific register/accumulator. I would prefer the register/accumulator to be selectable, rather than fixed. DJN is definitely too “designed’ for the task, but if JMN operates on a selectable register, then I think it works fine.

    There are no registers in Redcode, these instructions operate on the current location in shared memory. It’s a very flat model, with no stack pointers or anything similar. You can see more details here.

    Out of curiosity, why do you consider DJN too “designed” compared to the other two jump instructions?

  8. “why do you consider DJN too “designed” compared to the other two jump instructions?”

    It permanently wraps together two different aspects of looping – the control (decrecment) and the condition (is zero). It’s really about halfway between open-ended and close-ended, but for a good test case I would prefer the other one. Also note that in the review paper I mentioned earlier, that even with close-ended loops, they were unable to find any algorithms developed that were more than one nested within another.

  9. I haven’t looked at CoreWars very much, but at a glance it doesn’t seem to be a very good platform, primarily because it seems to be about destruction, not construction. That is, it isn’t about *doing* something, but about *destroying* something. Part of my point is that the space for destruction is greater than the space for construction.

    I didn’t find a quick link to rules and instruction set, so I can’t say much definitively, but that was my first gut reaction.

  10. Patrick –

    “If your position is that an “open-ended loop”, which I take to mean an iteration control construct without a fixed number of steps”

    I just wanted to clarify that the point is more that the termination is not implicit. For example, in ruby, an each() loop is implicitly terminated by the length of the array. It is not possible to have an each() not terminate (unless there is non-termination in the steps within the each()). So, even though this is a fixed number of steps, it is open-ended:

    i = 0;
    while(i < 5) {
    /* Do something */
    i++;
    }

    The while construct does not implicitly link the condition to the control. That's why I don't like DJN (though I don't know the specifics). If it was given a memory location or a register, if it is an integer, that means you are nearly-guaranteeing termination with that instruction.

    Of course, someone will say, "well, what if life's programming doesn't have these?" The answer to this is simply, for creating truly novel solutions, these types of constructs are required. In addition, we know that these types of constructs do exist in life, so they must be accounted for.

  11. As a quick postlude, I want to say that although I think this method is good and useful for design detection, I don’t think that such complicated measures need to be employed to detect design. I think that, in general, you can tell that life is designed because life is built around *organization* at every level. Organization indicates a rational cause.

    However, I think it is important to, within the details, determine which specific aspects of life are designed and which are evolved or evolvable. As I pointed out earlier, I think if this system were regularly employed, it would eventually lead to finding new discoveries in biology because, if someone found something that shouldn’t be evolving that actually was evolving, then it would be de facto evidence that there is a programmed evolutionary mechanism guiding either the mutations or canalizing the phenotype. Thus, rather than just saying, “hey ho! Look at what magic evolution has done!” a researcher would know when they need to look further and find a more specific cause for the mutation/series of mutations.

    Also, I don’t know the details, but I think that knowing which features are evolvable and which are not might help at least partially in determining the taxonomic importance of different features.

    Anyway, all that to say that I don’t think that my method is even needed for determining *whether* life is designed. I think that the evidence for that is clear and speaks clearly just from the multi-level organization of the organisms themselves (not to mention self-replication and consciousness). However, whether you agree with that statement or not, it is still important to determine within the organism which features are evolvable and which are not. That is where I think my method shines well. Of course, if you didn’t think that life looked designed, perhaps it might convince you, but that is just a nice side-bonus 🙂

  12. Ruby is a dynamic and object-oriented programming language, so the behavior of the each method is context dependent at the individual object level. What’s more, Ruby has what are called open classes, which means I can alter the implementation of the each method for the entire Array class (as an example).

    Ruby is the ultimate in open-ended-loop languages!

  13. As a wrap-up, I just wanted to say thank you to everyone for the great interactions! I appreciate all of the comments and criticisms, and especially the time everyone took to examine my idea carefully! It is often difficult to find people both able and willing to engage in such ideas.

    Also, as an only-moderately-related plug for anyone still listening, here’s some of the stuff I’m selling or have been working on:

    1) Engineering and the Ultimate – a compendium of papers from a quasi-ID-related conference held a few years ago.

    2) Programming from the Ground Up – an old book I wrote on assembly language under Linux. It’s over a decade old, but I think it still largely holds up.

    3) I’m working on a JavaScript book for new programmers in my spare time. If anyone wants to read it and offer criticisms or suggestions, email me at jonathan@bartlettpublishing.com and I’ll send you a PDF of the current version.

    4) I’m getting ready to start a fundraiser for getting quality microscopes into independent classrooms (homeschool co-ops, charter schools, etc.) and possibly independent researchers. I haven’t actually officially announced the fundraiser, but if you want to donate, you can do at gofundme.com/microscopes. The official launch of the fundraiser will be later this week or next.

  14. johnnyb,

    if someone found something that shouldn’t be evolving that actually was evolving, then it would be de facto evidence that there is a programmed evolutionary mechanism guiding either the mutations or canalizing the phenotype. Thus, rather than just saying, “hey ho! Look at what magic evolution has done!” a researcher would know when they need to look further and find a more specific cause for the mutation/series of mutations.

    And say instead “hey ho! Look at what some magic ‘designer and/or programmed evolutionary mechanism’ has done!”

    One thing lacking in this kind of analysis is a proper understanding of how mutations, whether designed or not, get into every member of a species. ‘Intelligent guiding’ requires that this happen against the trend of environmental selective advantage – otherwise why not just use selective advantage? That is, intelligently guided organisms must be less fit, less adapted, than their predecessors.

  15. johnnyb,

    cubist – I did, earlier, but you may have missed it. Read section 3.1 of the paper referenced for an example and explanation. The super-short version is that it is the FleQ/FleN pathway in the development of the flagellum. It is an open-ended loop because it is a negative feedback loop – a downstream product of FleQ (which is FleN) is what turns FleQ off.

    The flagellum has become such an ID icon, it’s even the touchstone for feedback! But downstream products interacting with precursor enzymes or their transcription/translation is the absolute essence of biological control, and happens everywhere. I may have missed context; do you think such systems are inherently non-evolvable? I’ve never encountered a molecular biologist who a) was unaware of such mechanisms b) thought they posed the remotest problem for evolution.

  16. johnnyb: As a wrap-up, I just wanted to say thank you to everyone for the great interactions! I appreciate all of the comments and criticisms, and especially the time everyone took to examine my idea carefully! It is often difficult to find people both able and willing to engage in such ideas.

    Hi Jon.

    Hello and good-bye, it seems! Sorry your arrival and departure coincided with my being unable to find time to get to a keyboard. (Not that I’d have much to add, as computer programming is another of the many skills I lack.) I would echo others’ skepticism about using a computer model to suggest deficiencies in the theory of evolution before making sure that the model actually makes a good model for evolution.

  17. I’m not sure whether it’s worth responding to this, as you have left, but on the off chance that you drop by again, here are my responses for what they are worth:

    johnnyb:
    Elizabeth –

    I don’t really want to get into an argument over Behe’s definitions – it seems kind of pointless since that’s not the topic, but I’ll give a post to it.It was probably not as well developed in my paper as I had thought.Basically, I think that open-ended loops *are* the proper computational mapping to Behe’s idea.If I remember correctly, Behe, in the larger development of his idea, tried to convey the fact that they were core processes, and not just basic external catabolic systems.I think the reason for this is because the more core processes are more likely to be subject to recursive control.Behe, not being a computer scientist, did not know how to express that, but I think that this is the meat of what he was trying to get at.Therefore, since it is non-recursive (aka not an open-ended loop), it is not IC.

    Well, Behe was very much the topic of both my OP about AVIDA, in which Tristan posted your comment, and also of your own paper, and indeed of the AVIDA paper we were discussing. And by both Behe’s specified definitions of IC, IC turned out not to be a bar to evolution. I think it is a mistake to think that just because AVIDA is instantiated on a computer, and the functions the organisms evolve are logic functions, not things like running or looking or hiding, that it is sensible to push the analogy any further. Biological things have some things in common with computer programs, but a lot of things are different, not least being that the systems are not nearly so brittle.

    As to Avida having dead organisms reproduce, I think (it has been a while since I dug into it) that if you don’t properly perform tasks, it just slows you down, it doesn’t necessarily kill you.So, if no one ever performed a task correctly, they would still function and reproduce, but at a reduced rate.I think they do die if they exceed a population threshold, but I don’t think that they do from lack of performing function.They just reproduce more slowly.

    I don’t see that that is relevant. Reproductive speed is not everything. What matters is the number of viable progeny you leave

    “Two dimensions, yet neither the increased reflexes nor the better camouflage have to happen “simultaneously”.”

    I don’t disagree that there are also dimensions that work out in evolutionary favor, only that they are compounded by the number of dimensions that *do* have to happen and work simultaneously.

    No, they don’t have to “happen” simultaneously. Some functions rely on two components being present (or more than two). But the don’t have to occur simultaneously. That, again, is what AVIDA shows, and is something Darwin missed – that sequences can propagate even if they are neutral or even deleterious, through drift, thus generating many instantiations in each of which the second sequence can occur, thus hugely increasing the probability that both will occur in the same individual. And in a sexually reproducing population, or one in which there is some kind of HGT mechanism, that effect is amplified still further.

    “Most loss-of-function mutations are non-lethal, even where the function is normally beneficial.”

    I agree, but they certainly aren’t selected for.Also, if natural selection requires you go down too many non-selectable highways, can evolution really be said to be operating “by natural selection”?If natural selection is too weak, it doesn’t do anything at all, as John Sanford has pointed out.This is a problem for evolution, which needs NS to build organisms, not design.

    But “NS” and “design” are not the only two alternatives. There is also drift – and AVIDA shows just how important drift can be. It doesn’t supplant NS – if you have no selection in AVIDA, the most complex function doesn’t evolve. But each function evolves by way of deeply IC pathways – and the reason that happens, with high probability, is because of drift.

    So, knowing what we know, and Darwin didn’t (genetics; population genetics) we can express “NS” as a bias on drift. That sometimes-biased-drift turns out to be well-able to produce IC functions by IC pathways.

    “Not sure what this means either. Can you give an example? You seem to be assuming a very brittle system, in which any loss-of-function is lethal. Why should we assume this?”

    Here I’m not talking about loss of function.In the paper, the biochemical equivalent to open-ended loops is a negative feedback system, where a downstream product is required to suppress the generation of a protein.If the system is not completed yet, or the feedback is damaged, the open-ended loop is left wide open, draining organism resources.This is the same problem in both computer science and in organisms.I have run across several references to diseases where things are not turned off properly, and most of them are pretty bad, but I don’t have the references at the moment.This is why open-ended loops make selection for them so difficult – if the full system isn’t in place, it can easily spin out of control, not just basic loss-of-function.

    Yes, computer systems tend to be brittle. Biological systems do not. That seems to be at least partly because biological systems that were brittle did not result in robust individuals or populations. The great thing about catastrophic mutations is that they don’t leave progeny.

    There is, in other words, a lot of “selective pressure” (not a phrase I like) for homeostatic systems in biology. In fact, you could argue that homeostasis is almost a condition of self-replication.

    “clearly Darwin’s mechanism only kicks in once you have self-replication.”

    Right.My point is that self-replication is just one of the things that are needed.In order to successfully evolve across multiple dimensions (take your fish example) you need lots of existing code in multiple dimensions (pigment and motor genes, for instance).Therefore, even if multiple dimensions eases your problems, to enable multiple dimensions requires a *lot* of existing information, much more than just self-replication.

    Not necessarily. I would ask you to support this – but I am aware you do not intend to return to this conversation.

    “But why need you wait long for multiple dimensions? In the early stages of a proto-biont there are likely to be easily as many ways of improving reproductive chances as there are later, surely?”

    I think that’s wishful thinking.In orde to improve something, you need a parameterized system.It takes a lot of information to build systems sufficiently parameterized to evolve along different dimensions. And, at the start, the number of dimensions you are successful on is greatly outweighed by the number of dimensions you could die on.

    That doesn’t matter. Nor, to be honest, does it make a lot of sense. Perhaps you and I don’t mean the same by “dimensions”. And again, I’d ask you to support your claim about parameters, if you were going to stick around.

    I do understand the pressure of RL – but it is sort of frustrating to have someone drop into a conversation, then drop out leaving questions hanging! It’s the nature of internet conversations that they are a bit time-lagged.

    I do hope you will consider dropping by when you next have an opportunity. I’m sure we can wait. If you do, and this thread has already dropped off the front page, I will sticky it.

  18. johnnyb: The super-short version is that it is the FleQ/FleN pathway in the development of the flagellum. It is an open-ended loop because it is a negative feedback loop – a downstream product of FleQ (which is FleN) is what turns FleQ off.

    Wait. A negative feedback loop is one in which the feedback tends to reduce the loop’s activity. And you’re saying that qualifies as an “open-ended” loop? Sorry, johnnyb, but that doesn’t pass the laugh test. I’m not sure whether you just haven’t allowed yourself to recognize the incompatibility of your terms, or you’re using a non-standard denotation of at least one of said terms, or what, but I gotta say this doesn’t exactly entice me to want to read that paper you referenced…

  19. johnnyb,

    I haven’t looked at CoreWars very much, but at a glance it doesn’t seem to be a very good platform, primarily because it seems to be about destruction, not construction. That is, it isn’t about *doing* something, but about *destroying* something.

    I’m not sure what that has to do with your claim about iterative control constructs being unevolvable.

    In any case, Core Wars is about developing a program that is the best competitor for limited resources. Does that sound like anything else we discuss around here?

  20. johnnyb,

    I just wanted to clarify that the point is more that the termination is not implicit. For example, in ruby, an each() loop is implicitly terminated by the length of the array. It is not possible to have an each() not terminate (unless there is non-termination in the steps within the each()). So, even though this is a fixed number of steps, it is open-ended:

    i = 0;
    while(i < 5) { /* Do something */ i++; } The while construct does not implicitly link the condition to the control. That's why I don't like DJN (though I don't know the specifics). If it was given a memory location or a register, if it is an integer, that means you are nearly-guaranteeing termination with that instruction.

    That adds considerable clarity, thanks.

    “Iteration without explicit termination” might be an objective enough criteria to work with (although identifying it in evolved digital organisms can be non-trivial).

  21. Is the assertion that, if open-ended loops cannot be brought about by natural evolutionary processes, that this is a problem for evolutionary explanations? Is it possible that living forms are not doing Turing Complete computation. Who says that they are?

    As far as I can see the assertion is that the presence of open-ended loops in Avida, and their presumed absence in nature, means that Avida isn’t a very good model of what happens in natural evolutionary systems. Fine with me. I am not one of those who think Avida is a sufficiently good model of nature.

    But actually there are plenty of mechanisms in nature that look like open-ended loops to me. Squirrel: find nut, take it and bury it, Repeat until too tired, or until some other need creates pressure to do something else. Bumblebee: Visit next flower, collect pollen, repeat this until too heavily loaded with pollen.

    If the discussion here as to what “open-ended” means concludes that these activities are open-ended loops, then there are many of them.

  22. Patrick:

    “Iteration without explicit termination” might be an objective enough criteria to work with (although identifying it in evolved digital organisms can be non-trivial).

    I’ve tried to understand what he could mean by an “unstructured loop”. He has mentioned terms like recursive, but I don’t see how that applies to the concept. I’m also not clear on what “without explicit termination” could mean. No termination conditions? Isn’t that just an infinite loop?
    In the paper he says:

    By “unstructured loop” I mean a loop in which the looping mechanism is not cleanly separated from the computation which is performed within the loop body

    The best interpretation I can think is self-modifying code. This aligns with the above quote, with mutations in DNA (which he regards as a program), and with UTMs which have their programs as part of the input tape and so open to modification. ETA: self-modifying code also seems consistent with Chaitin’s approach, which johnnyb says is like his.

    But I’m still unclear why such loops in the “DNA program” are needed to generate auto-catalytic loops in metabolic pathways. As best I can tell, both concepts use the word “loop”, therefore one must be needed for the other. I’m sure there is more than that, but I don’t see it.

    As I hinted with my reference to Chaitin, I think the deeper problem with his model is it does not account for the biology.

    For example, I understand him as saying DNA programs must be UTMs because they have to generate any possible system. But, he says, UTMs cannot be viewed, in general, as searching incrementally because such searches are inconsistent with the what he calls the “chaotic” behavior of UTMs. Since evolution is an incremental search for a target, evolution on its own cannot work.

    One issue is the one that RB and others have raised: evolution is not an incremental search for a given target.

    Another issue is raised by this quote from his paper:

    The implementation of solutions to arbitrarily hard problems on Universal machines requires guidance for how the program should change which originates from outside the machine

    He claims that the guidance must come from an outside agent or an outside system that “knows” the solution.

    But that guidance requires neither. Biochemical constraints are one source. And the feedback of the environment through NS is another.

    A final issue I have is that his paper appears to be an attempt at a deductive argument. If so, it is open to disproof by counter-example. So he needs to deal with all the counter-examples provided by evolutionary explanations of auto-catalytic loops.

  23. Mung:
    . What’s more, Ruby has what are called open classes, which means I can alter the implementation of the each method for the entire Array class (as an example).

    That does sound closer to self-modifying code which is how I interpret him.

  24. BruceS,

    But I’m still unclear why such loops in the “DNA program” are needed to generate auto-catalytic loops in metabolic pathways. As best I can tell, both concepts use the word “loop”, therefore one must be needed for the other.

    Now, that‘s equivocation!

    (Fallacy of)

  25. Patrick: “Iteration without explicit termination” might be an objective enough criteria to work with (although identifying it in evolved digital organisms can be non-trivial).

    I’m still open to critical inquiory regarding AVIDA, but I still haven’t seen any response to my questions about how this relates to biochemistry.

    My first solid hint of a serious problem was in the claim that DNA is analogous to programming. That needs some serious discussion.

    There are some analogous operations: Transcription and translation could be roughly construed as equivalent to tape reading. worked in a military comm center that used paper tape. You could read a tape and transmit it, copy it, or print it. Because the tape readers were synchronized to the printing and copying devices, you could get errors. Sort of like the child’s game of telephone, errors could accumulate.

    But biochemistry doesn’t have Gary Gaulin knobs for varying parameters. You can’t design biochemistry with parameters, because there is no way to know in advance what a change of parameter will do. It;s not like an oven where a knob changes the temperature incrementally. Or an aircraft wing where one can change the spacing of rivets incrementally.

    To be analogous to programming, you need a language with syntax. You need to be able to predict the consequences of changes to parameters. You simply don’t have this in biochemistry. There is no escape from cut and try.

  26. johnnyb:
    I just wanted to clarify that the point is more that the termination is not implicit. For example, in ruby, an each() loop is implicitly terminated by the length of the array. It is not possible to have an each() not terminate (unless there is non-termination in the steps within the each()). So, even though this is a fixed number of steps, it is open-ended:

    I’m not sure if the each is supposed to be an example of an unstructured loop?

    If it is, maybe the implicitly here is supposed to mean that some other part of the program could modify the length of the array and affect loop termination from outside the loop? (although not sure if that is consistent with whole paragraph). So in that case consider

    while (f(x)>0.5) {/*stuff*/ }
    where f(x) returns a pseudo-random number between 0 and 1. It seems to meet the condition.

    That f(x) is a function with side effects could be interpreted as a rough sort of self-modifying code as I discussed in above post.

    Anyway, enough pseudo-code and pseudo-arguments for today.

  27. BruceS: Anyway, enough pseudo-code and pseudo-arguments for today.

    Johnny has tried to transfer the OOL argument to computer code.

  28. BruceS,

    I’ve tried to understand what he could mean by an “unstructured loop”. He has mentioned terms like recursive, but I don’t see how that applies to the concept. I’m also not clear on what “without explicit termination” could mean. No termination conditions? Isn’t that just an infinite loop?

    I think he means something like a do-while construct as opposed to a for loop, but I could be wrong.

  29. petrushka: Johnny has tried to transfer the OOL argument to computer code.

    Is Bartlett’s argument that “open-ended loops” are present in Avida but cannot evolve in living systems, and therefor Avida is an inadequate simulation of evolution?

    Or is it an argument about the OOL?

  30. Patrick:
    BruceS,

    I think he means something like a do-while construct as opposed to a for loop, but I could be wrong.

    I think it is more than that, as for is just syntactic sugar for while in languages I am familiar with (but need test at top, so while, not do-while).

    for (init;c;inc){…} same as init;while(c){…;inc};

    You can do something similar for for-each depending on the syntax for pointers or whatever the language uses to work directly with the objects for-each iterates over.

  31. Joe Felsenstein: Is Bartlett’s argument that “open-ended loops” are present in Avida but cannot evolve in living systems, and therefor Avida is an inadequate simulation of evolution?

    Or is it an argument about the OOL?

    I’ve tried to follow the 2010 paper, at least the intro and the sections on IC. Open-ended or unstructured loops occur both in the code and in the biology.
    My understanding of his argument:

    Kauffman (1993, p. 12) notes that the ability to generate an arbitrary diversity of organisms by means of reprogramming the DNA makes biology analyzable under the same kind of terms as universal computers (i.e., Universal Turing Machines),

    In the paper, he calls the loops “unstructured loops” and says the UTMs implemented by the DNA must include them to generate complication biological loops. He also says such UTMs must be “chaotic” which he claims means that cannot produce such outcomes by incremental processes like evolution. Examples of biological loops he gives in the paper involve certain gene regulation mechanisms where

    • The function of the downstream pathway of the regulated gene
    is dependent on the gene being repressed at the appropriate
    time.
    • The products which turn off the regulated gene are manufactured
    downstream of the gene itself.

    I believe in posts on this thread he also mentioned auto-catalytic loops.

    Avida has been discussed, but he does not want to be stuck on one implementation. He says

    Here’s my challenge. Find *any* evolved algorithm (on any system, not just Avida) such that:

    (a) It includes open-ended loops that contribute to function
    (b) it is a Turing-complete language/system (or at least a decent approximation)
    (c ) the mutating system does not in itself guide the creation of open-ended loops
    (d) it doesn’t loop on a favored variable (i.e. such that the variable is implicitly encoded)

  32. OK. I see he is not just being critical of Avida as a good-enough model of evolution.

    Instead he has sort-of concluded that an explanation of evolution must involve the genome being Turing-complete “or at least a decent approximation”.

    I can’t see why. Are, bacteria, for example Turing-complete automata?

  33. Joe Felsenstein:
    OK.I see he is not just being critical of Avida as a good-enough model of evolution.

    Instead he has sort-of concluded that an explanation of evolution must involve the genome being Turing-complete “or at least a decent approximation”.

    I can’t see why.Are, bacteria, for example Turing-complete automata?

    His claims as I understand them: Given that one can analyze the genome as a Turing machine, section 2.5 of his paper discusses why it has to be UTM. Further the “chaotic parts”* of the UTM must be used for IC phenomena. This means they cannot have arisen incrementally by evolution.

    What about counter-examples of how IC systems could have evolved incrementally? He tries to explain away those away in section 2.6 (an outside agent did it or some premise to his model does not apply)

    Anyway, trying to puzzle out that paper out was an interesting intellectual exercise, but I think I’ve now reached my limit for that type of exercise.
    —————
    * For chaotic, he refers to 4 classifications of TMs done by Wolfram. But I think Wolfram was classifying cellular automata, not TMs. Wolfram said that only class 4 in his analysis, which produced chaotic results, were equivalent to UTMs. So it’s not clear how the references to Wolfram apply

    I interpret his “chaotic portion” of the UTM as those inputs which are “close” according to some measure and yet which produce output which diverges. But I cannot follow his explanation of why that property is needed to produce the IC biological loops he describes.

  34. UTMs have, if I recall correctly, an infinitely long “tape” to write digits on, and read them from.

    Genomes are of finite length.

    So are computer memories — the rather capable machine I type this on is not, technically, able to simulate a UTM.

  35. BruceS,

    I think he means something like a do-while construct as opposed to a for loop, but I could be wrong.

    I think it is more than that, as for is just syntactic sugar for while in languages I am familiar with (but need test at top, so while, not do-while).

    for (init;c;inc){…} same as init;while(c){…;inc};

    You can do something similar for for-each depending on the syntax for pointers or whatever the language uses to work directly with the objects for-each iterates over.

    Sorry, I was unclear. I think he is distinguishing between a for loop with a specific number of iterations and a while loop with a conditional number of iterations. Still not sure, though.

  36. Patrick:

    Sorry, I was unclear.I think he is distinguishing between a for loop with a specific number of iterations and a while loop with a conditional number of iterations.Still not sure, though.

    I’ve realized that the paper used a gene regulation example, not autocatalytic loops. I need to understand the biology of that example better, which is probably something I should do in any event. If it sheds any light on what he means, that I’ll post a followup.

    Also, my idea of self-modifying code was based on an intuition of how he incorporated mutation and its effect on the “DNA program” into his analysis. I’m not sure if that intuition was right, but I don’t want to spend more time on the paper trying to pin it down.

  37. Joe Felsenstein:
    UTMs have, if I recall correctly, an infinitely long “tape” to write digits on, and read them from.

    Genomes are of finite length.

    So are computer memories — the rather capable machine I type this on is not, technically, able to simulate a UTM.

    Yes, and the reality of finiteness must impose some limits on chaotic behaviour.

    He justifies use of Turing machines by a reference to Kaufmann’s book, which I don’t have access to, but I see from the Amazon preview’s index that the author devotes many pages to Turing machines at the end of the book.

  38. Joe Felsenstein: Is Bartlett’s argument that “open-ended loops” are present in Avida but cannot evolve in living systems, and therefor Avida is an inadequate simulation of evolution?
    Or is it an argument about the OOL?

    Looks like an OOA argument to me. It’s not about the simulation of evolution. It’s about the origin of the simulator.

  39. BruceS: • The function of the downstream pathway of the regulated gene
    is dependent on the gene being repressed at the appropriate
    time.
    • The products which turn off the regulated gene are manufactured
    downstream of the gene itself.

    Okay, this looks to me like he is arguing that biological evolution must have foresight. That it must simultaneously implement a lock and key.

    Even Shapiro isn’t saying that, and I suspect he would if he could get away with it.

  40. petrushka: Okay, this looks to me like he is arguing that biological evolution must have foresight. That it must simultaneously implement a lock and key.

    Even Shapiro isn’t saying that, and I suspect he would if he could get away with it.

    I think it is supposed to be a description of how some instances of gene regulation work according to science. But I don’t understand the biology, so that is just my guess.

    An example of a relatively irreducibly complex mechanism, then, would be the control of the flagellar assembly in the bacterium Psuedomonas aeruginosa, which uses a multilevel control system to regulate the formation of the flagellum. FleQ
    is a transcription factor that regulates a number of other genes used in flagellar assembly. One of the downstream products of the assembly is FleN. FleN interacts with FleQ to deactivate it, preventing multiflagellation (Dasgupta et al. 2003). The regulation of FleQ is done downstream of FleQ itself, making a
    step-at-a-time evolution of the pathway extremely difficult.

    Pallen and Matzke (2006) argue for the exaptational origin
    of the flagellum. As we’ve shown, just the FleQ/FleN pathway
    makes the evolution of this system solely by natural selection
    unlikely.

Leave a Reply