Good Math/Bad Math

Friday, March 17, 2006

The Problem with Irreducible Complexity

Today, I thought I'd take on another of the intelligent design sacred cows: irreducible complexity. This is the cornerstone of some of the really bad arguments used by people like Michael Behe.

To quote Behe himself:


By irreducibly complex I mean a single system composed of several well-matched, interacting parts that contribute to the basic function, wherein the removal of any one of the parts causes the system to effectively cease functioning. An irreducibly complex system cannot be produced directly (that is, by continuously improving the initial function, which continues to work by the same mechanism) by slight, successive modifications of a precursor system, because any precursor to an irreducibly complex system that is missing a part is by definition nonfunctional. An irreducibly complex biological system, if there is such a thing, would be a powerful challenge to Darwinian evolution. Since natural selection can only choose systems that are already working, then if a biological system cannot be produced gradually it would have to arise as an integrated unit, in one fell swoop, for natural selection to have any thing to act on.


Now, to be clear and honest upfront: Behe does not claim that this is a mathematical argument. But that doesn't mean that I don't get to use math to shred it.

There are a ton of problems with the whole IC argument, but I'm going to take a different tack, and say that even if those other flaws weren't there, it's still a meaningless argument. Because from a mathematical point of view, there's a critical, fundamental problem with the entire idea of irreducible complexity: you can't prove that something is irreducible complex.

This is a result of some work done by Greg Chaitin in Algorithmic Complexity Theory. A fairly nifty version of this can be found on Greg's page.

The fundamental result is that given a complex system, you cannot in general show that there is no smaller/simpler system.

As usual for algorithmic information theory, the proof is in terms of computer programs, but it works beyond that; you can think of the programs as programs to simulate a device.

First, suppose that we have a programming system, which we'll treat as a function. P(x) = the result of running program x on P. x is both a program, and its input data, coded into a single string, so x=(c,d), where c is code, and d is data.

Now, suppose we have a formal axiomatic system, which describes the basic rules that P operates under. We can call this FAS.

If it's possible to tell where you have minimal program using the axiomatic system, then you can write a program that examines other programs, and determines if they're minimal. Even better: you can write a program that will generate a list of every possible minimal program, sorted by size.




Let's jump aside for just a second to show how you can do that, generate every possible minimum program:


  1. First, write a program which generates every possible string of one character, then every possible string of two characters, etc., and outputs them in sequence.
  2. Connect the output of that program to another program, which checks each string that it receives as input to see if it's a syntactically valid program. If it is, it outputs it. If it isn't, it just discards it.

  3. At this point, we've got a program which is generating every possible program for P. Now, remember that we said that using FAS, we can write a program that tests an input program to determine if its minimal. So, we use that program to test out inputs, to see if they're minimal. If they are, we output them; if they aren't, we discard them.


Now, let's take a second, and write out the program in mathematical terms:

Remember that P is a function modeling our computing system, FAS is the formal axiomatic system. We can describe P as a function from a combination of program and data to an output: P(c,d)=result.

In this case, c is the program above; d is FAS. So P(c,FAS)=a list of minimal programs.




Ok, now, back to the main track.

Take our program, c, and our formal axiomatic system, FAS, and compute their
length. Call that l.

Now, run P(c,FAS) until it generates a string longer than l.

Ok. Now, write a program c' that for P that runs P(c,FAS) until the length of the output is larger than l + some constant. Set the constant to the length of c'.

What does this program do? It runs a program which generates a sequence of minimal programs until it finds one larger than itself plus all of its data, then it runs that and emits the output.

So - c' finds and outputs a supposedly minimal program larger than
itself
. But since c' is a program which emits the same result
but is smaller, the other program isn't minimal.

Evil, huh?

But the point of it is quite deep. It's not just a mathematical game. We can't tell when something complicated is minimal. Even if we knew every relevant fact about all of the chemistry and physics that affects things, even if the world were perfectly deterministic, we can't tell when something is as simple as it can possibly be.

So irreducibly complexity is useless in an argument; because we can't know when something is irreducibly complex.

21 Comments:

  • Interesting post. As someone who believes in evolution but does not believe that random mutation combined with natural selection is not an adequate mechanism to explain speciation, I have always found Behe's arguments interesting and the rebuttals unconvincing as they have tended to focus on some computer model a researcher created to "prove" a bacterial flagellum or whatever can arise from incremental changes. This is actually a much better rebuttal because the claim that something is IR is non-falsifiable.

    By Anonymous steve, at 4:46 PM  

  • Besides, Steve, modern evolutionary theory does not model speciation solely as a result of random mutation and natural selection. This is a crucial misunderstanding amongst the throngs of anti-evolutionists. The idea of random mutation and natural selection acting exclusively, is nothing more than a strawman assembled by strategic obfuscation and diversionary tactics by the politicos of the DI, the CRI, and the like.

    By Blogger Don Sheffler, at 7:14 PM  

  • I have always found Behe's arguments interesting and the rebuttals unconvincing as they have tended to focus on some computer model a researcher created to "prove" a bacterial flagellum or whatever can arise from incremental changes.

    I think you're probably thinking about the mathematical model that Nilsson and Pelger used to demonstrate that the eye was evolvable. The equivalent for the flagellum is Matzke's incredibly detailed step-by-step description of how it's believed the flagellum evolved.

    I agree that Behe's argument is superficially convincing. However, when you think about it for a moment, it's easy to produce an irreducibly complex system. Just take a reducibly complex system and remove as many components from it as you can :)

    The idea of random mutation and natural selection acting exclusively, is nothing more than a strawman assembled by strategic obfuscation and diversionary tactics by the politicos of the DI, the CRI, and the like.

    Although, to be fair, I believe that RM and NS are currently considered to be by far the most prominent causes involved in evolution.

    By Blogger Lifewish, at 8:38 PM  

  • I love your site! go get 'em, shredder!

    By Anonymous unca paddy, at 8:58 PM  

  • An interesting post, but it doesn't really rebut Behe: irreducible complexity doesn't claim that a system S is minimal in some sense, only that all reasonable precursors to S are non-functional.

    For example, he might claim that a classic mousetrap is IC. Showing that a gluetrap is simpler does not disprove his point.

    Of course, Behe's argument is fundamentally rubbish: we need to show that all precursors to S are non-functional in the sense of totally useless, not in the sense of unable to do what S does. The fact that he hasn't been able to identify anything that is IC is point in favor of evolution.

    By Blogger Gorobei, at 11:53 PM  

  • gorobei:

    You're actually missing one key thing about this proof. It's not saying something like "A spring-type mousetrap isn't provably IC because a glue type trap is simpler". It's saying that even in a _specific_ device, you can't in general tell whether it's IC.

    For a mousetrap, that may seem kind of facile. But remember that even for that mousetrap, people have pointed out various things that _can_ be eliminated. And if you're talking about something vastly more complicated like a biological system, you can't really argue that something is IC - because you can't be sure that it is.

    By Blogger MarkCC, at 10:47 AM  

  • One other comment about the whole IC thing. I may turn this into a full post at some point, but just to get it out there:

    If you consider the combination of the Dembski search stuff, and this IC stuff, there's a nifty math argument about IC.

    Behe uses a constructive argument about IC: you can't create it because if you remove any part of it, it stops working; so it must have come into existence in exactly one step.

    But if you think in terms of evolution as search over a landspace, where more complex things are "higher", and simpler things are "lower", then one of the possibilities is that you need to pass over a ridge to get into a valley. The low point of the valley is an IC system. So you needed to gradually evolve something more complicated, of which the supposedly IC system was a subcomponent. Then the evolutionary process _eliminates_ the unneeded pieces, leaving the IC system.

    Behe always deliberately sidesteps this argument, and just repeatedly hammers away on the constructive part, because it's the only way that his argument can work.

    By Blogger MarkCC, at 10:54 AM  


  • So irreducibly complexity is useless in an argument; because we can't know when something is irreducibly complex.


    I think the proof says that we can't have a program which for any arbitrary program will tell us whether it is IC or not. But it doesnt say that we cannot decide for any specific program whether it is IC or not.

    Basically its like halting problem. We cannot have a program that decides whether a program halts or not. But clearly

    while(1){
    }

    doesnt halt.

    So it might be possible to create a system which can be shown to be IC.

    By Anonymous viked, at 12:06 PM  

  • markcc,

    you point is well taken that, in general, we can't decide if a system is IC.

    This is still setting the bar too high for Behe: he only needs to find one specific system that is provable IC. As Viked noted, we can solve the halting problem for some specific programs.

    I suppose Behe could further argue that since the universe is just a big FSA rather than a Turing machine equivalent, this line of inquiry is inapplicable to his theory.

    By Blogger Gorobei, at 12:14 PM  

  • The whole argument over IC is ridiculous anyway. For starters, Behe would have us prove a negative to convince him and his minions that it's not impossible for any system to have evolved incrementally or to have been reduced from another more complex set of systems.

    Gorobei, as Mark says nothing is "provable IC". You may very well show that something doesn't retain the same function by removing some number of critical components, but this is far from showing IC. FAR. Maybe he could mix in a little scientific method.

    You can't just say that there is no possible path to the current position just because you can't envision one, and then try to put the onus on everyone to prove you wrong. If the flagella previously had a different function or was part of a set of components that have since been eliminated, thus producing its current function, no one could prove such to any level of satisfaction for Behe & Co.

    And this is what he banks on.

    The simplicity of the idea of evolution and its processes of co-opting, combining, distorting, sorting and eliminating, is that everything had, or was part of, a different function previously.

    Behe is just pointing to one where the exact series of steps is not yet well understood. Kind of pathetic that somebody would commit his career to such nonsense.

    To me, his "Ah Hah!" just sounds like Harpo's little horn.

    By Blogger Don Sheffler, at 2:01 PM  

  • Mark CC,

    Regarding your comparison of complexity to a landscape, it is important that people, not necessarily you Mark, distguish a "complexity landscape" which you describe and a "fitness landscape" which is what most other evolutionist mean by "landscape." With that qualifier in mind, I though that this analogy it one of the best descriptions I've ever heard. (Ruse uses the example of an arch bridge which can have its supports taken out once the bridge is in place, but I like the landscape analogy better.)

    I'm also curious to know just what this new idea of "compositional evolution" is supposed to contribute to our understanding of what now appears to be "IC."

    By Blogger jeff g, at 4:31 PM  

  • steve:

    As much as I'd like to take credit for a particularly convincing argument, I don't think that this argument is as strong as many of the other critiques of IC - it just comes at it from a different direction. Sort of piling on to the already large heap.

    The thing is, IC is a really bad argument. It comes down to "I can't see how X happened, therefore, X couldn't have happened." It's an incredibly arrogant argument, because it's fundamentally built on the notion that nothing in nature can exceed his imagination.

    The fact of the matter is, IC is meaningless; and even if it were meaningful, it still wouldn't be a good argument.

    By Blogger MarkCC, at 8:11 PM  

  • viked:

    The point of this argument is that the notion of IC is essentially meaningless. It actually happens, if you look at algorithmic complexity, that the paradoxical cases, where you can't know if it's minimal or not are extremely common - and generally, you can't prove that any particular minimal system really is minimal. It's much worse than the halting problem: the halting problem relies on an explicitly self-referential program to break things; this AIC minimum complexity problem is much more subtle. The allegedly irreducible program is not special in any way - it's a property of the system around it.

    That's what's particularly interesting about this proof. Anything could in fact be a "problem case" that can be evaded. And when it's a problem case, what that means is that there's a perfectly valid proof of its minimality; but that proof is wrong because of fundamental incompleteness problems in mathematics itself.

    By Blogger MarkCC, at 8:18 PM  

  • Mark,

    I think gorobei's first point is correct. Under Behe's definition of irreducible complexity, an IC system need not be minimal in an absolute sense. The removal of any part destroys the system's function, but that does not mean that there is not a simpler system, made of different parts, which has the same function. A minimal system is irreducibly complex, but an irreducibly complex system need not be minimal.

    To put this in the language of your post, a program is irreducibly complex if the removal of any character causes the output to change. This does not mean that there is not a shorter program, composed of different characters, which produces the same output. A program need not be minimal to be IC, but if it is minimal it is guaranteed to be IC.

    The flaw in Behe's definition, of course, is that it doesn't cover changes in funtion as parts are added or removed (what Behe calls "indirect" routes). Behe admits that indirect routes are possible "in principle", but he argues that they are highly improbable. How he feels he can reach that conclusion without enumerating all possible indirect paths is beyond me.

    By Blogger keiths, at 10:45 AM  

  • "Behe admits that indirect routes are possible "in principle", but he argues that they are highly improbable. How he feels he can reach that conclusion without enumerating all possible indirect paths is beyond me."

    Exactly. And in any case this brings us back to the fact that 'improbable' isn't 'impossible'.

    By Blogger Don Sheffler, at 4:52 PM  

  • If I'm reading the proof correctly, it shows that there's no rule that will correctly tell, for all programs, whether or not the program is minimal. But assuming that IC is the type of complexity contemplated by the proof, the assumption is too strong. The IC argument doesn't require a rule that applies to all systems: it only needs a rule that applies to SOME system.

    Say it's a map to the space {minimal, don't know} rather than a map to {minimal, not minimal}. So when our algorighm maps to minimal, we know the algorithm is minimal, but when it maps to don't know, we have no information. Consequently, we can't generate an algorithm that generates all possible minimal programs, and the proof no longer holds.

    Also, doesn't the proof assume without proof that the minimal programs are not all of the same length? If they are, then we can't generate a minimal program longer than l.

    Of course, I may be misunderstanding what's going on here.

    By Anonymous Anonymous, at 3:59 AM  

  • In addition to the problem already mentioned, the proof also makes implicit use of the program being able to discriminate between an (at least) countably infinite set of inputs. Otherwise you could check off the responses to each input and directly compare a program's possible responses to those of every one smaller than it in finite time.

    In real terms, this means you would have to show the existence of an infinite set of scenarios and the existence of organisms that can discriminate between any two elements from a shared countable subset of them.

    There are also further conditions needed.

    None the less, an interesting idea ;).
    Keep fighting the good fight.

    By Anonymous Chris, at 6:15 AM  

  • The other obvious problem is that proof, as they say, is for mathematics and alcohol. If the goal is to make ID into science, it isn't clear why proof of minimal complexity would be needed.

    By Blogger Macht, at 12:19 PM  

  • Proving that irreducible complexity is impossible is unnecessary. A far more interesting calculation is the thermodynamic probability of such a structure forming given the available antecedents and information from the environment.

    By Blogger Mark Butler, at 3:16 PM  

  • I should say rather that "proving a particular system is irreducibly complex is unnecessary"...

    By Blogger Mark Butler, at 3:20 PM  

  • markb:

    First - this post is disputing with Behe's irreducible complexity argument. It's not a valid argument mathematically, which is the point I was addressing.

    Second - with respect to probability, I do not in general consider probability arguments at all convincing; probability calculations depend on a lot of assumptions that we cannot presently validate, because we do not know enough; and all that a probability argument can do is provide a really big number to say "It's unlikely that this would happen". But unlikely things happen all the time - arguing that something *can't* happen can't be done with probability.

    Finally, that "information from the environment" line is, shall we say, questionable - it's not particularly meaningful; it's a way of saying "the surrounding environment", but phrasing it in a way that looks suspiciously like just another attempt at weasel-words to provide some way of saying "God must have done it".

    By Blogger MarkCC, at 4:11 PM  

Post a Comment

Links to this post:

Create a Link

<< Home