William Dembski, No Free Lunch: Why Specified Complexity Cannot Be Purchased Without Intelligence, Rowman & Littlefield, 2002. A review by Jeffrey Shallit, Department of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1. Ever since its inception, the theory of evolution has come under attack by creationists, who find its account of life's diversity threatening to their religious beliefs. Modern creationists have had essentially zero impact on science, but their political impact has been significant, especially in the United States. There they have managed to get evolution downplayed in biology curricula and disclaimers inserted in biology textbooks. Recently, a group of neo-creationists financed by the Discovery Institute, a conservative Seattle think tank, has attempted another approach to dismantle biological education: the so-called "Wedge Strategy". This strategy is based on an allegedly scientific approach called "intelligent design" (ID). Roughly speaking, advocates of ID wish to infer intelligent causes from complex phenomena. Since life is complex, ID proponents conclude it must have been designed by an intelligence. Many intelligent design advocates openly admit that this "intelligence" can be identified with the deity of Christianity (Maynard, 2001). ID proponents have received much media attention, although their scientific output, as measured by articles in peer-reviewed scientific journals, is non-existent (Gilchrist, 1997; Forrest, 2001). But as the Wedge Strategy document (Anonymous, 1998) makes clear, the real goal behind ID is not scientific, but political and religious. ID proponents wish to "defeat scientific materialism" and replace science with a new discipline that is "consonant with Christian and theistic convictions". Philosopher and mathematician William Dembski is one of the intellectual leaders of the ID movement. In The Design Inference (1998) he gave an account of his methodology from which one can supposedly infer design, but did not seriously address evolution, which can generate the appearance of design. Later, in Intelligent Design (1999), he began an attack on the theory of evolution and evolutionary algorithms that is continued in No Free Lunch, the book under review, whose title I abbreviate henceforth as NFL. Central to Dembski's argument is his concept of "specified complexity" or "complex specified information" (CSI). CSI is not Shannon information or Kolmogorov complexity, although both concepts are drawn on in NFL. Roughly speaking, an event exhibits CSI if it matches a pattern that is both improbable and describable with the background knowledge of an intelligent agent. Dembski contends that the presence of CSI is a reliable marker of intelligent design, and CSI cannot be generated by algorithms, chance, or any combination of them. He proposes a "Law of Conservation of Information", and argues that evolutionary algorithms cannot generate CSI, thus casting doubt on evolution's ability to account for the complexity in biological organisms. Has Dembski succeeded in making ID intellectually respectable? No. Let me not pull any punches: Dembski's No Free Lunch is a poorly written piece of propaganda and pseudomathematics. What, precisely, is wrong with NFL? A detailed list of problems would require dozens of pages, if not more: the recent critical review by Richard Wein (2002) weighs in at 37,000 words. In this review I restrict myself to six major themes: mathematical difficulties, grandiose claims, equivocation, poor writing, misrepresentation, and poor scholarship. 1. Mathematical difficulties. For an event to contain CSI, it must be improbable. But improbable with respect to which probability distribution? An event may appear very improbable with respect to one distribution while being significantly more probable with respect to another. Dembski wishes to infer design in the absence of a causal history---hence, in the absence of any historical basis for probability estimates---yet omits any detailed discussion of how, after observing an event, we decide what class of events it was drawn from. Furthermore, Dembski appears to use two different methods of evaluating the probability of an event. If a human being was involved in the event's production, he typically estimates its probability relative to a uniform probability hypothesis. For Dembski, a Shakespearean sonnet exhibits CSI because it would be unlikely to be produced by choosing several hundred letters uniformly at random from the alphabet. On the other hand, if no human being was involved, Dembski nearly always bases his probability calculations on the known causal history of the event in question. This flexibility in the choice of a distribution allows Dembski to conclude or reject design almost at whim. Another significant error occurs on pages 152--154 of NFL, where Dembski offers what appears to be a complete proof that deterministic functions cannot generate CSI. This proof is a crucial step justifying his "Law of the Conservation of Information" mentioned earlier. First, he assumes that j is an event containing CSI, i is another event, and f(i) = j for some function f. Next, he argues that "i constitutes specified information at least as complex as j". (Here the complexity of j is measured by -log_2 p, where p is the probability that a random event would match a chosen pattern to which j conforms.) Dembski's argument is full of the trappings of genuine mathematics: domains, subsets, inverse maps, and homomorphisms of boolean algebras; it looks convincing at first glance. There is no doubt that it really is intended to be a proof, because on page 154 he states "Bottom line: for functions to generate CSI they must employ preexisting CSI." But further down on that page we learn that the proof just presented was, in fact, not a proof at all. Dembski's reasoning "did not take seriously the possibility that functions might add information". Strange --- a reader might suppose this was ruled out by the argument just covered. But no! He apparently forgot that "the information in f must now itself be taken into account". (Exercise: exactly where in the argument on pages 152--154 does this omission occur?) To handle this, Dembski introduces an operator U such that if f(i) = j then U(i, f) = j and blithely states (p. 155) "Clearly, the information inherent in (i,f) is no less than that in j." But it is not so clear. For one thing, it is not "information" that is at stake here, but Dembski's CSI. It is certainly possible that both i and f could fail to be specified in Dembski's technical sense, while at the same time j is specified. For example, consider the case where i is an encoded English message and f is an unknown and obscure decryption function. If our background knowledge does not include f, we may recognize j = f(i) as matching a pattern while i and f do not. For another, Dembski's notion of information is a statistical one; it measures "information" through a rescaled form of probability. But what is the probability distribution corresponding to f? We are not told. It would certainly be possible at least in some cases, to invent a probability distribution for f and reason about it, but this crucial point is simply not addressed in sufficient detail. Dembski also overlooks the possibility that additional information can be accumulated simply by iterating f. If f is a length-increasing mapping on strings, this makes measuring the information content of f problematic, since choosing the correct associated probability distribution becomes more obscure. Dembski confuses things even further by stating "Note that in the case of algorithms U is a universal Turing machine". Does this mean that CSI could, in fact, be increased if f were noncomputable (in the theory of computation sense)? How, indeed, would the CSI of a noncomputable f even be defined? (Lest the reader think this is a fine technical point, let me observe that Pour-El and Zhong (1997) have shown that the unique solution of a certain wave equation with computable initial conditions is uncomputable.) None of this is explored. Omissions such as these cast serious doubt on Dembski's claims. 2. Grandiose claims. Dembski has a high opinion of his own work. He states (p. xii--xiii) that CSI "is increasingly coming to be regarded as a reliable empirical marker of purpose, intelligence and design", although to my knowledge Dembski's coined term "CSI" has not been adopted by any other probabilist or information theorist. Nor have any papers about CSI been published, either by Dembski or other researchers, in peer-reviewed mathematics or statistics journals. Nevertheless, he insists that specified complexity is the only way to detect design (p. 116). He also claims his "Law of Conservation of Information" has "profound implications for science" (p. 163). On occasions Dembski elevates mathematical trivialities to the level of profound insights. On page 166 he justifies a claim that "CSI is holistic" (that is, it cannot be accumulated through an iterative process) by calculating that the Shannon information of an English sentence exceeds the sum of the information contained in its individual words. But a careful examination of his argument shows the missing information is precisely that contained in the space characters between the words. 3. Equivocation. The fallacy of equivocation is to use the same term to mean two different things. For example, "Nothing is better than complete happiness. A ham sandwich is certainly better than nothing. Therefore, a ham sandwich is better than complete happiness." The conclusion follows only because of the equivocation about the meaning of "nothing". The equivocation fallacy is an integral part of the argument in NFL. For example, the word "specified" is a term of art for Dembski; it means something very precise and particular, involving a complicated interplay between functions, probability, rejection regions, and background knowledge. One can certainly argue that the definition is incoherent (as I do in Elsberry and Shallit (2002)), but that is not the point I wish to make here. The point is that according to Dembski's own rules as laid out in Section 2.5 of NFL, asserting that something is specified requires a detailed argument involving a probability calculation. It is not enough to simply assert it. But that is just what Dembski does when it comes to analyzing biological organisms. On page 289 he asserts, "At any rate, no biologist I know questions whether the functional systems that arise in biology are specified." Perhaps they don't. But the question is not, Do biologists call such systems specified?, but Are they specified in the precise technical sense demanded by Dembski? This is equivocation at its finest (or worst). Another example appears on page 213. There Dembski discusses the work of Thomas Schneider (2000), who provided an experimental model showing how Shannon information may increase in evolution. Dembski says, "As an example of smuggling in complex specified information that is purported to be generated for free, consider the work of Thomas Schneider." Considering that Schneider, like everyone else who works in information theory, has not made any reference to Dembski's CSI in his paper, this claim of "smuggling" is unwarranted. Dembski's equivocation fallacy comes from equating Shannon information --- a well-understood concept that has been used for fifty years in literally thousands of scientific papers --- with Dembski's own CSI, which has not. There are many other examples of equivocation in NFL. The reader may enjoy constructing a detailed list. 4. Poor writing. Even a book with bad ideas and poor reasoning may be enjoyable if the writing is good enough. (I have in mind almost anything by Wendell Berry.) But NFL does not possess even this saving grace. The book gives the impression of having been assembled haphazardly from previously published essays. Take the name choice in "complex specified information". As we have seen, Dembski takes "information" to mean -log_2 p, where p the probability of an event matching a chosen pattern. He calls the information "complex" if p is small. Dembski's use of "complex" has little to do with "complicated": for example, the record HHH ... H representing flipping 500 heads in a row constitutes "complex information" under his definition, even though the record of the event is very simple. To add further to the confusion, to be "specified" for Dembski means to conform to a pattern. He apparently modeled this after another theory of information, the theory of Kolmogorov complexity. But in the Kolmogorov theory, a string is called "complex", or said to possess "high information", if no simple way to specify it exists! Another term, such as Robin Collins' "specified improbability", would have been less confusing. Sometimes the poor writing takes the form of choosing strange notation, as in the formal statement of the "Law of Conservation of Information" on p. 160: I(A & B) = I(A) mod UCB . Here "mod" does not mean what every computer scientist or number theorist would expect: namely, "a mod b" as "the remainder upon division of a by b". No, the reader has to wait until the next page to find out that what Dembski really means is the inequality I(A & B) <= I(A) + UCB where UCB is 500. Then why not just say that, instead of bringing in the confusing term "mod"? Sometimes the form of the argument seems to be designed more to impress and confound, rather than convey meaning, as in the discussion of compact topological groups and Haar measures on page 105, or algebraic groups on page 201. This material is inessential to the main argument and could easily have been excised or summarized in a footnote. Similarly, the concept of "invariant" is trivial enough that I can explain it to my 7-year-old, but Dembski's discussion on page 274 is extravagant in its use of mathematical notation. Other times the impact of poor exposition is felt more deeply, as in the definition of CSI itself. Is CSI a quantity expressible in bits as implied on p. 160? Or does something either "exhibit" CSI or not exhibit it, as implied on p. 163? 5. Misrepresentation. I found several instances of misrepresentation in NFL. For example, on p. 211, Dembski dismisses the work of artificial life researcher Tom Ray as follows: Thomas Ray's Tierra simulation gave a similar result, showing how selection acting on replicators in a computational environment also tended toward simplicity rather than complexity --- unless parameters were set so that selection could favor larger sized organisms (complexity here corresponding to size). I have to wonder how carefully Dembski has read Ray's work, because this is not the conclusion I drew from reading Ray's papers. Curious, I wrote an e-mail message to Ray asking if he felt Dembski's quote was an accurate representation of his work. Ray (2002) replied as follows: "No. I would say that in my work, there is no strong prevailing trend towards either greater or lesser complexity. Rather, some lineages increase in complexity, and others decrease. Here, complexity does not correspond to size, but rather, the intricacy of the algorithm." A similar misrepresentation occurs in Dembski's selective quotation of Keith Devlin's review of Dembski's earlier book, The Design Inference. Dembski writes (NFL, p. 372) "Take for instance ... mathematician Keith Devlin's appreciative remarks about my work in his July/August 2000 article for The Sciences titled "Snake Eyes in the Garden of Eden": `Dembski's theory has made an important contribution to the theory of randomness --- if only by highlighting how hard it can be to differentiate the fingerprints of design from the whorls of chance'." But, as anyone reading Devlin's review in its entirety will realize, this line --- coming at the end of the review --- was an effort to mitigate previous harsh comments. For example, in the very same review Devlin observes that Dembski's work can be used to support two different conclusions: human life arose by a combination of chance and natural processes, and human life arose by design, and states: "But if Dembski's new mathematics, which he developed to help poke holes in the theory of evolution, can sustain two such contradictory conclusions, then it does not resolve the debate at all." When I informed Devlin that Dembski was quoting only one positive line of the review---as done in NFL, in a paper (Dembski, 2000), and a Diane Rehm radio interview (Dembski, 2001)---he labeled it misrepresentation and told me, "Anyone who read the entire article would realize I was negative about Dembski's thesis" (Devlin, 2002). Yet another misrepresentation occurs in Dembski's discussion of Dawkins' example of the power of selection, the famous Methinks it is like a weasel example. Dawkins (1987) starts with a randomly chosen string of 28 characters, and then breeds it by copying, together with a certain probability of random error. He, or rather, his computer, next evaluates a fitness function to find the string that most resembles the target string "Methinks it is like a weasel". All the less-fit strings die out, and the most-fit then goes on to breed again. After only a small number of generations (64 in Dawkins' example) the target is reached. Dembski discusses this example on pages 181--183 of NFL, but he gets it wrong. He insists that Dawkins' algorithm, instead of evaluating a fitness function, behaves as follows: it "randomly alter[s] all the letters and spaces in the current sequence that do not agree with the target sequence" and "whenever an alteration happens to match a corresponding letter in the target sequence, leave it and randomly alter only those remaining letters that still differ from the target sequence". But Dawkins said nothing of the sort. To add insult to injury, Dembski goes on in pp. 193--194 to propose an algorithm that he calls "slightly different but more realistic". It turns out that this supposed new algorithm is, in fact, much closer to Dawkins' original algorithm as described in The Blind Watchmaker. It is true that Dawkins did not provide many details about his implementation. But researchers other than Dembski seem to have no problem understanding Dawkins' algorithm. Discussions by both Bach (1993) and Jacob (2001) make it clear they understand that, in Dawkins' model, letters are not fixed once they match the target. Even minor details are subject to careless misrepresentation. For example, in Dembski's discussion of a certain sequence of bits corresponding to prime numbers that appears in the movie Contact, he says, (p. 9): "The SETI researcher who in the movie Contact discovered this sequence put it this way: `This isn't noise, this has structure.' " Dembski gets it wrong three ways. The discoverer of the prime sequence was Dr. Ellie Arroway (played by Jodie Foster). The character who remarked about structure wasn't Arroway, but Kent Clark (played by William Fichtner). The correct line in the movie is actually, "You know the interlaced frames that we thought were noise? This has structure. I'm hearing structure." And finally, this character wasn't commenting about the prime sequence at all! His comment is about another signal at a different frequency, which later proved to encode blueprints for a machine. These are just four of the misrepresentations in NFL. I could give several more, but by now I hope the reader gets the point. 6. Poor scholarship. For a book that purports to discuss fundamental questions about information, complexity, and biology, there is remarkably little discussion or awareness of previous work. Dembski does not cite any of the following works, just to list a few: - Kimura's paper where he shows how natural selection can increase Shannon information (Kimura, 1961); - Wicken's book on evolution and information (Wicken, 1987); - The papers of Saunders and Ho (Saunders and Ho, 1976; Saunders and Ho, 1981) that argue that complexity increases during evolution; - The paper of Nehaniv and Rhodes (1997) showing how, in a finite automaton model, complexity can evolve in biological systems. The field of artificial life evidently poses a significant challenge to Dembski's claims about the failure of evolutionary algorithms to generate complexity. Indeed, artificial life researchers regularly find their simulations of evolution producing the sorts of novelties and increased complexity that Dembski claims are impossible. Yet NFL's coverage of artificial life is limited to a few dismissive remarks, the longest of which I have already quoted above. Indeed, the term "artificial life" does not even appear in NFL's index. There is no reference to, for example, the work of Adami, Ofria, and Collier (2000) which suggests the possibility of increased complexity over time. As a scholarly work, Dembski's NFL falls dramatically short. I have covered six of the most significant problems with NFL. At least some of these problems could have been avoided had Dembski been more willing to test his claims through the peer-review process. But intelligent design advocates have consistently failed to publish their work in scientific journals (Gilchrist, 1997; Forrest, 2001). When pressed, some say this is because academia is a "closed shop", run by an "elite" that is biased against them. This claim is undermined by the fact that many non-mainstream and controversial views routinely get published in the scientific literature. Just recently, controversial claims of table-top fusion induced by the collapse of super-hot bubbles were published in a major scientific journal (Taleyarkhan, West, Cho, Lahey, Nigmatulin, and Block, 2002). What intelligent design advocates fail to realize is that the peer-review process could benefit them enormously, by identifying weak arguments and incorrect claims before they are published. For example, a thorough peer review might have revealed that a crucial calculation on p. 297 of NFL is off by a factor of about 10^65. The benefits of peer review are so obvious that I can only conclude that some ID advocates are not really interested in the advancement of science. Their goal is to replace science as it is currently done with a form of religion, and that in turn may have unintended consequences. In today's science it is not uncommon for Christians, Jews, Muslims, and atheists to work together without friction. But I doubt many Muslim, Jewish, or atheist scientists will want to cooperate with a movement that insists, as Dembski does in Intelligent Design, p. 210, that "Christ is indispensable to any scientific theory, even if its practitioners don't have a clue about him". One of science's most attractive aspects is the the way it transcends religious and political differences. Let's keep it that way. Acknowledgements. In the preparation of this review I am pleased to acknowledge extensive conversations with Wesley Elsberry and Richard Wein. I also thank William Dembski for his generosity in sending me a complimentary copy of No Free Lunch. References C. Adami, C. Ofria, and T. C. Collier (2000), Evolution of biological complexity, Proc. Nat. Acad. Sci. USA 97, 4463--4468. Anonymous (1998), The Wedge Strategy, http://www.antievolution.org/features/wedge.html E. Bach (1993), Timing the blind watchmaker: analysis of an evolution model of Richard Dawkins, UMAP Journal 14, 295--308. Richard Dawkins (1987), The Blind Watchmaker, W. W. Norton. William Dembski (1998), The Design Inference: Eliminating Chance Through Small Probabilities, Cambridge University Press. William Dembski (1999), Intelligent Design: The Bridge Between Science & Theology, InterVarsity Press. William Dembski (2000), "Intelligent design coming clean", Metaviews 098, November. Available at http://www.arn.org/docs/dembski/wd_idcomingclean.htm William Dembski (2001), interview on The Diane Rehm Show, April 18. Archive at http://www.wamu.org/dr/shows/drarc_010416.html Keith Devlin (2002), personal communication, February 26. Wesley Elsberry and Jeffrey Shallit (2002), Information theory, evolutionary computation, and Dembski's "complex specified information", submitted for publication. B. Forrest (2001), "The wedge at work: how intelligent design creationism is wedging its way into the cultural and academic mainstream", in R. T. Pennock, ed., Intelligent Design Creationism and Its Critics, MIT Press, pp. 5--53. G. W. Gilchrist (1997), The elusive scientific basis of intelligent design theory, Reports of the NCSE 17 (3) (May/June), 14--15. C. Jacob (2001), Illustrating Evolutionary Computation with Mathematica, Morgan Kaufmann, 2001. M. Kimura (1961), Natural selection as the process of accumulating genetic information in adaptive evolution, Genetical Research 2, 127--140. Steve Maynard (2001), "Life's intelligent design: Author of `Darwin on Trial' sees a win", Tacoma News Tribune, May 7. C. L. Nehaniv and J. L. Rhodes (1997), Krohn-Rhodes theory, hierarchies and evolution. In Mathematical Hierarchies and Biology, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 37, American Mathematical Society, 1997, pp. 29--42. M. B. Pour-El and N. Zhong (1997), The wave equation with computable initial data whose unique solution is nowhere computable, Math. Logic Quarterly 43, 499--509. T. Ray (2002), personal communication, January 30. P. T. Saunders and M. W. Ho (1976), On the increase in complexity in evolution, J. Theoretical Biology 63, 375--384. P. T. Saunders and M. W. Ho (1981), On the increase in complexity in evolution II. The relativity of complexity and the principle of minimum increase, J. Theoretical Biology 90, 515--530. T. D. Schneider (2000), Evolution of biological information, Nucleic Acids Res. 28, 2794--2799. R. P. Taleyarkhan, C. D. West, J. S. Cho, R. T. Lahey Jr., R. I. Nigmatulin, and R. C. Block (2002), Evidence for nuclear emissions during acoustic cavitation, Science 295, 1868--1873. Richard Wein (2002), Not a free lunch but a box of chocolates. Available at http://www.talkorigins.org/design/faqs/nfl/ J. S. Wicken (1987), Evolution, Thermodynamics, and Information, Oxford University Press. About the author. Jeffrey Shallit is a mathematician and computer scientist. He received his Ph. D. from the University of California, Berkeley in 1983, and has taught at the University of Chicago and Dartmouth College prior to his present position at the University of Waterloo. With Eric Bach, he is the author of Algorithmic Number Theory (MIT Press, 1996) and (with Jean-Paul Allouche) Automatic Sequences (Cambridge University Press, forthcoming).