Wednesday, October 17, 2007

On Being Twice a Square



The last time my age was twice a square, I got married.

The time before that, I became of legal age.

This time around, my wife Anna decorated a finite automaton cake to celebrate. I shared it with my 4th year class on formal languages and parsing.

Tuesday, October 09, 2007

If Only All Theists Were This Modest

I've always been impressed with my colleague David Seljak's honesty and forthrightness. He's a professor at St. Jerome's University, a Catholic "church college" affiliated with the University of Waterloo. He sent me the following comments by e-mail and graciously allowed me to post them here:


"Christians ought to remember that normal, thinking people do not automatically see the sense in their claims. Indeed believers ought to be a minority. Even Paul says in his letter to the Corinthians. "but we preach Christ crucified: ...foolishness to Gentiles". This stuff is supposed to sound crazy to you guys. After all, we Catholics believe that if we eat the flesh and blood of a Jewish zombie who died 2000 years ago, our invisible friend in the sky will save us from death. :) Faith does not come "naturally"; that is why we call it a "gift". We should hardly be surprised when a number of people say, "no thank you, that sounds ridiculous." It seems to me that Christians should be a lot more humble about our truth claims and a whole heckuva lot more charitable to people who don't take them up."


I daresay that if all Christians were this honest and humble, the conflict between theists and atheists would dry up.

Monday, October 01, 2007

Taner Edis visits Waterloo

Taner Edis, a professor of physics at Truman State University in Missouri, and the co-editor of the anthology Why Intelligent Design Fails? visited Waterloo briefly last Friday. He gave at talk at Wilfrid Laurier University, down the street from me, on "Science and Religion in Islam". This is a topic of his recent book, An Illusion of Harmony.

I've known of his work for quite a while, but had never heard him speak in person. Edis is noteworthy in part because of his Turkish roots, which give him some insight into the Muslim world's flirtation with pseudoscience and creationism. And he is an extremely fair writer, in the model of Ed Brayton, who always tries to understand the other side's position and summarize it accurately.

He started by pointing out that different sciences have converged, through separate paths, on naturalistic explanations for the world. ( If I may quote Stephen Weinberg, "religious skepticism is not a prejudice that governed science from the beginning, but a lesson that has been learned through centures of experience in the study of nature." ) These explanations cast doubt on the reality of supernatural beings.

Scientific materialism, therefore, is a threat to modern religious belief, although technology itself is attractive. There are two kinds of responses: try to show that science supports religious belief (say, by finding passages in the Koran that supposedly presage modern scientific developments) or argue that "true science" is compatible with religion.

While there are many Christian sects that support a young-earth creationist view, in Islam, the old-earth creationist view predominates. There is a strain of Islamic creationism that originated in Turkey but has become popular world-wide. As an example, Edis passed around a truly revolting tract by Harun Yahya entitled Fascism: The Bloody Ideology of Darwinism.

Edis discussed two science-related "urban legends" that are widely repeated in Islamic communities. One was that Jacques Cousteau became a Muslim after observing that there is a salinity barrier in the Mediterranean which is supposedly mentioned in the Koran.

Edis pointed out that Muslims who advance pseudoscience are not opposed to all science and technology. As an example, he cited the Nur movement, whose followers are very pro-technology.

Edis stated that Darwinian evolution, particular human evolution, is not widely accepted in Islam because a naturalistic process with random elements is unacceptable theologically. Islam differs from Christianity in that Christianity has a large number of moderate sects that view science as a separate domain, while Muslims typically see science as subordinate to the revelations of the Koran. Liberal Muslim views are much rarer than liberal Christian views.

Edis pointed out that Muslim countries are very weak in science, although applied science does better than basic research. Those who point out that creationism is pseudoscience are labeled as "secularist".

Altogether, I found Edis' talk to be informative and well-presented. I can't say as much, regrettably, for the questions that followed. I was startled at how incoherent some of the questions were, and some questioners didn't seem to listen carefully to his replies, apparently preferring to base their remarks on caricatures.

A Muslim woman who said she was a professor of chemistry at Wilfrid Laurier (probably this professor) made two statements. First, she said that, as a chemist, she saw no conflict between science and her religion, because Islam instructs its followers to be seekers after truth. Second, she disputed the title of the talk, saying that "Science and Religion in Islam" was misleading because the talk was not about the true Islam. In other words, she employed the "No True Scotsman" fallacy.

In reply, Edis correctly observed that chemistry enjoys a slightly different position than physics or biology. Some aspects of physics and biology (e.g., cosmology, evolution) provide explanations for the world that are significantly at odds with religious claims. Chemistry, however, seems to intrude less significantly into what has traditionally been perceived as religion's domain.

Edis rebutted her second statement by pointing out that, as a non-believer, for him there was no "true Islam", but only a variety of different Islams as practiced by different religious groups. He said it would be arrogant for him to pick one of these Islams and declare it as the true Islam; that was for believers to decide. His concern was to examine Islam as it was actually practiced.

Another Muslim questioner heard Edis' response about chemistry and didn't seem to grasp the distinction Edis was making, saying that he had dismissed chemistry as less important than biology or physics (something not even remotely implied by Edis' reply). The same questioner dismissed the theory of evolution as just one explanation among many.

It was an interesting afternoon, and I only wish I had had more time to discuss with Edis after the talk.

Students Want Me to Do Their Homework

I often get e-mail messages from students in other countries. They pose a problem to me and ask for its solution, and they usually include a note to the effect that this is for their "personal research".

Now, I don't want to be hard on the students. After all, maybe some of these requests are genuine. As a young student, I occasionally wrote to famous mathematicians (or people I thought were famous mathematicians) with questions, and I was often pleased to get a reply. I still treasure postcards and letters from people like D. H. Lehmer and Daniel Shanks. I would have been very hurt and insulted to get a note saying, "Don't ask me to do your homework for you", because my questions always derived from my own adolescent research.

Nevertheless, I'm often suspicious of these requests, because my guess is that most of them come from students who are too lazy to do their own homework problems, and want me to do them instead. E-mail has made it feasible for a student to receive a homework assignment, search the web for people working in that area, pose the problem to a professor, and get a result back, all in less than 24 hours -- in plenty of time to hand in for a homework assignment. That wasn't possible when communication was by postal letters. And there is definitely a different flavor between a genuine research problem (which I often receive from colleagues) and the kinds of questions these students ask.

So what to do? My solution is to respond that I am happy to answer these questions if the students ask the question again in a month. That way, if the question comes from a homework assignment, in a month the answer probably won't do the cheating student any good. If the question is genuine, and the poser really wants to know the solution, waiting a month won't hurt too much.

I throw it open to my audience: what other possible strategies are there for answering these kinds of queries?

Tuesday, September 25, 2007

The Discovery Institute's Latest Fellow, Mahmoud Ahmadenijad?

First, read this transcript of Iranian President Mahmoud Ahmadinejad's talk at Columbia University.

Now, ask yourself: wouldn't he be perfect as a Discovery Institute fellow?

The Discovery Institute wants to allow supernatural causation in science, "to reverse the stifling dominance of the materialist worldview, and to replace it with a science consonant with Christian and theistic convictions." (Wedge Document)

Ahmadinejad says "One of the main harms inflicted against science is to limit it to experimental and physical sciences..." and "... the material is just a shadow of supreme realities..."

The Discovery Institute wants us to "teach the controversy" about evolution. Ahmadinejad wants us to teach the controversy about the Holocaust: "...if, given that the Holocaust is a present reality of our time, a history that occurred, why is there not sufficient research that can approach the topic from different perspectives?"

I think the Discovery Institute should move quickly to hire him, before Ahmadenijad is offered a position at the Institute for Historical Review.

Sunday, September 23, 2007

FaithMB = (Ignorance) + (Intellectual Dishonesty)

Marvin Bittinger is a retired professor of mathematics education and author of many textbooks. From Pharyngula I learned about his new book, The Faith Equation: One Mathematician's Journey in Christianity.

The "Faith Equation", it turns out, is this: Faith = (Mind) + (Heart) + (Will).

Now, after you've stopped laughing, here is my revision of his equation:

FaithMB = (Ignorance) + (Intellectual Dishonesty)

Now I wouldn't be so arrogant as to claim that everyone's faith is based on the pillars of ignorance and intellectual dishonesty; I know a lot of skeptical, searching, intellectual Christians. Here the subscript "MB" on faith indicates that it only refers to the faith of one Marvin Bittinger.

Why do I say intellectual dishonesty? First, there's the matter of Biblical prophecies. Part of Bittinger's book deals with various prophecies in the Bible. He considers each one, evaluates its probability, and multiplies the probabilities together to get a very small number. He concludes the result shows that the fulfillment of these prophecies is a miracle. I'll point out that claims of Biblical prophecies that can be easily dispelled by reading TIm Callahan's book, Bible Prophecy: Failure or Fulfillment?, but that's not my main point. No, the main point is Bittinger's claim here that "the Bible contains hundreds if not thousands of prophecies which have come true, with none failing".

None failing? How about the prophecy in Matthew 24, where Jesus lists a number of coming events, such as "sign of the Son of man in heaven" and "angels with a great sound of a trumpet", etc., etc. and then says "This generation shall not pass, till all these things be fulfilled." Well, it's 2000 years later, and none of these things have happened.

The second example comes here, where Bittinger claims "Whether the earth is 10-15 billion years old (old-earth opinion) or 5-6 thousand years old (young-earth opinion) is subject to debate in scientific and theological circles". Here Bittinger shows his ignorance, because nobody claims the earth is 10-15 billion years old. The current best estimate for the age of the earth is about 4.5 billion years, and this is based on multiple lines of evidence.

The intellectual dishonesty comes in because it is not true to say that the age of the earth is "subject to debate in scientific ... circles". There is simply no debate. The evidence for the 4.5 billion year age is so strong, and the evidence against is so weak, that the question simply does not come up any more.

Another example: on page 49, Bittinger claims, "Our nation was founded on the motto 'In God We Trust'". That will certainly be news to historians, who will point out that (a) the Constitution is a secular document that doesn't mention "God" and (b) the unconstitutional motto "In God We Trust" was only approved in 1864, long after the US was founded.

The really depressing thing is that this combination of ignorance and intellectual dishonesty is the norm in Christian apologetic circles. As evangelical Mark Noll once wrote, "The scandal of the evangelical mind is that there is not much of an evangelical mind." Too bad Marvin Bittinger did not heed his warning.

Saturday, September 22, 2007

By Jove, I Think He Doesn't Get It: A Night with Professor Higgins

Michael Higgins is a Catholic religious scholar, author, and local legend who is currently President of St. Thomas University in Fredericton, New Brunswick. Last night he delivered the inaugural Michael Higgins Lecture at St. Jerome's University, a church college affiliated with my own university, the University of Waterloo. The title was, "It's Tough Being God These Days", and the main theme was the new atheism.

A night with Prof. Higgins is always entertaining, as he is a witty and erudite speaker. At one point, speaking of atheists, he said, "We used to burn them", which got a good laugh. Despite his wit and erudition, I have always found Higgins' talks unsatisfying. To me, a Higgins talk is best likened to eating at an overrated Parisian restaurant. You are taken with the setting and the opulence and the view of Notre Dame. But then the food comes, and you are disappointed to discover that most of the effort has been expended on the surroundings, and little on the meal itself.

Last night was no exception. There was a bit of chest-pounding against atheism and the usual suspects of Dawkins, Hitchens, and Dennett, a rather dispirited defense of religion and an acknowledgment of some religious sins, a brief theological analysis concluding that "God is big", and a limp finish that consisted of quoting some of his favorite religious writers. I left hoping for more.

Unlike some Catholic commentators, Higgins takes the current wave of atheism seriously. He views it as a significant trend, labeling it a "virulent and subcompetent atheism" that is "seismic in its implications". However, he thinks the arguments are nothing new: "everything originated in the 18th and 19th centuries". He denigrates the "industry" of atheist writers such as Dawkins, Hitchens, and Dennett, arguing that their books are "aggressive and vituperative". Their hubris is "stunning". They ridicule "without fear that it is indecorous or unjust".

Higgins is very impressed by John Cornwell, who wrote a reply to Dawkins. He quoted Cornwell as saying that in the past, atheists were content to dispute the arguments of believers, but the current wave of atheists likes to ridicule the believers themselves. (But listen to this interview with Cornwell and Dawkins, where Cornwell is caught blatantly misrepresenting what Dawkins had to say.)

To his credit, Higgins says that religion is partly to blame. The new wave of antipathy is, he admits, "religion's own fault". He cites religion's "capacity for terror" and cites as an example "honor killings". "Religion's capacity to divide is considerable," Higgins concedes.

But it's too easy, Higgins says, to blame the excesses of religion on religion. Honor killlings do not represent religion, but terror. "No holy man" could ever claim terrorist acts as "a life-giving force". The issue, Higgins argued, is not to eliminate religion, but to eliminate the caricature of religion, to delegitimize those who speak on behalf of religion but do so inauthentically.

Atheists have the spotlight now, Higgins says, and so the media interprets religious stories in that light. The recent revelations about Mother Teresa were not interpreted according to the "theology of God's absence", but rather that she was a hypocrite or worse.

Luckily, he observed, theists outreproduce atheists, so there is little danger. The answer to the new atheism is not in "noble silence". "God is bigger than our systems" and "Once we recognize God's bigness we recognize our own fanaticism". There must be "respect between people of faith" and "Catholicism can lead".

Now, my analysis. Higgins claimed that those who attack religion are ignorant of it. He even went so far as to suggest, in answer to a question, that Hitchens was mentally unbalanced. I have a two-word answer: courtier's reply.

Higgins says that the new atheism engages in a "caricature" of genuine religion. My reply: look around you. We have a local Catholic school board actually debating whether to give the HPV vaccine to girls, not because of the cost or the unproven nature of the vaccine, but because it might encourage them to engage in sexual activity. We have Muslims rioting and killing in Pakistan because of a rumor that a Christian had desecrated the Koran, all the while insisting that Islam is a peaceful religion. We have Mother Teresa working with poor and sick people, while refusing to endorse the birth control that might genuinely help them. We have Jerry Falwell blaming 9/11 on "pagans, and the abortionists, and the feminists, and the gays and the lesbians". It's not possible to caricature religion because, these days, religion caricatures itself.

I'm sure that Higgins would reply with a version of the "No True Scotsman" fallacy, because that's what he did in his talk. These kinds of actions, Higgins would say, are not genuine religion. I say, they represent genuine religion for millions of believers, and they find their justification in the holy texts themselves. Look at Kirk Durston, a local religious leader who excuses genocide in the Bible when God does it. Look at Muslims who draw their inspiration for violence from passages in the Koran such as “Believers, make war on the infidels who dwell around you. Deal harshly with them.”

I'm not saying all religious believers are of this stripe; far from it. But religion has been treated with kid gloves far too long. Higgins decried the treatment of religion in the media, calling it shallow. But when did you ever see a believer quizzed in the pages of your local newspaper about whether their beliefs are supported by evidence? Or if their beliefs are genuinely beneficial to society? In my local newspaper, faith is always treated as a positive aspect to one's personality. I see skepticism, not faith, as more worthy of respect. "There lives more faith in honest doubt, Believe me, than in half the creeds."

There was time for a few questions, and here's the one I asked. I asked why is it, when theists want to attack atheism or science, they often use religious language to do so? As examples I cited this article by a theist who suggested that evolutionary biologists answer criticism of evolution with "Darwin said it, I believe it, and that settles it," which is evidently a reference to the famous bumper sticker with "Jesus" replacing "Darwin". I pointed out that Prof. Higgins himself used this language, when he favorably cited another writer as referring to "evangelical atheists". In reply, Higgins first took exception to my use of the word "theist". (Hey, I was just trying to be inclusive; what word woud he have me use?) Then he denied that this tactic was frequently used. I find it hard to take his answer seriously, as there are many more examples. To cite just one, fellow Catholic writer Denyse O'Leary refers to the new atheism as an "anti-God crusade". Not only do theists use this religious language in attacking atheists, they use religious language that recalls the worst aspects of religion.

In the end, I don't think that Professor Higgins gets it. The new atheists have been emboldened by religion's excesses, but they don't base their arguments on that alone. Fundamentally, the new atheists are simply not convinced by religion's claims. When we hear Higgins assert that "God is bigger than our systems", we want to know, where's the evidence that what you are talking about even exists? We don't see God-talk as helpful in resolving issues; when God-talk is introduced, it moves us away, rather than towards, a solution based on rational consideration of the issues. Higgins wants to appropriate human values, such as compassion and tolerance, to religion's domain, but these values are subscribed to by theist and non-theist alike. In the end, religion doesn't have as many virtues as Higgins claims, nor does the new atheism have as many faults as he would have us believe.

Friday, September 21, 2007

Funding Ontario Religious Schools, Revisited

For comedy, there's nothing better than the protestations of the principals of local religious schools, as they try to assure us that, should they get provincial funding, they'll really be no different from other provincial schools. Previously, I pointed out that Bob Moore, principal of Guelph's John Calvin Christian School, doesn't seem to know what the word "evolution" refers to. He apparently thinks it has something to do with "origins of the universe".

Now, in the September 12 issue of the Kitchener-Waterloo Record, principal Julius de Jager of the Cambridge Christian School is the next to demonstrate significant confusion. He states that the Ontario curriculum document "does not require a teacher to teach as fact the Darwinian theory of adaptation". The poor muddled fellow can't even bring himself to use the word "evolution", it seems.

Next, de Jager adds, "Nor does it [the curriculum document] preclude a possible explanation that God created an amazing diversity in plant and animal life." Oh, right. That really sounds like science.

Guys, if you're trying to convince us that religious schools should get funded, you're doing a pretty bad job.

Thursday, September 20, 2007

Objective Journalism

The current wave of interest in atheism, fueled by religion's excesses, really does represent something new. For proof, consider the photo below, sent to me by a colleague, from an independent bookstore he recently visited:



This kind of display would have been simply unimaginable at any other time in the history of North America.

And today, Representative Pete Stark (D-CA) will give his first speech after coming out as a non-theist. Again, I can't imagine any congressman having the guts to admit this in the past 50 years. (Maybe in the age of Ingersoll, but not recently.)

To any reasonable observer, these kinds of events do signal some kind of sea change in opinion.

But then, "journalist" Denyse O'Leary isn't a reasonable observer.

My parents were journalists, so I learned something about the proper practice of that craft from them. All journalists have biases, but good journalists learn to recognize them, so they don't say remarkably stupid things like, "the [atheist] crusade exudes an unmistakable air of desperation". Good journalists actually interview people who disagree with them, and summarize their views fairly.

Ahh, but fairness and objectivity mean nothing when God's on your side.

It's All About the Science, Right?

These intelligent design advocates crack me up sometimes. While the leaders furiously insist that 'it's all about the science', the grass roots behind them are constantly giving away the store.

Check out this barely literate solicitation from the elders at Trinity Baptist Church in Norman, Oklahoma, where they are trying to raise funds to bring William Dembski to speak at OU. Could the religious motivation be more clear?

"Our prayer for this entire effort is for God to open doors so the power of His gospel would be made known to groups of people who need to hear the truth."

This group is so intellectually bankrupt that they don't seem to care whether or not Dembski's claims are true -- they only want to use him as an evangelical tool. (And if they really needed $10,000 for the event, they might wind up financially bankrupt, too!)

I want people to understand and accept the theory of evolution because it's true, because it makes a nontrivial statement about the world we live in, because it's essential to understanding HIV, drug-resistant tuberculosis, and other important public issues, because it offers deep insights into why we behave the way we do, but not because it will 'lead people to atheism'. I'd much rather have scientifically-knowledgeable theist neighbors than ignorant atheist ones.

Wednesday, September 19, 2007

That's a Nice Rack!



Here's a moose with a great rack of antlers. Photo courtesy my graduate student Dalia Krieger, who snapped this on a recent backpacking trip in eastern Canada.

How Do You Read Recursivity?

If you'd like to receive Recursivity via a news feed, then try these links:

http://recursed.blogspot.com/feeds/posts/default?alt=rss

http://feeds.feedburner.com/Recursivity

and let me know how they work for you.

Tuesday, September 18, 2007

David Warren's Ignorance

David Warren continues to display that special blend of arrogance and ignorance that could be named after him, if Michael Egnor hadn't already been eponymized.

In this column he writes:

It is because Darwinism has embedded itself so deeply into the assumptions of our age, that it must be attacked frontally. For Darwinian assumptions cloud our view of reality. They subvert our grasp of moral issues. They make it possible for people to be dismissive, not only of art, philosophy, and religion, but of the requirements and limitations of true scientific research. They eviscerate the human spirit, by insisting that, in the last analysis, everything is random and meaningless. Conversely, they justify true fascism (“survival of the fittest”), and all the horrors of eugenics, abortions and euthanasia.

Moral relativism could not stand, except on a Darwinist base, and reason itself is rendered defenceless, by the notion that all nature was randomly contrived.


I don't know why theists like Warren continually trot this nonsense out. Darwinian evolution is a scientific theory about evolution that explains the diversity of life as we see it today. If it has implications that are depressing or repugnant to Warren, then too bad. As paleontologist George Gaylord Simpon wrote, If a sect does officially insist that its structure of belief demands that evolution be false, then no compromise is possible. An honest and competent biology teacher can only conclude that the sect's beliefs are wrong and that its religion is a false one.

Warren claims "Darwinian assumptions ... subvert our grasp of moral issues". He is foolish and mistaken in two ways. First, Darwin's theory is not an assumption, but a conclusion, based on hard research by hundreds of biologists, theist and non-theist alike. Second, Warren apparently knows nothing at all about current work on the evolutionary origins of ethics. I happen to think that Richard Alexander's book, Darwinism and Human Affairs, is one of the deepest and most profound works ever written on morals. If Warren has read it, I'll eat my hat.

Evolution says nothing like "everything is random and meaningless". Randomness plays a part in evolution, but it isn't the whole story. Randomness is represented by mutations and accidents, but selection -- a decidedly non-random process -- is also essential.

Warren confuses the descriptive nature of "survival of the fittest" with a prescription: this is how we ought to behave. But of course, he knows so little about evolution that he doesn't understand that co-operation is not ruled out by evolution, but rather is a result of it; see, for example, The Evolution of Cooperation.

Warren is the perfect blowhard. Supremely confident in his assertions, and demonstrating his supreme ignorance at the same time. Why the Ottawa Citizen continues to employ him is a mystery.

Monday, September 17, 2007

On Design

Well, since Michael Egnor has sort of answered my questions, it's time for me to try to answer his. I'll try to be less evasive than he was.

One thing I'd like to point out is that Egnor seems to be under the misapprehension that the information theory that mathematicians and computer scientists actually study has something to do with inferring design.* This is simply not the case. Open up, for example, the book on Kolmogorov complexity by my colleague Ming Li, and you won't find a word about inferring design. (It's ID advocate Bill Dembski, of course, who is largely responsible for this confusion.) So, contrary to what Egnor thinks, as a mathematician and computer scientist I have no particular expertise on the general topic of "inferring design". It's just not something we do; maybe he should ask a SETI researcher, or a forensic investigator. But then again, Egnor has no particular expertise on the topic, either.

First, some general remarks about "design". I'll start by saying that I don't know exactly what he means by "designed". One of the favorite games of ID advocates is equivocation, so it's important to pin them down on a precise meaning. ID advocates rarely say plainly what they mean by "design". Do they mean simply that something has a pattern to it (as in "the design of a snowflake"), or do they mean something that has a "function", or must there necessarily be some teleology involved? I think it's incumbent on ID advocates to make clear what they mean. But I'll look at all three possibilities.

If ID advocates intend the first meaning ("pattern"), then the answer is clear: design need not imply a designer. The world is full of patterns that arise from the constrained nature of the physical universe. We can explain the overall pattern in a snowflake, for example, by referring to the symmetry in a water molecule in ice combined with the homogeneity of conditions as the snowflake forms. We don't normally bring in supernatural beings to explain snowflakes.

ID advocates, such as Bill Dembski, have nevertheless tried to rescue this hopeless case by bringing in probability. Dembski has argued that if an observed event fits a pattern, and the probability of this fit is extremely small, then the event must be due to design by an intelligent being. But as Wesley Elsberry and I have shown, his claim is based on incorrect mathematics combined with specious arguments. Dembski likes to say something on the order of 'witnessing specified events of low probability implicates design'. But the correct claim is merely 'specified events of low probability are never witnessed at all; if they are, that is prima facie evidence that your probability estimates are wildly off'.

Here's an example: there's a fellow with a web page who claims to have witnessed at least three independent meteorite falls. (The pictures he shows aren't meteorites, but let's ignore that for a moment.)

Now this page suggests that the probability of witnessing a meteorite land near you during your lifetime is about 1 in 2.5 million. So if the events are independent, we conclude that the probability of a particular person witnessing 3 meteorite falls in their lifetime is about 1 in 16 million million million. Even taking into account the total population of the world, this fellow's claim seems extremely unlikely. Could it have happened? Yes, but if so, we would have to consider some other possibilities: maybe the distribution of meteorite falls is extremely uneven, so that many more meteorites fall at this fellow's location than others. Maybe somebody's having him on, shooting meteorites out of a cannon towards his house. Maybe there's some other explanation entirely. In either case it's not that a specified event of low probability was witnessed; it was that our probability estimates were wrong. Dembski says design must be inferred when all other explanations are ruled out, but if my analysis is followed, inference to design no longer has the privileged place that Dembski accords it.

The second possible meaning of "design" corresponds to the inferred function of some object; this is basically the old argument of William Paley involving the watch found on the heath. While this argument may have been convincing two hundred years ago, it's convincing no longer, for the obvious reason that we know that evolutionary processes can produce function. We have good experimental evidence of this from novel mutations that, for example, allow some bacteria to digest nylon byproducts. As a computer scientist, I must also cite the artificial life experiments of Karl Sims, who showed how nontrivial and novel behaviors could evolve through mutation and selection -- something Dembski claims is impossible. Dembski has never addressed Sims' work.

The third possible meaning of "design" involves teleology; we infer a designer when we see something designed for a purpose. But either this begs the question, or it reduces to the previous paragraph about "function". So in all three cases, I don't think that seeing "design" implies a "designer".

ID advocates are always accusing others of 'wanting to eliminate the design inference from science'. Of course, this is pure nonsense. Archaeologists, for example, routinely attempt to deduce the roles that various objects played in the lives of the cultures they study. But, as Elsberry and Wilkins point out in their article from Biology and Philosophy, there is a huge difference between inferring design based on artifacts for which we have a causal story like human construction, and inferring design based on some causal story lacking any details whatsoever. They refer to this latter attempt, commonly used by ID advocates, as "rarefied design", and characterize it as "based on an inference from ignorance, both of the possible causes of regularities [that might explain the event] and of the nature of the designer."

One more point: I don't think that the question "is it designed?", in the absence of any candidate for a designer, is particularly interesting. That is, in the absence of motive, I don't think that knowing that something is designed tells you anything at all. I can do no better than to quote from Elsberry and Wilkins, who say

The problem with a simple conclusion that something is designed, is its lack of informativeness. If you tell me that skirnobs are designed but nothing else about them, then how much do I actually know about skirnobs? Of a single skirnob, what can I say? Unless I already know a fair bit about the aims and intentions of skirnob designers, nothing is added to my knowledge of skirnobs by saying that it is designed. I do not know if a skirnob is a good skirnob, fulfilling the design criteria for skirnobs, or not. I do not know how typical that skirnob is of skirnobs in general, or what any of the properties of skirnobs are. I may as well say that skirnobs are "gzorply muffnordled", for all it tells me. But if I know the nature of the designer, or of the class of things the designer is a member of, then I know something about skirnobs, and I can make some inductive generalizations to the properties of other skirnobs.

Now to Egnor's question. He wants to know why SETI is different from deducing design in biological systems. Referring to the fictional movie, Contact, where scientists received a blueprint for constructing a mechanical device, he asks, "If the scientific discovery of a ‘blueprint’ would justify the design inference, then why is it unreasonable to infer that the genetic code was designed?"

The answer is that I don't think that these situations are at all comparable. In the case of SETI, the fact that we are receiving a narrow-band signal is already suggestive, since we don't currently know any simple physical process that could produce these signals. This isn't a definite conclusion, though, because we have no idea what the probability of intelligent beings is, and we can't rule out narrow-band signals arising from some other physical process we simply don't know about.

In SETI, we are specifically looking for intelligent beings. These beings presumably live in another part of our universe, and presumably they evolved through natural processes, in much the way we did. This being the case, we hypothesize that, like us, these beings are interested in contacting other intelligent life, and would do so through radio waves. All these are assumptions based on our characterization of the "personality", if you will, of the originators of the signals. If any of these guesses are wrong, or if we are alone, we won't succeed. Our argument is based on analogy with our own thought processes, not "specified complexity" or other ID nonsense.

ID advocates, however, rule out any deductions based on the identity of the Designer. Yet, in real science, questions about intention and identity arise all the time in archaeology. To give just one example: in the 1890's, historian Arthur Evans heard of mysterious seal-stones from Crete. The identity of their creators, as well as the script used, was then unknown. Evans went on to identify the stones as the product of a civilization now called Minoan, and eventually one of the scripts, Linear B, was deciphered. The fact that ID advocates refuse to consider the really interesting scientific questions "who designed it?" and "why did they design it?" shows that they're not doing science.

To say that SETI is like the genetic code means that we have to hypothesize some designer who designed something for some reason. But where's the designer? In SETI, we can pinpoint a place in the universe where the signals are originating from. If the signals encode a machine, we can reasonably deduce that the intention is that we are to build it. But in the genetic code, who is the hypothesized designer? Where did they originate? When did they carry out their design? What is the intention of the design? All the really interesting questions are ruled as 'out of bounds' by ID advocates. Until they really come to grips with these questions, they're doing religion, not science.

As an example of something I'd find convincing, if we were to find a crashed spaceship with plans showing how to build a bacterium, and scientists carried out these plans and found that they really did construct life, then I'd find this very strong evidence that life on earth was designed.

Another point of disanalogy is that we know that DNA changes and evolves through time by processes such as mutation, gene duplication, and selection. There are even some very tentative answers to how the genetic code evolved. So the alternative hawked by ID advocates, that 'somebody made this sometime for some purpose, but we don't know where, when, or how', is not very impressive. In exactly the same way, a theory that lightning is 'caused by some intelligent being, but we don't know exactly how or why' is not very impressive, either.

Finally, DNA doesn't carry any of the hallmarks of human design, the kind of design we are most familiar with. Genes, for example, are often pleiotropic; they have multiple interacting effects. Human design, on the other hand tends to separate systems so they don't interact. Human activities tend to produce texts that are quite compressible; but a typical genome is hardly compressible at all. Biological entities reproduce themselves, but few, if any, human designs have this property. When we consider an analogy, like the one Egnor proposes, to be fair, we have to consider points of disanalogy, too. (For more examples of disanalogy, see Mark Isaak's article in Reports of the NCSE, Volume 23, no. 5-6.)

Let's alter the Contact story. Suppose the signal didn't encode a machine, but rather a sequence of DNA bases S. When we create DNA corresponding to this sequence, and stick it in a cell, we get an organism that tells us all about life on some other planet. Now the analogy is even closer than before; yet I think it is clear that our inference about the origin of S is still different from any inference about our own DNA. Indeed, it is entirely reasonable and scientific to infer that S is designed by intelligent beings on another planet, but our own DNA evolved.

Finally, on an unrelated note, Egnor takes me to task for my lack of civility. This is pretty rich, considering that Egnor's buddies at the Discovery Institute routinely insult the appearance of scientists, call them dishonest, and play games such as adding fart noises to Judge Jones' Dover decision. I say, clean your own stable first. Scientists are angry at the constant misrepresentation and juvenile antics of ID advocates, and we're not going to take it any more.

* Addendum: Because ID advocates have a track record of misunderstanding even the most trivial point, I should add that of course information theory could be used to separate, for example, human-generated text from noise. As I already mentioned, natural language text is quite compressible, while noise would probably not be compressible. But here we are not detecting design per se as some abstract category; rather we are using an empirical distinction between two things we have observed: natural language text, and noise.

Sunday, September 16, 2007

Towards a Canadian Republic

Good news for people who find the loyalty oath to the Queen --- a requirement for becoming a Canadian citizen --- to be an embarrassing anachronism inconsistent with Canada's devotion to "freedom of thought, opinion, and expression". Charles Roach and his group, Citizens for a Canadian Republic, are back in the game, thanks to a judge's dismissal of a shameful motion by Canada's Attorney General to prevent the suit.

Should Discovery Institute Spokesmen Be Charged with This Offense?

Excessive mooing.

Saturday, September 15, 2007

José González does Dawkins

I don't watch TV, but even I know about this amazing Sony ad featuring the music of José González and 250,000 bouncing colored balls:



González is a Swedish musician, and the song in the ad is "Heartbeats", a cover of a song from a group called "The Knife".

Now he has a new album out, and guess what? It's based, at least in part, on Richard Dawkins.

I know what I want for my birthday!

Friday, September 14, 2007

More Egnorance

Well, I see Michael Egnor is at it again.

He calls my my response "odd". Apparently, where Dr. Egnor comes from, it is considered "odd" to object when someone manufactures fake quotes and attributes them to you. No apology from Dr. Egnor is forthcoming, however.

Dr. Egnor says nothing at all about the fact that both he and Tom Bethell think that SETI researchers look for prime numbers to detect intelligence, when in fact SETI's own website approvingly quotes Louis Narens explaining why this might not be a good idea. (Thanks to Eric for pointing this out.) Apparently, where Dr. Egnor comes from, it is considered bad form to retract phony claims.

Dr. Egnor says nothing at all about his friend Tom Bethell's support for crackpot views on AIDS. Apparently, where Dr. Egnor comes from, if you discourage efficacious treatment for a life-threatening disease, that's just fine. He's in good company: other prominent creationists, such as Phillip Johnson, maintain the same views. Here's an issue where a word from Egnor, a medical doctor, could really have an impact. The silence from Dr. Egnor is deafening.

No, what really gets Dr. Egnor all worked up is the fact that I didn't answer his question (although the answers in the responses at the Panda's Thumb seemed pretty good to me).

In the meantime, I sent the following question to Dr. Egnor by e-mail:


Dear Prof. Egnor:

I wonder if you see any irony in the fact that, while intelligent design proponents are complaining about the suppression of their views and the unwillingness of scientists to debate, you attack me from a weblog that does not allow comments, while the Panda's Thumb and Recursivity are open to comments from everyone ... including you.

Regards, Jeffrey Shallit

P. S. Is it your general practice to steal copyrighted photos from people's websites without asking their permission?


So I'll make you a deal, Prof. Egnor: you answer my questions, and I'll answer yours. You first.

P. S. If you're going to cite me, Prof. Egnor, please spell my name correctly. Thanks.

Tuesday, September 11, 2007

Aww. Michael Egnor Notices Me

Well, I see that physician and Discovery Institute shill Michael Egnor has noticed me.

Egnor, a man whose arrogance and ignorance has already led to the coining of a new word, is unhappy about my critique of Tom Bethell. So unhappy, in fact, that he has to resort to forging fake quotes from my article.

Egnor claims that I called Bethell "a liar" - he uses those two words, and puts them in quotes. Any reasonable person would come to the conclusion that they appear in my article. Only problem is, the word "liar" doesn't appear anywhere in my piece, as a text search will easily confirm. Gee, a Discovery Institute spokesman misleading the public - what is the world coming to?

What I said was, "Bethell then goes on to repeat a common lie of the intelligent design movement..." Repeating a lie doesn't necessarily make one a liar; it is possible to repeat a lie from sheer ignorance.

Next, Egnor misrepresents the thrust of my observation about SETI. Egnor says, "Professor Shallit ridicules Bethell’s observation that Search for Extraterrestrial Intelligence (S.E.T.I.) research demonstrates that, under appropriate circumstances, the scientific inference to intelligent design in nature can be a legitimate interpretation of data." Actually, I did nothing of the sort. If we were to receive a coded message from outer space reading "Welcome earthlings! We are your reptilian overlords. Submit or be absorbed!", I would gladly join the hordes defending our beloved planet from invaders.

What I actually was objecting to - and it would be clear to anyone with connected brain cells - was Bethell's false claim that the people at SETI carry out their objectives by looking for "such things as a sequence of prime numbers". They don't look for prime numbers at all, as I showed by quoting directly from the SETI web pages.

Egnor makes the false claim that Bethell was just using an example from the fictional movie Contact. Although prime numbers do appear in Contact, Bethell said nothing at all about that movie, as a simple text search of Bethell's article will show. Bethell's claim was about what SETI researchers actually do; his claim was incorrect, and Egnor still doesn't understand why.

I find it strange that Egnor, a medical doctor, would defend Bethell, a man whose command of science is so unhinged that he has problems with relativity and thinks there is no AIDS epidemic in Africa.

Addendum: there's also a delicious irony involved in Egnor's post. The DI and intelligent design proponents are always whining about how legitimate scientists want to shut down debate about ID. Egnor's post, however, is on a web log that doesn't allow comments. The Panda's Thumb and Recursivity, by contrast, permit and encourage comments. Who, really, wants debate?

Sunday, September 09, 2007

Bethell the Buffoon

Check out the final exchange about intelligent design between John Derbyshire and Tom Bethell, where Bethell insists that creationism and intelligent design are as different as chalk and cheese. (Part 1 here; Part 2 here.)

In it, Bethell demonstrates once again why he is a blathering buffoon. Bethell tells us that "Structures or signals of specified complexity permit an inference to design without any necessary recourse to the supernatural" without bothering to mention that "specified complexity" is junk mathematics and doesn't permit an inference to anything at all, except that Bethell is rather gullible to accept William Dembski's assurances as gospel.

Bethell then goes on to repeat a common lie of the intelligent design movement: that the SETI Project (Search for Extraterrestrial Life) spends its time looking for "such things as a sequence of prime numbers". Sorry, Tom, that was the movie "Contact". You know, fiction?

In real life, SETI researchers look for look for narrow-band signals, because such signals don't appear to originate from simple systems, and because we believe intelligent beings, if they exist, would use a method of communication similar to ours. Repeat after me: SETI detection doesn't use prime numbers, "specified complexity", or red herrings. Bethell claims he's actually visited the SETI project, so how come he doesn't know this? Is it dishonesty, or simple stupidity?

Next, Bethell shows a profound misunderstanding of information theory when he claims, "Francis Crick, the co-discoverer of the structure of DNA was asked how the all-important coding information found its way into the DNA in the first place. It's so complex that a reliance on random events will never get us there." Bethell apparently doesn't understand that in the Kolmogorov theory of information, complexity is the same as randomness. It's easy to get complexity; all you need is a source of random events.

Here's a funny one: early on, Bethell solemnly intones that "Science is not properly based on authority, however." Later, however, in discussing the RNA world hypothesis, he says, "But I'm told that the alternative, the "RNA world," has huge complexities of its own. It's all pure guesswork." Oh. So he's been told that the RNA world hypothesis has problems, and he apparently accepts that without even looking into it. But I thought science wasn't based on authority? Mr. Bethell, meet your opponent, Mr. Bethell.

Mr. Bethell needs a good closer, so to finish up he reaches deep into the creationist playbook and comes up with the Colin Patterson story. It goes without saying that Bethell gets the details wrong; Patterson, for example, did not deny common descent. For the sake of argument, let's pretend for a moment that Patterson is on Bethell's side. Then the point of Bethell's misremembered anecdote is that we should rely on the authority of Colin Patterson, but not on the authority of all the other biologists who accept that evolution is the best explanation we have for the diversity of life as we see it today.

Altogether, a rather unimpressive performance for Mr. Bethell, who has been denying evolution for 30 years without learning anything about it. Funny -- he behaves just like a creationist.

Principal of Local Christian School Gives Away the Store

As I've previously discussed, there is a current push by some religious groups and the Ontario Tories to fund private religious schools. John Tory, leader of the Conservatives, awoke a firestorm of controversy when he stated that it would just fine if Christian schools decided to teach creationism.

In a September 8 letter to the editor published in our local paper, the Kitchener-Waterloo Record, Bob Moore, the principal of the John Calvin Christian School in Guelph, Ontario, calls the teaching of creationism a "bogey man". He went on to say "...evolution and creationism are non-issues." So far, par for the course.

Now, here's where Moore inadvertently gives away the store. His very next sentence is "The actual scientific study of the origins of the universe in any faith-based school would be remarkably similar to what McGuinty experienced when he was educated in a Roman Catholic faith-based school, and I suspect that he thinks he was well-educated."

Only problem is, evolution is a theory of biology that has nothing to do "the scientific study of the origins of the universe". This is exactly the kind of confusion sown by creationist tracts.

Unwittingly, Principal Moore has demonstrated a lack of understanding of evolution, and the reason why private religious schools shouldn't be funded.

Saturday, September 08, 2007

Canadian Muslim Group Invites Al-Zarqawi Supporter as Speaker

Well, I see my colleague Mohamed Elmasry is at it again.

Elmasry, you may remember, is the Electrical and Computer Engineering professor who claimed that Israeli citizens were fair game:

COREN: So everyone in Israel and anyone and everyone in Israel, irrespective of gender, over the age of 18 is a valid target?

ELMASRY: Yes, I would say.

Elmasry later apologized for his remark.

Now, in his role as "Chair and National President" of the Canadian Islamic Congress, he's bringing Al-Zarqawi supporter and general froot loop Yvonne Ridley to speak in Montreal, Toronto, and Waterloo. Yes, that's certainly the way to improve relations with the Jewish community.

A convert to Islam, Ridley has urged British Muslims not to cooperate with the police and has been an apologist for both Al-Zarqawi and a Chechen terrorist involved in the Moscow theater hostage crisis.

Recently she has blustered that "However if any of those Zionist idiots continue to try and paint me as an anti-semite I must warn you ... one of my closest friends is one of Britain's best defamation lawyers." Let's see, the last British journalist that blustered about libel in the same way was David Irving... and that didn't work out so well for him, did it?

In response to accusations of anti-Semitism, Ridley writes "Well a semite is a person who can be an Arab or a Jew ... hmm, so these dingbats are accusing me of hating the entire Jewish and Arab world?" Except that, as Robert Wistrich points out in Antisemitism: The Longest Hatred, "`Antisemitism' is a problematic term, first invented in the 1870s by the German journalist Wilhelm Marr to describe the `non-confessional' hatred of Jews and Judaism which he and others like him advocated... `Antisemitism' -- a term which came into general use as part of this politically motivated anti-Jewish campaign of the 1880s -- was never directed against `Semites' as such.... ...As a result, for the last hundred years, the illogical term `antisemitism', which never really meant hatred of `Semites' (for example, Arabs) at all, but rather hatred of Jews, has come to be accepted in general usage as denoting all forms of hostility towards Jews and Judaism throughout history."

I don't like the fact that B'nai Brith "would have supported" a ban of Ridley from Canada. By all means, let the attention-seeking froot loop speak. Her own words demonstrate her intellectual bankruptcy and the dangers of mixing religion with politics.

Mathematics in a Jack Reacher Novel

Lee Child is the author of a series of 11 novels involving Jack Reacher, an ex-Army MP who travels around the US, shooting up bad guys, saving the good guys (and gals), all while having no fixed address and no possessions. Think of The Saint, but more laconic, and on steroids.

In the latest Jack Reacher novel, Bad Luck and Trouble, we are suddenly informed that Reacher has "some kind of a junior-idiot-savant facility with arithmetic." (This characteristic never appeared before in any other Reacher novel.) Reacher uses the number 8197 as his ATM card PIN "because [97] was the largest two-digit prime number, and he loved 81 because it was absolutely the only number out of all the literally infinite possibilities whose square root was also the sum of its digits. Square root of eighty-one was nine, and eight and one made nine. No other nontrivial number in the cosmos had that kind of sweet symmetry. Perfect."

Of course, 0 and 1 also have the property that their square root equals the sum of their digits, but Reacher apparently dismisses these as "trivial".

This kind of property -- that a number's square root equals the sum of its digits -- is exactly the kind that most mathematicians would dismiss as uninteresting. There are at least two reasons. First is the privileged position given to base-10 numeration. In base 10, the square root of 81 equals the sum of its digits, but that's not the case in base 2, where 8110 = 10100012, so the sum of the base-2 digits is 3. Why should we single out base 10, rather than some other base?

Second, the reason why 0, 1, and 81 are the only numbers with the Reacher property is essentially trivial: the sum of a number's digits grows, at most, something like 9 log10 n which, as n goes to infinity, is much less than sqrt(n). So we already know, with essentially no calculation, that there can only be a finite number of Reacher numbers in any base; the fact that there are three of them is not particularly interesting.

[Exercise: 81 also has the property that its fourth root equals the sum of its digits, when expressed in base 2. Find another number besides 0 and 1 with this property. Extra credit: explain why nobody cares.]

Elsewhere in the novel, Reacher explains how he would choose a 6-digit password:

"Six characters? I'd probably write out my birthday, month, day, year and find the nearest prime number." Then he thought for second and said, "Actually, that would be a problem, because there would be two equally close, one exactly seven less and one exactly seven more. So I guess I'd use the square root instead, rounded to three decimal places. Ignore the decimal point, that would give me six numbers, all different."

So what's Reacher's birthday? Keep in mind that, according to the novels, he seems to be between 35 and 55 years old. I'll give the answer in another post - if anybody cares.

Update: (April 3 2015). Here's a genuine mathematical question. Fix a base b, such as 2 or 10. Are there infinitely many numbers n such that n is a power of the sum of the base-b digits of n? Reacher's number 81 works in base 2 and base 10, for example. For base 2, the first few examples are 0,1, 81, 625, 7776, 16807, 46656, 59049, 1679616, 1475789056, 6975757441, 137858491849, 576650390625 and form sequence A256590 at the On-Line Encyclopedia of Integer Sequences.

Wednesday, September 05, 2007

Stupid Tory Tricks: Religious Schools In Ontario Could Teach Creationism, Get Public Funds

The aptly named Progressive Conservative leader John Tory, in his push to fund religious schools in Ontario, says it would be just fine with him if Christian schools teach creationism as a legitimate alternative to evolution.

For those outside Ontario: here, public funds are used for the public schools and for the "separate schools" -- those that are run by Catholic religious groups. These Catholic schools are a parallel system, with their own elections for school boards, and are an unfortunate result of the compromise that led to Confederation 140 years ago. As a result of the London Conference of 1866, separate schools were guaranteed in in Québec and Ontario, but not some other provinces. Section 93 (3) of the Constitution Act (formerly called the British North America Act) reads

(3.) Where in any Province a System of Separate or Dissentient Schools exists by Law at the Union or is thereafter established by the Legislature of the Province, an Appeal shall lie to the Governor General in Council from any Act or Decision of any Provincial Authority affecting any Right or Privilege of the Protestant or Roman Catholic Minority of the Queen's Subjects in relation to Education:

Not surprisingly, other religious groups, including Protestant and Jewish groups, have objected to the special treatment received by Catholics in Ontario. But instead of attempting to end public funding for all religious schools, the Progressive Conservatives have made funding of all accredited religious schools part of their party platform in the upcoming provincial elections. Polls show, however, that the majority of the public is opposed to this change. Rick Johnson, head of the Ontario School Boards Association, resigned his position to run for one of the opposition parties, the Liberals.

According to an interview with Tory I heard on the CBC this afternoon, “They teach evolution in the Ontario curriculum, but they also could teach the facts to the children that there are other theories that people have out there that are part of some Christian beliefs."

If I could vote in Ontario (I can't, since I'm only a permanent resident, not a citizen), I certainly wouldn't give my vote to someone who doesn't know the difference between a fact and a theory, and who thinks that creationism is a scientific theory that is suitable for teaching in Ontario's science classes.

Unbelievable!

Go read this column from an editor of the Galesville Republican, a small paper in Wisconsin. The writer, a certain Rose Eddy, compares the Freedom from Religion Foundation (an excellent organization devoted to the separation of church and state - I'm a member) to the Ku Klux Klan, the Nazis, and Al Qaeda.

There's been a lot of whining in my local paper about how "people of faith" are misrepresented in the mainstream media. The funny thing is, the kind of misrepresentation Christians get in the media is nothing compared to the abuse regularly heaped on atheists.

Saturday, September 01, 2007

Shortest No More

Well, as I anticipated, my shortest google query that returns no results no longer qualifies. So I'll have to try another. This time, though, I'll cleverly disguise it so that google won't find it.

The first three letters of my query are "zk0".

And the last two letters are "q" followed by 1+6.

Can anyone find a query of 4 letters and numbers that returns no results?

Friday, August 31, 2007

A Google Query

What's the shortest string of lower-case letters and numbers (no spaces or other characters) you can type into google and not get any hits?

The shortest I've found so far, by non-systematic experimenting, is of length 5. I'd tell you what it is, but then it would be indexed by google and hence no longer work.

Oh, what the heck. I'll tell you anyway: zk4qj .

There. I've said it. And now. like Frankenstein, my lovely creation will soon be destroyed.

Monday, August 27, 2007

The Discovery Institute Lies Again

In this latest posting, the Discovery Institute shows once again why it has a well-deserved reputation for dishonesty.

The DI is touting William Dembski's No Free Lunch as "essential reading". But there is no mention that the book has received uniformly negative reviews from biologists and mathematicians, nor that the centerpiece calculation of the book, an estimate of a probability associated with the bacterial flagellum, is off by about 65 orders of magnitude. There is no mention that the definition of "complex specified information" is nonsensical and does not have the properties claimed for it. There is no mention that David Wolpert, co-discoverer of the "No Free Lunch" theorems mentioned in Dembski's book, criticized Dembski's argument as hopelessly imprecise.

But what else can you expect from the Dissembling Institute?

Thursday, August 23, 2007

The Noncommutative Frobenius Problem is Solved!

I rarely get the opportunity to talk about research problems on this blog, but this is an exception.

Consider the famous "Chicken McNuggets problem": if Chicken McNuggets are sold at McDonald's only in boxes of 6, 9, or 20 McNuggets, what's the largest number of McNuggets you can't buy at McDonald's? The answer happens to be my favorite number, 43. (Why it is my favorite is a story that will have to wait for another day.) Notice that you can buy any number of McNuggets greater than 43. For example,

44 = 4*6 + 1*20,

45 = 5*9,

46 = 1*6 + 2*20,

47 = 3*6 + 1*9 + 1*20,

48 = 8*6,

49 = 1*9 + 2*20,

and any number greater than 49 can be obtained by adding an appropriate multiple of 6 to these.

In general, you're given a set S of integers, and you want to know the largest number that cannot be expressed as a non-negative integer linear combination of the elements of S. This is called the Frobenius number because Frobenius is supposed to have mentioned it often during his lectures.

Of course, such an integer may not exist. For example, if S = {4, 6}, then you can only get multiples of 2 by forming an integer linear combination of 4 and 6. So you need to impose an important condition: the greatest common divisor of the elements of S must be 1. If this is the case, then you can express every sufficiently large integer as a non-negative integer linear combination of the elements of S.

Now, solving the classical Frobenius problem is easy in some cases. For example, here's a well-known formula for the case when S has only two elements, x and y, and here it is: xy - x - y. So, for example, the Frobenius number of 5 and 7 is 23. Every number larger than 23 can be expressed as a non-negative integer linear combination of 5 and 7. 24, for example, would be 2*5 + 2*7, and so forth -- but 23 itself cannot.

Greenberg wrote a paper in 1988, and Davison wrote another paper in 1994, in which they gave an efficient algorithm for three numbers.

Unfortunately, the general problem was proved NP-hard (under Turing reductions) by Ramirez Alfonsin in 1996. Roughly speaking, this means the problem is at least as hard as many classical problems for which we still have no efficient solution, such as the traveling salesman problem.

About 6 years ago, I suggested generalizing this problem from numbers to strings of symbols (sometimes called "words"). This kind of generalization is a typical activity in mathematics and theoretical computer science. You take a well-studied problem over one kind of domain, and see how the problem translates in another. The classical Frobenius problem dealt with positive integers, so we'll replace them with strings. Now S will be a set of strings.

Now we have to find the analogue of a non-negative integer linear combination. This is no problem: strings like to join up with other strings, in a process called concatenation, so our non-negative integer linear combinations will be replaced by all possible ways to concatenate the strings of S, using any of them any number of times (including 0 times). This process is sometimes called Kleene closure after the American logician Stephen Kleene, and we write it as S*. For example, if S = {0, 01}, then S* = { ε, 0, 00, 01, 000, 001, 010, ... }. That funny ε at the beginning is the usual mathematical representation for the empty string: the string with no letters at all in it. Notice that order matters in concatenation (houseboat isn't the same as boathouse), so we've gone from a commutative setting to a noncommutative one.

So S* is an infinite set of strings. (By the way, in this particular example, where S = {0, 01}, the set S* happens to have a nice description: it's the set of all strings that don't begin with a 1, and don't have two consecutive 1's appearing anywhere.)

OK, now we've generalized the "non-negative integer linear combination" part. How about the condition that the greatest common divisor (gcd) of the elements of S must be 1? Well, the point of that condition was just to ensure that every sufficiently large integer had a representation, so rather than worrying about how to define the greatest common divisor of two strings, let's replace the gcd condition with: every sufficiently long string must be in S*. There's another way to say this: the complement of a set T is the set of all strings occurring in the universal set that don't occur in T. Here the universal set is just the set of all strings. So our condition is that the complement of S* should be finite. In the arcane lingo of mathematicians, we can abbreviate this as: S* is co-finite.

Now, are there any examples where S* is co-finite? Yes. One example is S = {1, 00, 01,10, 000, 01010}. It shouldn't be too hard to convince yourself that every string except 0 and 010 can be written as concatenation of strings in this set. So in this case S* is co-finite.

Finally, we need an analogue of the largest integer not representable. That's not hard --- it's just the length of the longest string not in S*. In the previous example, where S = {1, 00, 01,10, 000, 01010}, the answer would be 3, since 010 is the longest string omitted from S*. Let's call this the Frobenius number of the set of strings S.

Now it's not too hard to show that if the longest string in S is of length n, and S* is co-finite, then the Frobenius number is bounded by a function which is exponential in n. For example, over an alphabet of two letters, you can show that the Frobenius number is < (2/3)*(4n - 1). (In case the exponent doesn't show up well in your browser, that's 4 to the n power, minus 1, times two-thirds.)

I figured out this generalization a while ago, and the upper bound a year or so ago. But I could not find any example where the Frobenius number was anywhere near as big as that upper bound. Indeed, for a long time, the worst-case example I knew was when you took S to be the set of all strings of length n, together with all the strings of length n+1. In this case, the Frobenius number is easily shown to be n2 - n - 1.

I gave the problem to my Ph. D. student Zhi Xu, who only started a few months ago. We tried many different possibilities, but eventually we figured out that you should try sets S that contain almost all strings of some lengths, omitting only a few. And recently he made a big breakthrough: he was able to construct examples where the Frobenius number is exponentially large in n, the length of the longest string. Here's one of his examples: take S to be over a binary alphabet, that is, over {0,1}, and let it contain all the strings of length 3, all the strings of length 5, except that you remove the strings {00001, 01010, 10011}. Then S* is co-finite, and the length of the longest string not in S* is 25. For example, 0000101001100000001010011 can't be gotten by concatenating the strings of S.

So our understanding of Frobenius problem for strings is now greatly improved, in the sense that there is an exponential upper bound and a class of examples that provides an exponential lower bound. The bounds are not exactly tight, but they are much tighter than ever before. Zhi Xu has many other results on this problem, and you can see our paper on the subject here. We wrote it together with Jui-Yi Kao, another student of mine who also made some very nice contributions. I expect this paper will form the basis of Zhi Xu's Ph. D. thesis. Of course, there is much more to be done in this area.

I hope you enjoyed this tour of my recent research, and congratulations to Zhi Xu for a job well done!

Wednesday, August 22, 2007

How Stupid Do They Think We Are?

I see that the crafty and unctuous Sal Cordova is up to his old tricks again, this time truncating a quote of Darwin to make it appear that Darwin endorsed intelligent design. No doubt when called on this dishonesty, he'll call it "street theater".

David Warren: Blowhard of the Month, Again

David Warren, who I previously celebrated as Blowhard of the Month back in January 2006, is at it again.

Take a look at this recent column, which believe it or not, was actually published in the Ottawa Citizen.

From the very first line, Warren demonstrates ignorance (or dishonesty). He calls Paul Feyerabend a "scientist", when in fact, Feyerabend was a philosopher.

He then celebrates Freeman Dyson, a once-respectable mathematician and physicist who has become slightly, uh, eccentric in his dotage. (Dyson even wrote a friendly foreword to Elizabeth Lloyd Mayer's credulous Extraordinary Knowing.) Why does Warren like Dyson? I doubt Warren could coherently explain even one of Dyson's contributions. No, what Warren likes about Dyson is that Dyson is a global warming skeptic. Of course Dyson's opinion about global warming is about as valid as mine, considering that Dyson has no training in climatology and has not published any papers on the subject.

Later, Warren refers to "Darwinist cosmology". Considering that Darwin was a biologist, not a physicist or a cosmologist, I can only wonder what Warren thinks he is talking about.

Finally, in Warren's crowning moment, he completely misrepresents Michael Behe's testimony in the Dover case, claiming that "Behe demurred" when attorney Eric Rothschild said, "So you believe astrology is valid science." Of course, this is false, as a glance at the testimony will show. Rothschild never said what Warren claims. Here's the crucial exchange:


Q Under that same definition astrology is a scientific theory under your definition, correct?

A Under my definition, a scientific theory is a proposed explanation which focuses or points to physical, observable data and logical inferences. There are many things throughout the history of science which we now think to be incorrect which nonetheless would fit that -- which would fit that definition. Yes, astrology is in fact one, and so is the ether theory of the propagation of light, and many other -- many other theories as well.


Warren finishes by saying


How I wish the high priests of Darwinism could restrain themselves in similar ways. They can’t, because Darwinism is a religion, and moreover, a false religion, in fear of free inquiry.


Why is it that theists, when they want to insult science, they call it a religion?

Sunday, August 19, 2007

Return of the Vanity Scam

It seems the American Biographical Institute just won't give up.

They failed to entice me by selecting me as a "Great Mind of the 21st Century", so now they've upped the ante.

Now they're nominating me as "Man of the Year".

For only $195 (or $295 if I want it laminated on "Finland Birch Wood"), I can get a decree calling me "Man of the Year 2007", "based on his outstanding accomplishments to date and the noble example he has set for his peers and entire community."



Really, I wonder how vain you would have to be to fall for this transparent scam.

Oh. About this vain. Or this vain. Or this vain...

Tuesday, August 14, 2007

A New Word - "Outcheap" - and McCain's Unintentional Irony

On NPR this morning there were two items of linguistic interest.

The first was this interview with Joe White, the Detroit bureau chief for the Wall Street Journal. White discussed driving a plug-in electric car, and in the discussion he used a word I've never heard before:

"The reasons why we don't have all-electric cars running around - and this goes back more than a century - is that battery technology simply hasn't evolved to the point where we can outperform and outcheap gasoline and the internal combustion engine."

The OED doesn't list "outcheap" as a word, but it's clear what it means: "to be able to be produced more cheaply than an alternative". It reminds me of a word my friend Jean-Paul once invented, as a translation for the French defenestrer: to "outwindow". He was disappointed to learn that "defenestrate" already existed in English.

I found some earlier citations using Lexis. An article in Crain's Detroit Business, April 15, 1996, quotes Farmington Hills retailing consultant Frederick Marx as saying , ''Anybody can add volume giving it away, and that's what it's becoming: a contest of who can outcheap each other.''

The second item was this interview with presidential candidate John McCain.

"One of the things that drove Harry Truman's decision to integrate our military was how shocked and angered he was by the lynchings of two African-American World War II veterans. Truman was certainly no - you know, he used racial epitats in private conversation, etc., but he believed that his oath to protect the Constitution made him responsible to protect the rights of all the American people."

Here McCain used the nonexistent word "epitat". He really meant "epithet", but was probably mixing it up in his mind with "epitaph", and so out came this mélange of both words.

Ironically, McCain also said, "Let's have some straight talk. Harry Truman was not the greatest intellect that ever inhabited the White House, but he had the right instincts, and frankly, he had the humility and inspiration to recognize that you have to suborn your personal ambitions for the greater good."

Here McCain demonstrates that he doesn't know what the relatively uncommon word "suborn" means. According to the OED, it has several meanings, but the ones that are most familiar are

  • "to use illegal or underhanded means to induce someone else to do a misdeed"
  • "to induce someone to give false testimony" (as in "to suborn perjury")


McCain probably meant to say "subdue" or "subjugate". I like the irony that he was calling Truman intellectually deficient while, in the same sentence, he exhibited some ignorance himself.

Talk Radio Hosts Fired for Debunking Phony Racist Memo

From the Washington Post comes this sad story about two radio talk show hosts who have been fired for debunking a rumor, long passed around in the African-American community, that the Carter administration secretly plotted to undermine domestic black leaders.

Casey Lartigue Jr. and Eliot Morgan hosted "The Casey Lartigue Show", a weekly political talk show on XM satellite radio. They discussed this phony memo which exists in various versions on the Internet. (One tip-off that it's phony? Brzezinski's last name was spelled incorrectly.) The version I've linked to is on (no surprise) the website of Louis Farrakhan.

Lartigue and Morgan were fired when they exposed the memo as a fake. In doing so, they went against the XM's lead talk show host, Joe Madison, who still believes that the memo is real.

Talk radio: where telling the truth can get you fired. I guess that's why people like Rush Limbaugh still have jobs.

Monday, August 13, 2007

Combinatorics on Words, A Puzzle, and a Silly Research Proposal

One of the areas I work in is combinatorics on words. In this field, we are interested in words (strings of symbols) and their properties.

For example, a square is a nonempty word of the form xx, where x is a word. Some examples of squares in English include tartar and murmur. If a word contains no subword that is a square, we say it is squarefree. Notice that the word squarefree is not squarefree, as it contains the square ee.

A classical question, first discussed a hundred years ago by the Norwegian mathematician Axel Thue, is whether there exist infinite squarefree words over a finite alphabet. Over a two-letter alphabet, this is not possible, as any binary word of length 4 or more contains a square. (Proof: let the first letter be a. Then if the next letter is a, we have a square. So assume the next letter is b. If the third letter is b, we have a square again. So assume the third letter is a. Now, whatever letter is chosen as the fourth letter, we get a square.)

But is it possible over a three-letter alphabet? The answer is yes, as Thue showed.

Erdős considered a variation on this problem. Instead of trying to avoid squares, let's try to avoid abelian squares. An abelian square is a nonempty string of the form x x', where x' is a permutation of x. Some nice examples of abelian squares in English include reappear (the first half of the word reappears in the second half) and mesosome. Can you find the longest word in English that is an abelian square? Hint: it represents part of the body. If you're interested in this sort of wordplay, see my page on repetitions in natural languages, where the solution to the puzzle is given.

For many years it was not known whether one could construct an infinite word over a 4-letter alphabet that contains no abelian squares. But in 1992, Veikko Keränen showed that one could. His construction involves constructing a map that sends each letter in {a,b,c,d} to a string of length 85. Starting with a, one then simply iterates this map. For more information, visit Keränen's page.

Now we've covered combinatorics on words, and the puzzle. It's time for the third item in the title. Go visit this silly research proposal by a professor of civil engineering and engineering mechanics at Columbia University. The proposal is so poorly written that I can't really tell what he has in mind, but he seems to suggest representing strategies for development in third-world countries by strings of symbols that specify a temporal sequence of events. I really hope this is a joke, but if it is not a joke, I hope it doesn't get funded.

Friday, July 27, 2007

New Study Shows "Cell Phone Tower Allergy" All in the Mind

I have two relatives who believe that electromagnetic fields are having a deleterious effect on their health.

Although I doubt this new study will convince them, it's still relevant. Elaine Fox, of the University of Essex, studied 44 people who claimed they were sensitive to cell phone towers and 114 normal people. They then exposed them to signals from the mast, sometimes telling them when the tower was on or off, and sometimes not telling them.

When the subject did not know whether the tower was on, they were not able to decide any better than chance whether the tower was on or not. When they knew, the sensitive people exhibited significantly more symptoms than the ordinary people.

This establishes with reasonable certainty that "cell phone tower allergy" is all in the mind. Their symptoms may be real, but they're due to fear and hysteria, not the signals.

Sunday, July 22, 2007

Good and Bad Reporting

Contrast this article from yesterday's National Post about the rise of atheism with this series by local religion "reporter" Denyse O'Leary.

The National Post article points out that the non-religious in America have grown from 8% to 14.3% of the population between 1990 and 2001, and that a 2006 study shows 20% of young adults are non-religious, up from 11%. The article discusses the recent atheist books by Sam Harris, Richard Dawkins, and Christopher Hitchens, and quotes prominent atheists such as Dan Barker and Annie Laurie Gaylor of the Freedom From Religion Foundation, and Herb Silverman, an atheist mathematician who successfully challenged a South Carolina law that established a religious test for public office, in conflict with the US constitution.

Now, any sensible person would conclude from the statistics in the National Post article and the wave of best-selling atheist books that interest in atheism is increasing, and the Post reporter has a brief analysis why: former UW professor Michael Higgins is quoted as saying "There is a profoundly anti-religious sentiment that exists in the culture-at-large as a result of 9/11" and "There is a souring against religion. There is a general perception that most political and social problems have been generated by religion [and] this comes from the danger people fear as a consequence of 9/11."

Now look at O'Leary's "reporting". She calls the rise of atheism an "anti-God crusade". (Isn't it strange that when theists want to insult atheism, they resort to using explicitly religious language that recalls the bad aspects of religion?) And she suggests that the rise in the interest in atheism is really due to the failure of materialism. She even denies that atheism is on the rise, claiming "atheism ... is stagnant or withering away". Of course, no actual statistics are provided to support this claim. I wonder what it would be like to live in O'Leary's topsy-turvy world.

In her series, O'Leary doesn't do any actual reporting. You will look in vain to find O'Leary actually interviewing anyone, particularly an atheist, to find out what they believe. No, O'Leary resorts to quoting the work of real journalists, journalists who have actually bothered to do the legwork required for an article. Instead, the series consists mostly of sneers and insults directed at atheists and amateur psychologizing:

"...Materialist science is in trouble. And the trouble does not stem from traditional religions, though materialists are - as one might expect - quick to blame their troubles on traditional religions and to reassure themselves that - despite all the evidence - traditional religions are doomed. But, materialists are also smug and thus cannot imagine or respond to any source of trouble arising from their interpretation of the evidence.

They have apparently decided instead to target the Christian religion as the source of their problems. One outcome is that, as we shall see, many materialists want to start a new religion to compete with the traditional ones, including a Darwin Day (Christmas, Eid al-Fitr, and Chinese New Year all rolled into one?)..."


Along the way, O'Leary manages to plug her books. (No article by O'Leary is complete without self-promotion.) She resorts to the hoariest clichés, calling atheists "militant" and "dogmatic".

There is an interesting parallel here between O'Leary's parasitic use of other reporters' work to construct her series, and the behavior of creationists. Like creationists, O'Leary didn't do any actual research of her own. Like creationists, O'Leary isn't interested in exploring her subject, the evidence, or why people believe they way they do. Like creationists, O'Leary spends most of her time denigrating a view she doesn't accept.

My parents were journalists. Some journalists are friends of mine. Ms. O'Leary, you're no journalist.

Saturday, July 21, 2007

Turku's Fibonacci Smokestack



From my student, Dalia Krieger, here's a picture of a smokestack in Turku, Finland, that displays, in neon, the first 10 Fibonacci numbers. Why is it there? I have no idea. But why should Finland have all the fun? Let's put the Thue-Morse sequence on some smokestacks.