Extreme math: 1 + 1 = 2

Finally, I have found online, a copy of the magnificent culmination of the 20th century’s most ambitious work of mathematics. The last page of Russel and Whitehead’s proof that 1+1=2. On page 378 (yes, three hundred and seventy eight!) of the Principia Mathematica.. Yes, it’s there. The whole thing: the entire Principia, in all of its hideous glory, scanned and made available for all of us to utterly fail to comprehend.

oneplusone.jpg

For those who are fortunate enough not to know about this, the Principia was, basically, an attempt to create the perfect mathematics: a complete formalization of all things mathematical, in which all true statements are provably true, all false statements are provably false, and no paradoxical statements can even be written, much less proven.

Back at the beginning of the 20th century, there was a lot of concern about paradox. Set theorists had come across strange things – things like the horrifying set of all sets that don’t contain themselves. (If it contains itself, then it doesn’t contain itself, but if it doesn’t contain itself, then it contains itself. And then really bad actors need to pretend to be robots short-circuiting while Leonard Nimoy looks on smugly.)

So some really smart guys named Bertrand Russell and Alfred North Whitehead got together, and spent years of their lives trying to figure out how to come up with a way of being able to do math without involving bad actors. 378 pages later, they’d managed to prove that 1+1=2. Almost.

Actually, they weren’t there yet. After 378 pages, they were able to talk about how you could prove that 1+1=2. But they couldn’t actually do it yet, because they hadn’t yet managed to define addition.

And then, along came this obnoxious guy by the name of Kurt Godel, who proceeded to show that it was all a big waste of time. At which point I assume Russell and Whitehead went off and had their brains explode, pretty much the same way that the bad actors would later pretend to do.

Don't forget the SB challenge

I don’t want to get too NPR-ish, but: Just a quick reminder about our SB charity thing. GM/BM readers have donated almost $1000 dollars to help get desparately needed supplies for math teachers. And our benevolent Seed overlords are matching up to the first $10,000 worth of contributions through ScienceBlog challenges.
Help some great kids get the chance to learn math and science.

Good Math, Repeating Decimals, and Bad Math

Just saw a nice post at another math blog called Polymathematics about something that bugs me too… The way that people don’t understand what repeating decimals mean. In particular, the way that people will insist that 0.9999999… != 1. As a CS geek, I tend to see this as an issue of how people screw up syntax and semantics.

And it has some really funny stupidity in the comments. 0.9999999… = 1.

One quick quote from the post, just because it’s a nifty demonstration of the fact which I’ve not seen before: (I replaced a GIF image in the original post with a text transcription.)

Let x = 0.9999999…, and then multiply both sides by 10, so you get 10x = 9.9999999… because multiplying by 10 just moves the decimal point to the right. Then stack those two equations and subtract them (this is a legal move because you’re subtracting the same quantity from the left side, where it’s called x, as from the right, where it’s called .9999999…, but they’re the same because they’re equal. We said so, remember?):

10x = 9.99999999...
-        x =  0.99999999...
-------------------------
9x = 9

Surely if 9x = 9, then x = 1. But since x also equals .9999999… we get that .9999999… = 1. The algebra is impeccable.

I also need to quote the closing of one of the comments, just for its sheer humor value:

Bottom line is, you will never EVER get 1/1 to equal .99999999… You people think you can hide behind elementary algebra to fool everyone, but in reality, you’re only fooling yourselves. Infinity: The state or quality of being infinite, unlimited by space or time, without end, without beginning or end. Not even your silly blog can refute that.

Friday Random Ten, June 16

  1. The Stills, “In the Beginning”. I accidentally downloaded this from Salon this morning. I know absolutely nothing about the band.
  2. Planet X, “Digital Vertigo”. PlanetX is quite a strange group. All instrumental, something like a cross between bebop and heavy metal. Great group, highly recommended.
  3. Darol Anger and the Republic of Strings, “Ouditarus Rez”. Darol is one of my favorite musicians. He’s a violinist who at different times has played everything from classical to jazz to bluegrass to rock; he’s performed with everyone from Emmylou Harris to Bela Fleck to Joshua Bell. The Republic of Strings is one of his recent ventures; and they do a range of styles from old-time fiddle tunes, to full-of-fire country fiddling, to jazz vocal tunes.
  4. Flook, “Larry Get Out of the Bin / Elzic’s Farewell”. Flook is the greatest instrumental Irish band in the known universe. 4 people, all accousting: probably the worlds best tinwhistle player, an great alto flute(!)/accordion player, one of the greatest bodhran player’s I’ve ever heard, and a really amazing rythym guitarist. Do not miss an opportunity to hear these guys live; even if you think you don’t like Irish music, go hear them, they’ll change your mind.
  5. Oregon, “Prelude”. Oregon is trio playing interesting bop jazz. Sometimes atonal, sometimes downright ugly, sometimes amazing. Led by an Oboe/English horn player who used to do a lot of touring with Bela Fleck before Bela hooked up with Jeff Coughin. (Who is a truly horrible player in my opinion; I don’t know what Bela sees in Jeff; the guy’s loud, repetitive, loud, dull, loud, non-creative, loud, gimmicky, and loud.)
  6. Suzanne Vega, “Straight Lines”. Great tune off of my favorite Suzanne Vega album. I really like her very sparse old stuff.
  7. Solas, “The Wiggly Jigs”. More trad Irish.
  8. Porcupine Tree, “Prodigal”. PT is one of my favorite neo-progressive bands. They’ve got a really great sound, blending almost bizzarely smooth vocals with dense distorted guitar.
  9. Dream Theater, “Stream of Consciousness”. Dream Theater is neo-progressive heavy metal. Great if you like that kind of thing, which I definitely do.
  10. Lunasa, “The Cullyback Hop”. And one more trad Irish band. Lunasa is a very traditional instrumental Irish band. Very up-tempo, a bit too much so at times, but full of amazing energy, traditional instrumentation, and a very trad style. Melody lead is generally flute and Uillean bagpipes, with guitar and bass backing. It’s damned hard to sit through a Lunasa album without wanting to get up and dance. The ultimate Irish concert experience would be a double billing of Flook and Lunasa.

What timing! Dembski again demonstrates innumeracy

Right after finishing my post about how Dembski has convinced me that he is not a competent mathematician, I find PZ linking to a Panda’s Thumb post about Dembski, which shows how he does not understand the meaning of the mathematical term “normalization”.
Go look at the PT post: Something rotten in Denmark?
Is this guy really the best mathematician the ID folks have available to represent them?

Dembski's Profound Lack of Comprehension of Information Theory

I was recently sent a link to yet another of Dembski’s wretched writings about specified complexity, titled Specification: The Pattern The Signifies Intelligence.
While reading this, I came across a statement that actually changes my opinion of Dembski. Before reading this, I thought that Dembski was just a liar. I thought that he was a reasonably competent mathematician who was willing to misuse his knowledge in order to prop up his religious beliefs with pseudo-intellectual rigor. I no longer think that. I’ve now become convinced that he’s just an idiot who’s able to throw around mathematical jargon without understanding it.
In this paper, as usual, he’s spending rather a lot of time avoiding defining specification. Purportedly, he’s doing a survey of the mathematical techniques that can be used to define specification. Of course, while rambling on and on, he manages to never actually say just what the hell specification is – just goes on and on with various discussions of what it could be.
Most of which are wrong.
“But wait”, I can hear objectors saying. “It’s his theory! How can his own definitions of his own theory be wrong? Sure, his theory can be wrong, but how can his own definition of his theory be wrong?” Allow me to head off that objection before I continue.
Demsbki’s theory of specicfied complexity as a discriminator for identifying intelligent design relies on the idea that there are two distinct quantifiable properties: specification, and complexity. He argues that if you can find systems that posess sufficient quantities of both specification and complexity, that those systems cannot have arisen except by intelligent intervention.
But what if Demsbki defines specification and complexity as the same thing? Then his definitions are wrong: because he requires them to be distinct concepts, but he defines them as being the same thing.
Throughout this paper, he pretty ignores the complexity to focus on specification. He’s pretty careful never to say “specification is this”, but rather “specification can be this”. If you actually read what he does say about specification, and you go back and compare it to some of his other writings about complexity, you’ll find a positively amazing resemblance.
But onwards. Here’s the part that really blew my mind.
One of the methods that he purports to use to discuss specification is based on Kolmogorov-Chaitin algorithmic information theory. And in his explanation, he demonstrates a profound lack of comprehension of anything about KC theory.
First – he purports to discuss K-C within the framework of probability theory. K-C theory has nothing to do with probability theory. K-C theory is about the meaning of quantifying information; the central question of K-C theory is: How much information is in a given string? It defines the answer to that question in terms of computation and the size of programs that can generate that string.
Now, the quotes that blew my mind:

Consider a concrete case. If we flip a fair coin and note the occurrences of heads and tails in
order, denoting heads by 1 and tails by 0, then a sequence of 100 coin flips looks as follows:

(R) 11000011010110001101111111010001100011011001110111
00011001000010111101110110011111010010100101011110.

This is in fact a sequence I obtained by flipping a coin 100 times. The problem algorithmic
information theory seeks to resolve is this: Given probability theory and its usual way of
calculating probabilities for coin tosses, how is it possible to distinguish these sequences in terms
of their degree of randomness? Probability theory alone is not enough. For instance, instead of
flipping (R) I might just as well have flipped the following sequence:

(N) 11111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111.

Sequences (R) and (N) have been labeled suggestively, R for “random,” N for “nonrandom.”
Chaitin, Kolmogorov, and Solomonoff wanted to say that (R) was “more random” than (N). But
given the usual way of computing probabilities, all one could say was that each of these
sequences had the same small probability of occurring, namely, 1 in 2100, or approximately 1 in
1030. Indeed, every sequence of 100 coin tosses has exactly this same small probability of
occurring.
To get around this difficulty Chaitin, Kolmogorov, and Solomonoff supplemented conventional
probability theory with some ideas from recursion theory, a subfield of mathematical logic that
provides the theoretical underpinnings for computer science and generally is considered quite far
removed from probability theory.

It would be difficult to find a more misrepresentative description of K-C theory than this. This has nothing to do with the original motivation of K-C theory; it has nothing to do with the practice of K-C theory; and it has pretty much nothing to do with the actual value of K-C theory. This is, to put it mildly, a pile of nonsense spewed from the keyboard of an idiot who thinks that he knows something that he doesn’t.
But it gets worse.

Since one can always describe a sequence in terms of itself, (R) has the description

copy '11000011010110001101111111010001100011011001110111
00011001000010111101110110011111010010100101011110'.

Because (R) was constructed by flipping a coin, it is very likely that this is the shortest
description of (R). It is a combinatorial fact that the vast majority of sequences of 0s and 1s have
as their shortest description just the sequence itself. In other words, most sequences are random
in the sense of being algorithmically incompressible. It follows that the collection of nonrandom
sequences has small probability among the totality of sequences so that observing a nonrandom
sequence is reason to look for explanations other than chance.

This is so very wrong that it demonstrates a total lack of comprehension of what K-C theory is about, how it measures information, or what it says about anything. No one who actually understands K-C theory would ever make a statement like Dembski’s quote above. No one.
But to make matters worse – this statement explicitly invalidates the entire concept of specified complexity. What this statement means – what it explicitly says if you understand the math – is that specification is the opposite of complexity. Anything which posesses the property of specification by definition does not posess the property of complexity.
In information-theory terms, complexity is non-compressibility. But according to Dembski, in IT terms, specification is compressibility. Something that possesses “specified complexity” is therefore something which is simultaneously compressible and non-compressible.
The only thing that saves Dembski is that he hedges everything that he says. He’s not saying that this is what specification means. He’s saying that this could be what specification means. But he also offers a half-dozen other alternative definitions – with similar problems. Anytime you point out what’s wrong with any of them, he can always say “No, that’s not specification. It’s one of the others.” Even if you go through the whole list of possible definitions, and show why every single one is no good – he can still say “But I didn’t say any of those were the definition”.
But the fact that he would even say this – that he would present this as even a possibility for the definition of specification – shows that Dembski quite simply does not get it. He believes that he gets it – he believes that he gets it well enough to use it in his arguments. But there is absolutely no way that he understands it. He is an ignorant jackass pretending to know things so that he can trick people into accepting his religious beliefs.

A really easy "Ask an SBer".

As usual for this time of the week, the seed folks have tossed out a new “Ask a Science-Blogger” question for us to answer. This weeks is particularly easy. The question:

How is it that all the PIs (Tara, PZ, Orac et al.), various grad students, post-docs, etc. find time to fulfill their primary objectives (day jobs) and blog so prolifically?

The answer: Insanity.
(Full disclosure: I’m not a PI; that is, I’m not an academic researcher who needs to do grant proposals to get funding for my projects. However, I am a professional researcher for an industrial research lab, and while I don’t write grant proposals, I do write project proposals to get projects funded, and I have to show results to the people who give me money for my projects. In the end, it’s not all that different.)

Help the SB gang help schools.

Janet over at Adventures in Ethics and Science has gotten a bunch of us SB folks to get involved in raising money for school science programs. As the only current resident math geek around here, I’m expanding it from just science to also math.
What we’re doing is trying to get people to donate to DonorsChoose.org. That’s an organization where teachers who’s classrooms lack the supplies that they need can submit proposals, and donors can select specific proposals that they want to support. Each of the participants from SBs has picked a bunch of proposals that we think are valuable, and we’re asking you guys, our readers, to look at those proposals, and donate some money to whichever ones you think are worth supporting.
This is something that is very near and dear to my heart. Back in my college days, I did some teaching for something called the Educational Opportunity Fund in NJ. EOF is now gone due to budget cuts. But back then, the idea of it was, take a bunch of really smart kids from really bad schools, and bring them to Rutgers for the summer. For the summer, they worked two days a week, and took classes three days a week. During the school year, they also had to go to EOF classes every weekend. If they continued to participate in this all the way through high school, then EOF would give them a scholarship to Rutgers. I taught for the EOF summer program for three years. And I got to know some of the smartest, greatest kids you could ever hope to meet.
One of the things about working for EOF that used to depress me was talking to my kids about their normal schools. They went to schools where there weren’t enough textbooks – or often any textbooks – much less any better school supplies. If it wasn’t for EOF, most of these kids would never have had any chance to get to college: not because they weren’t smart enough, and not because they weren’t willing to work hard enough; and not even because the teachers in their schools weren’t good enough to prepare them for college. They would have had no chance simply because in a classroom with no books, with no paper, with no chalk – there’s no way to teach them.
My daughter started kindergarten this year. Her kindergarten classroom – just one kindergarten classroom for 20 kids – has more supplies for teaching math than the entire schools that my EOF kids went to.
It’s a god damned crime. Every school should have textbooks, blackboards, and the basic teaching materials that teachers need. Kids like the ones I taught in EOF are getting screwed over every day by schools that simply do not have the materials that they need to teach them.
So, I’ve gone through the proposals for math classes in the NYC area, and selected a big list of proposals, ranging over pretty much every grade level. They’re mostly small proposals for basic supplies that every math class should have.
Our wonderful Seed overlords have donated a bunch of goodies, as have a variety of other organizations drafted by SBers. If you want to donate some money to any of the things proposed by any of the SBers, send a copy of your contribution confirmation email to sb.donorschoose.bonanza@gmail.com, and you’ll be entered into a drawing to get one of those.
Go throw a few bucks at donorschoose. The GM/BM challenge is here. You can find all of the SB challenges through Janet’s post here.
I’ll be throwing in a couple of hundred dollars worth of pledges this afternoon. Why not help, and go over now and give them some money?

Dembski and No Free Lunch with Competitive Agents (updated repost from blogger)

(Continuing in my series of updates of the GM/BM posts about the bad math of the IDists, I’m posting an update of my original critique of Dembski and his No Free Lunch nonsense. This post has more substantial changes than my last repost; based on the large numbers of comments I’ve gotten in the months since then, I’m addressing a bit more of the basics of how Dembski abuses NFL.)

It’s time to take a look at one of the most obnoxious duplicitous promoters of Bad Math, William Dembski. I have a deep revulsion for this character, because he’s actually a decent mathematician, but he’s devoted his skills to creating convincing mathematical arguments based on invalid premises. But he’s careful: he does his meticulous best to hide his assumptions under a flurry of mathematical jargon.

One of Dembski’s favorite arguments is based on the no free lunch theorems. In simple language, the NFL theorems say “Averaged over all fitness landscapes, no search function can perform better than a random walk”.

Let’s take a moment to consider what Dembski says NFL means when applied to evolution.

In Dembski’s framework, evolution is treated as a search algorithm. The search space is a graph. (This is graph in the discrete mathematics sense: a set of discrete nodes, with a finite number of edges to other nodes.) The nodes of the graph in this search space are outcomes of the search process at particular points in time; the edges exiting a node correspond to the possible changes that could be made to that node to produce a different outcome. To model the quality of a nodes outcome, we apply a fitness function, which produces a numeric value describing the fitness (quality) of the node.

The evolutionary search starts at some arbitrary node. It proceeds by looking at the edges exiting that node, and computes the fitness of their targets. Whichever edge produces the best result is selected, and the search algorithm progresses to that node, and then repeats the process.

How do you test how well a search process works? You select a fitness function which describes the desired outcome, and see how well the search process matches your assigned fitness. The quality of your search process is defined by the limit of the following:

  1. For all possible starting points in the graph:
    1. Run your search using your fitness metric for maxlength steps to reach an end point.
    2. Using the desired outcome fitness, compute the fitness of
      the end point

    3. Compute the ratio of your outcome to the the maximum result
      the desired outcome. This is the quality of your search for this length

So – what does NFL really say?

“Averaged over all fitness functions”: take every possible assignment of fitness values to nodes. For each one, compute the quality of its result. Take the average of the overall quality. This is the quality of the directed, or evolutionary, search.

“blind search”: blind search means instead of using a fitness function, at each step just pick an edge to traverse randomly.

So – NFL says that if you consider every possible assignment of fitness functions, you get the same result as if you didn’t use a fitness function at all.

At heart, this is a fancy tautology. The key is that “averaged over all fitness functions” bit. If you average over all fitness functions, then every node has the same fitness. So, in other words, if you consider a search in which you can’t tell the difference between different nodes, and a search in which you don’t look at the difference between different nodes, then you’ll get equivalently bad results.

Ok. So, let’s look at how Dembski responds to critiques of his NFL work. I’m going to focus on his paper Fitness Among Competitive Agents.

Now, in this paper, he’s responding to the idea that if you limit yourself to competitive fitness functions (loosely defined, that is, fitness functions where the majority of times that you compare two edges from a node, the target you select will be the one that is better according to the desired fitness function), then the result of running the search will, on average, be better than a random traversal.

Dembski’s response to this is to go into a long discussion of pairwise competitive functions. His focus is on the fact that a pairwise fitness function is not necessarily transitive. In his words (from page 2 of the PDF):

From the symmetry properties of this matrix, it is evident that just because one item happens to be pairwise superior to another does not mean that it is globally superior to the other. But that’s precisely the challenge of assigning fitness of competitive agents inasmuch as fitness is a global measure of adaptedness to an environment.

To provide such a global measure of adaptedness and thereby to overcome the intransitivities inherent in pairwise comparisons, fitness in competitive environments needs therefore to factor in average performance of agents as they compete across the board with other agents.

To translate that out of Dembski-speak: in pairwise competition, if A is better than B, and B is better than C, that doesn’t mean A is better than C. So, what you need to do to measure competitive fitness, you need to average the performance of your competitive agents over all possible competitions.

The example he uses for this is a chess tournament: if you create a fitness function for chess players from the results of a serious of tournaments, you can wind up with results like player A can consistently beat player B; B can consistently beat C, and C can consistently beat A.

That’s true. Competitive fitness functions can have that property. But it doesn’t actually matter: because that’s not what’s happening in an evolutionary process. He’s pulling the same old trick that he played in the non-competitive case: he’s averaging out the differences. In a given situation, a competitor does not have to beat every possible other fitness function. It does not have to be the best possible competitor in every possible situation. It just has to be good enough.

And to make matters worse for Dembski, in an evolutionary process, you aren’t limited to picking one “best” path. Evolution allows you to explore many paths at once, and the ones that meet the “good enough” criteria will survive. That’s what speciation is. In one situation, A is better, so it “wins”. Starting from the same point, but in a slightly different environment, B is better, so it wins. Both A and B win.

You’re still selecting a better result. The fact that you can’t always select one as best doesn’t matter. And it doesn’t change the fundamental outcome, which Dembski doesn’t really address, that in an evolutionary landscape, competitive fitness functions do produce a better result that random walks.

In my taxonomy of statistical errors, this is basically modifying the search space: he’s essentially arguing for properties of the search space that eliminate any advantage that can be gained by the nature of the evolutionary search algorithm. But his only argument for making those modifications have nothing to do with evolution: he’s carefully picking search spaces that have the properties he wants, even though they have fundamentally different properties from evolution.

It’s all hidden behind a lot of low-budget equations which are used to obfuscate things. (In “A Brief History of Time”, Steven Hawking said that his publisher told him that each equation in the book would cut the readership in half. Dembski appears to have taken that idea to heart, and throws in equations even when they aren’t needed, in order to try to prevent people from actually reading through the details of the paper where this error is hidden.)

The Problem with Irreducibly Complexity (revised post from blogger)

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:
minimal.jpg

  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 for φ. 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 φ. 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.