* As I mentioned yesterday, I’m going to repost a few of my critiques of the bad math of the IDists, so that they’ll be here at ScienceBlogs. Here’s the first: Behe and irreducibly complexity. This isn’t quite the original blogger post; I’ve made a few clarifications and formatting fixes; but the content remains essentially the same. You can find the original post in my blogger information theory index. The original publication date was March 13, 2006.*

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: given a system S, you cannot in general show that there is no smaller/simpler system that performs the same task as S.

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 the instructions to build and/or operate an arbitrary device.

First, suppose that we have a computing system φ, which we’ll treat as a function. So φ(x) = the result of running program x on φ. 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 φ 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 generate a list of every possible minimum program. Here’s a sketch of the program:

- 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.
- 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 for φ. If it is, it outputs it. If it isn’t, it just discards it.
- At this point, we’ve got a program which is generating every possible program for φ. 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 our 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 φ is a function modeling our computing system, FAS is the formal axiomatic system. We can describe φ as a function from a combination of program and data to an output: φ(c,d)=result.

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

Now, back to the main track.

Using the program that we sketched above, given any particular length, we can easily generate programs larger than that length.

Take our program, c, and our formal axiomatic system, FAS. and compute their

length. Call that l(c,FAS). If we know l(c,FAS), we can run φ(c,FAS) until it generates a string *longer* than l(c,FAS).

Ok. Now, write a program c’ that for φ that runs φ(c,FAS) until it finds a program K, where the length of the output of φ(K) is larger than l(c,FAS) + length(c’). c’ then outputs the same thing as φ(K).

This is the tricky part. What does this program do? It runs a program which generates a sequence of provably minimal programs. It runs those provably minimal programs until it finds one *larger than itself plus all of its data*. Then it runs that and emits the output.

So – c’ outputs the same result as a supposedly minimal program K, where K is *larger than c’ and its data*. But since c’ is a program which emits the same result as K, *but is smaller*, then K *cannot* be minimal.

No matter what you do – no matter what kind of formal system you’ve developed for showing that something is minimal, you’re screwed. Godel just came in and threw a wrench into the works. There is absolutely no way that you can show that any system is minimal – the idea of doing it is intrinsically contradictory.

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.