Recursivity

At Prof. Kenyon's talk on Monday on "Myths About Atheism", he mentioned a study I was not very familiar with: a paper by Curlin, Dugdale, Lantos, and Chin in Annals of Family Medicine 5 (2007), 353-360. In this paper, the authors studied to what extent the religious beliefs of doctors influenced their decision to work in underserved areas. Their conclusion was "Physicians who were more religious in general, as measured by intrinsic religiosity or frequency of attendance at religious services, were much more likely to conceive of the practice of medicine as a calling but not more likely to report practice among the underserved."

It's an interesting study, and it's one of several that suggest that religious people aren't more ethical or socially responsible than non-religious people. What I found most interesting, however, was Prof. Kenyon's citing of this response to the Curlin study by one Alva B. Weir, a physician from Bristol, Tennessee, and affiliated with the "Christian Medical and Dental Associations". You can read the whole letter at the link; I'll excerpt two paragraphs below:


First, the article is an indictment of physicians who follow the great faith traditions, each of which mandates a responsibility for the poor. Though the most spiritual doctors do serve the poor more, the majority of doctors practicing their faith do not seem to take the mandate seriously. There seems to be a disconnect between the teachings of their faith and this selected practice of their faith. This suggests a contagion of a secular culture’s philosophy, “Each man for himself.”

On the other hand, the care documented for the undeserved by physicians of little faith suggests an influence of the faith traditions they deny. A culture completely dominated by a Darwinian “survival of the fittest” mentality would find it difficult to embrace care for the underserved except through very twisted social Darwinian theory. It is the great faith traditions of the world that have taken a religious mandate to care for the poor and imbedded it into our social conscience.


Did you get that? The only reason that religious doctors don't do more is that they have been contaminated with the "contagion" of secular culture. And the reason that non-believers do as much as they do is because they have been influenced by "faith traditions they deny". The contortions of reasoning required to come to these conclusions boggle the mind.

Long before Jesus ever existed, human beings cared for the sick and the poor. They did so not because of the injunctions of some religious faith, but because humans are social animals who are able to comprehend the suffering of others.

Denying the truth claims of religious traditions, such as the divinity of Jesus, does not mean one has to embrace "social Darwinism", a philosophy that has little to do with evolutionary biology and everything to do with selfishness. Nonbelievers can do good, and do it without religion. One can accept evolution as the best scientific explanation for the diversity of life, and still help one's fellow man.

I am really, really glad that Alva B. Weir isn't my physician, because his response displays bigotry against nonbelievers, and suggests a willingness to twist the results of the study to fit preconceptions.

Tim Kenyon, a philosophy professor at the University of Waterloo, gave an enjoyable talk Monday entitled "Myths About Atheism". Prof. Kenyon is a clear and entertaining speaker. The talk was reasonably well-attended, and there was time for an hour's worth of Q & A at the conclusion.

Here are the 10 myths that Prof. Kenyon discussed:

1. Atheists are angry at [insert favorite god here].
   
   
2. Atheists are faking being atheists.
   
   
3. Atheists are immoral.
   
   
4. Atheism is Darwinism.
   
   
5. Atheists think they can explain everything.
   
   
6. Atheists hold that life has no meaning.
   
   
7. Atheism = communism/fascism/etc.
   
   
8. Atheism is faith-based.
   
   
9. Atheism is a religion.
   
   
10. Atheism dominates the media.
    

I think this is just the beginning of a much longer list. Here are a few that come to mind:

11. Atheists are dogmatic.

12. Atheists are militant.

13. Atheists choose atheism to avoid moral responsibility for their actions.

Can you think of any other common myths?

The CBC reports that Canada's National Science Advisor, Arthur Carty, will retire on March 31, and that the office will be closed. (Hat tip to Pharyngula.)

Although it's shortsighted and foolhardy to eliminate the office of National Science Advisor, we really needed someone with more willingness to stand up to the anti-science faction at SSHRC, the social science granting agency.

You may recall that SSHRC turned down a grant application of McGill professor Brian Alters, who had proposed to study how intelligent design advocates have a malign influence on biological education, because there was inadequate justification that "the theory of Evolution, and not Intelligent Design theory, was correct."

Many scientists, including me, wrote to Carty asking him to take a stand on this ridiculous position. Carty never even responded. His secretary promised action that never occurred.

Canada needs a science advisor office, and it needs a science advisor that is willing to defend evolution.

From time to time, I've been critical of our local paper, the Kitchener-Waterloo Record. But today they deserve a lot of congratulations.

Following up on a tip I told them about, today's front-page story exposes the questionable practices of Thorsten Wietschel, aka Sven Kugler, a "magnetic therapy" salesman.

Wietschel, or someone working for him, left the flyer below in my mailbox a couple of weeks ago.

As I uncovered by doing a Lexis search and informed the Record, Wietschel has a history of shady practices, including being charged with burglary and grand theft in California and being ordered by a court in Arizona to cease selling bogus medical products. Now he's in Kitchener for several talks in which he gives seniors a free lunch and then starts his pitch, offering expensive mattress covers lined with cheap magnets that he claims can help cure diseases. Apparently Wietschel is very smooth and convincing and has fooled people before.

The Record article by Brian Caldwell is well-written and pulls no punches. Hopefully it will prevent Wietschel from fooling more desperately ill people into buying his worthless magnetic mattress covers. Congratulations to Caldwell and city editor Harvey Taylor for a job well done!

Today is Donald Knuth's 70th birthday!


Donald Ervin Knuth was born in Milwaukee, Wisconsin, on January 10, 1938. He received his BS and MS degrees from Case Institute of Technology and his Ph.D. from the California Institute of Technology in 1963.

Knuth is probably best known for his three-volume work, The Art of Computer Programming, which popularized the analysis of algorithms as a basic tool of computer science. Volume 4, on combinatorial algorithms, is in preparation and parts have been published as "fascicles", preliminary to the final version.

Knuth is responsible for the theory of LR parsing, which he invented in a 1965 article. This method forms the basis for most modern compilers.

Knuth is the inventor of TeX, a system for typesetting mathematics that is used today by most mathematicians and computer scientists to prepare their papers.

Knuth is the recipient of many awards, including the 1974 Turing award (computer science's highest award).


My blogging friends in mathematics and computer science have put together a little birthday tribute to him:

• Mark Chu-Carroll, over at Good Math, Bad Math, offers this assessment of Knuth's contributions to typesetting.



• The irrepressible Doron Zeilberger sings Knuth's praises in this post, written in Zeilberger's inimitable style.



• From David Eppstein, a beautiful analysis of a backtracking algorithm to solve the exact cover problem.



• From Scott Aaronson, a review of Knuth's views on philosophy and God.



• From Luca Trevisan this lovely appreciation.



• From Bill Gasarch, an appraisal of Knuth's impact.



• From Suresh Venkatasubramanian, how to pick a random element from a set whose cardinality is unknown.



• Last but not least is my own little contribution.

There might be some more contributions later, so check back!

Still not satisified? You can look at this 1999 Salon piece, or this offbeat biography of Knuth from a future historian, or this NPR interview, or Knuth's own home page.

Happy birthday, Don!

To honor Donald Knuth's 70th birthday, I offer this personal reminiscence about Knuth's influence on me and the wider mathematical and computer science community.

My first exposure to Knuth's work was in 1973, when I had landed a summer job at the IBM Philadelphia Scientific Center with the APL group of Kenneth Iverson and Adin Falkoff. The Scientific Center, located at 3401 N. Market Street, had a wonderful mathematics library, and when I expressed some interest in computing some fundamental constants to many decimal places, the staff (probably Don Orth) directed me to Seminumerical Algorithms, Volume 2 of Knuth's magnum opus, The Art of Computer Programming. Reading it was like stepping into a new world.

Knuth revealed that doing a good job at programming was more than just putting together lines of code and timing them. One could actually analyze algorithms, determining their running times with great precision. One could prove mathematically that one algorithm was superior to another, and quantify how much better. And the analysis led to all sorts of amazing mathematics, involving asymptotic expansions, power series, and continued fractions. It fundamentally changed the way I viewed the computer.

Almost every page of Seminumerical Algorithms revealed something interesting. On one page, I learned about the binary gcd algorithm, an improvement on Euclid's algorithm. On another, a method for determining the continued fraction for any algebraic number that did not involve computing the number in decimal first. On another, the continued fraction for e^-1/n and tanh z. On another, a faster way to factor integers. Lacking the funds to buy the book, I began to photocopy pages that interested me. After a month or so I had photocopied almost the entire book.

And look! Knuth even offered a reward for readers who found errors in his book! In 1975, as a high school senior, I found an error (a small mistake in a factorization table), and sent it off to Knuth. I can still remember the pride I found when I received a check from him in the mail the next week. I never cashed the check, and still have it as a souvenir. (In my letter, I told him how I found his book so exciting that I photocopied nearly all of it; it didn't occur to me that an author expecting royalties might not find this a welcome sort of praise.) He wrote back, "For this you receive a reward of $1; find more errors and you'll be able to buy vol. 3 -- or make a Xerox copy of the check and cash it 100 times." Eventually I would accumulate 4 Knuth checks totalling $22.72 -- all still uncashed.

Later, when I attended university, I began to understand Knuth's wider influence. Almost everywhere I turned, Knuth had been there before. When I was interested in computing Euler's constant to thousands of digits, his 1962 paper showed me one way of doing it. When I got interested in paperfolding sequences, I found that his 1970 paper with Chandler Davis, "Number representations and dragon curves", had already proved everything I had and more. I wrote a program to play the guessing game "Master Mind", but then I found his paper, "The computer as master mind", which showed that my ideas were not optimal. His 1966 paper, "An almost linear recurrence", introduced me to the beauty and complexity of non-linear recurrences (even though, as it turns out, Mahler and de Bruijn had already published stronger results). A little-known 1964 paper in the Fibonacci Quarterly introduced me to some interesting series that eventually led to some of my first published papers. I read his marvelous book Surreal Numbers one weekend, and it eventually turned into a junior paper on the subject.

When I was an undergraduate, I wrote a paper on continued fractions that appeared in the Journal of Number Theory. Knuth read it, and included it as an exercise in Seminumerical Algorithms, page 363. (He assigned it a rating of 40, which means a difficulty equivalent to a "term project".) I was amazed to receive a postcard from him, inquiring about my middle name -- Knuth is very thorough (some might say obsessive) about including the full name of each person cited in his index. So at age 21 I was pleased to find myself in the index to volume 2, with my unusual middle name, sandwiched between "Shakespeare, William" and "Shamir, Adi".

It wasn't until I became a professor that I really began to appreciate the depth and breadth of Knuth's influence. His 1965 paper, "On the translation of languages from left to right" almost single-handedly developed the techniques that permit fast compilation of programming languages. The Knuth-Morris-Pratt algorithm was a breakthrough that allows linear time pattern matching, and introduced me to what are now called Sturmian words. His 1976 paper, "Big omicron and big omega and big theta", advocated the now-universal asymptotic notation like big-Theta. And his work on TeX created a system that nearly every mathematician and computer scientist uses to write their papers, exams, and homework assignments.

Of course, Knuth is human, and along the way he made some mistakes. I think his development of MIX, an idealized assembly language, was a waste of time and never had any significant influence. And, since I'm not a Christian, his book 3:16 Bible Texts Illuminated leaves me completely cold. But someone who is so productive and influential is allowed a few wrong turns now and then.

I should also say something about Knuth's personality. He is a very kind and considerate person. This is brought out in his version of Christianity, which is extremely humble -- just the opposite of the judgmental fundamentalists and creationists. In 2000, when he visited Waterloo to receive an honorary degree and to deliver the Pascal lectures, he brought a copy of his Selected Papers, autographed it, and left it in my mailbox. It is a gift I will always treasure. He has an offbeat sense of humor, as one can see by examining his earliest publication, from MAD magazine. Yet when you are wrong, he does not hesitate to point it out. I have at least two letters from him pointing out errors or disagreements with my work.

So, happy birthday to Donald Knuth! May he live a long life - long enough to complete The Art of Computer Programming, and savor its completion!

A surprising number of household objects are radioactive, and you can verify this with a cheap geiger counter, available on ebay for less than $100. (But be sure you get a geiger counter, not a radiation survey meter. The latter is good only after a nuclear attack, and is not sensitive enough for the experiment I describe here.)

One of the most surprising, at least to me, is water softener pellets -- more precisely, the kind that are made of postassium chloride (KCl). A 20 kg bag (below) sells for about $10 at your local supermarket or hardware store.


Here's a picture of my smallest geiger counter in an empty tupperware container. As you can see, it's registering 12 microRoentgen per hour. Probably most of this background radiation comes from cosmic rays or the smoke detector in my study.


Now I load up the tupperware container with about 1 kilogram of potassium chloride pellets, and try again:


Now the geiger counter is registering 40 microRoentgen per hour. It's not very radioactive, but it is about 2.3 times background.

Why are these water softener pellets radioactive? Surprisingly, it's just due to the potassium content. About 1 in every 8500 potassium atoms is K-40, a radioactive isotope of potassium (and the one that is used in potassium-argon dating). The half-life of K-40 is about 1.3 billion years, which means that potassium-argon dating can be used to date very old rocks (see Dalrymple, The Age of the Earth). K-40 emits both beta particles and gamma rays..

Now, your body also contains potassium, about 140g worth for the average person. So are people radioactive? Yes, slightly. According to this table, potassium-40 accounts for most of the self-irradiation of the body, with carbon-14 a close second. Altogether, about 8000 atoms a second are decomposing inside your body, and this can be measured with a sensitive detector.

Other radioactive items you might find in your house include smoke detectors (some use Americium-241), mantles for gas camping lights (some use Thorium oxide to make the light brighter, although this is less common now), and vaseline glass (uranium is added to the glass to get the yellow color).

One of the favorite dishonest tactics of denialists of all stripes is credential inflation. Credential inflation is the process by which those with little proficiency or knowledge of an area, or people with marginal credentials, are touted as experts. In this way, denialists can argue from authority, hoping that no one will challenge the credentials of their spokesmen.

Here are two recent examples of credential inflation. On the climate change denialist blog of far-right Senator James Inhofe, Christopher Monckton is described as a "UK climate researcher". In fact, Monckton is a former British journalist who apparently has no training in any relevant field, such as chemistry or atmospheric science. (His degrees were in classics and journalism.) He has not published a single peer-reviewed paper on climate change or environmental science. Monckton also has a public record of dishonesty, with a false claim that he is member of the House of Lords and a phony claim that he had to sell his ancestral home to pay off a puzzle prize.

I contacted the author of the Inhofe blog piece, Marc Morano. (Morano is a far-right hack who was involved in spreading the false Swift-boat claims about John Kerry.) Morano claimed in e-mail to me that "Lord Monckton has written many research papers on climate change", but was unable to substantiate this claim, producing instead a list of articles that appeared in newspapers such as the Telegraph and the Frontiers of Freedom website.

I then asked Morano about Monckton's training in climatology. He replied as follows:
"As far as I know Lord Monckton is not trained in climatology. But why do you only ask about climatology. The current global warming issue involved so many different disciplines, ie. Mathematics, economics, statisticians for modeling, Geologists for Earth's history, Astrophysicists for solar linking, oceanographers to understand CO2 emissions from oceans, etc."

To which I replied "You're right. Does Lord Monckton have any formal training in mathematics, statistics, geology, astrophysics, or oceanography?" To which Morano replied, "I do not know his entire educational background, but I do know that he has conducted climate research and even, I understand, got he UN to make a few corrections after he alerted them. That certainly qualifies as a "climate researcher." Maybe not peer-reviewed as you would like, but it still qualifies."

Shameless. I've pointed out mistakes in chemistry books, but that doesn't make me a chemistry researcher.

Here's another example of credential inflation. In a recent article on a Focus on the Family website, intelligent design advocate and evolution denialist William Dembski is described as a "leading scientist and mathematician". Now this is a claim that is easy to check. A real leading scientist or mathematician would have published at least a few very influential papers or books, receiving dozens of citations in the scientific literature. So I went over to the ISI Web of Knowledge (formerly Science Citation Index) website, to see how many citations Dembski has received. For a comparison, I chose Paul Vitányi, a colleague of mine who works in a similar area (information theory) and has the advantage of a fairly distinctive name.

I searched for "Dembski, W" using the "author finder" option. I then chose "WA Dembski" to search on (there is another researcher, W. J. Dembski, who actually has one paper that received more citations than all of Dembski's papers). According to ISI, Dembski has 5 items that have received citations. The total number of citations to his work is 5. I then asked for a citation report, and the following graph appeared.



Now, I did the same thing for Paul Vitányi. I chose "PMB Vitanyi" to search on, and found 60 papers cited a total of 358 times. Here's the same graph for Vitányi:



Examine the graphs carefully; the vertical scales are quite different.

So who, exactly, is the "leading scientist and mathematician" here?

Next time you see a denialist touting their expert, be suspicious. Credential inflation is one of their main tools.

The picture that has recently emerged of former governor Mike Huckabee is that of an intellectually incurious, greedy, and corrupt fundamentalist Christian.

So here are just some of the many reasons not to vote for him.

1. He thinks that scientists believe the earth is "six billion" years old. He also thinks we "just don't know" how old the earth is.

2. He covered up an incident where his son hanged a stray dog.

3. He lied about having a theology degree.

4. He claims ‘‘The Holy Bible . . . has truth, without any mixture of error, for its matter. Therefore, all Scripture is totally true and trustworthy.’’

5. In 1992, he wanted to quarantine people with AIDS, even though it was well-known then that AIDS could not be spread by casual contact.

6. He improperly claimed furniture given to the governor's office as a personal gift and then didn't list it on an inventory of office items.

7. He freed criminals who committed heinous offenses if they said they had become born-again.

8. He wants a regressive national sales tax in place of a progressive income tax.

9. In 1998, he signed a statement saying that "A wife is to submit graciously to the servant leadership of her husband".

10. He doesn't accept the theory of evolution.

---

Updated: an even better list by John Hunt is available here.

From Australia comes this very sad story of an argument between a creationist and two scientists that led to the death of one of the scientists after being stabbed by the creationist.

Creationists are constantly telling us how acceptance of the theory of evolution has undesirable consequences: for example, the National Association for Objectivity in Science claims that believe in evolution "can have a devastating impact on the student, leading him or her to devalue human life and possibly engage in drug abuse, sexual promiscuity, or violence, or even commit suicide."

Perhaps the opposite is true. Creationism, a form of religious dogma, can lead to violence because the creationist, having no evidence in support of his view, will become frustrated when challenged with evidence. The creationist typically believes that a supernatural being created him and that disbelief is evil. He is convinced of his moral superiority to the non-believer. Indeed, non-believers are threats, because they could spread their non-belief to others, contrary to his god's wishes.

Politicians aren't scientists, but it's reasonable for the next President of the United States to be knowledgeable about basic issues in science and technology.

Today we're confronted by many threats and politicial choices for which a knowledge of science is useful. An understanding of the biological theory of evolution is helpful for dealing with the crisis of AIDS in Africa, the over-prescription of antibiotics, and the rise of resistance in tuberculosis and staphylococcus infections. A general understanding of biology more generally would be helpful in dealing with bioterrorism and stem-cell research. An understanding of physics would be useful in evaluating our priorities in outer space and the possibility of a dirty bomb attack. An understanding of chemistry and environmental science would assist our lawmakers in dealing with global climate change and ozone depletion. An understanding of astronomy would be helpful for evaluating the threat posed by meteoritic impacts. More generally, an understanding of how science works and the scientific method would help leaders to evaluate competing scientific claims and to distinguish science from pseudoscience.

Unfortunately, many of the presidential candidates seem more interested in establishing their religious bona fides then they are in dealing with science and technology. Some candidates seem positively anti-science: Mike Huckabee, for example, has shamelessly repeats an old canard about bumblebees being unable to fly by the laws of physics and seems to believe he is not a primate or descended from primates.

Today I join scientists and other science bloggers in calling for a national debate among presidential candidates on science and technology. Let's have a chance for the scientists and the public to ask the questions and hear the answers of those who would lead.

Paul Davies, the British physicist and popularizer of science, wrote an astonishingly silly op-ed in the New York Times recently, in which he equates science and religion because both are based on "faith". It was a pleasure to see Davies' ideas completely shredded by Lawrence Krauss, Sean Carroll, and P. Z. Myers.

This isn't the first time Davies has said silly things. In The Fifth Miracle, for example, he attributes the ideas of algorithmic information theory to Gregory Chaitin, despite the fact that the Soviet probabilist Andrei Kolmogorov came up with them earlier (and despite the fact that nearly everyone calls the field "Kolmogorov complexity"). He also demonstrates his misunderstanding of Kolmogorov complexity when he says "Ordinary laws just transform input data into output data. They can shuffle information about but they can't create it." Of course, this is false. Take, for example, the transformation that maps a string x to the string xx. Then it is an elementary exercise in algorithmic information theory that the information (in the Kolmogorov sense) of xx is greater than that in x infinitely often. So, in fact, it is quite possible for "ordinary laws" to create information, in the Kolmogorov sense.

Also in the The Fifth Miracle, Davies makes the claim that quantum algorithms can make the solution of the traveling salesman problem "tractable" - a misconception so common that Scott Aaronson has resorted to debunking it in the masthead of his blog. It seems that when Davies pontificates about issues involving computational complexity and information theory, he cannot be relied upon.

Several years ago, Davies told me he would correct these mistakes (to his credit). But he's also been quoted as claiming, in Larry Witham's book By Design, that "Dembski's attempt to quantify design, or provide mathematical criteria for design, is extremely useful. I'm concerned that the suspicion of a hidden agenda is going to prevent that sort of work from receiving the recognition it deserves. Strictly speaking, you see, science should be judged purely on the science and not on the scientist." No surprise, Dembski flogs this quote whenever possible.

Two years ago, I asked Davies to justify his claims about Dembski. How, precisely, are Dembski's bogus claims "extremely useful"? Where have they been used? What about all the mathematical criticism of Dembski's work? Davies refused to justify his remarks, saying he was "too busy" to address them.

Now I see why he's "too busy". He's too busy writing silly op-eds for the New York Times.

Over at Jewcy, the repulsive David Klinghoffer offers up a defense of intelligent design, in response to Neal Pollack.

Jason Rosenhouse has taken time out from his forthcoming book on the Monty Hall problem to pen this response. As usual, it's incisive and worth reading. But there's one point that Rosenhouse didn't address.

Klinghoffer claims, "No Darwin critic that I know differs from established scientific conclusions about the age of the earth or of the universe since the moment of the Big Bang."

David Klinghoffer, meet your co-worker, Paul Nelson. Paul Nelson is a fellow at the Discovery Institute's Center for Renewal of Science and Culture. You know, the same place where Klinghoffer is Senior Fellow? Nelson is also a young-earth creationist; that is, he denies the scientific evidence for the age of the earth and the age of the universe, and instead claims the earth and universe are less than 10,000 years old. Of course, he doesn't do so because of the scientific evidence; he does so because his narrow, fundamentalist interpretation of the Bible tells him it must be so.

I suppose Klinghoffer can plead ignorance of Nelson's position. But it's hardly unknown. Nelson even contributed to a book entitled Three Views on Creation and Evolution, where he advocated the young-earth creationist point of view.

Remember when the Discovery Institute claimed "Faith healers and Holocaust deniers are not on the faculties of reputable universities. Scientists who support intelligent design are."? When that was shown to be a lie, did the Discovery Institute issue a retraction? Of course not: if they had to spend time retracting their lies, they wouldn't have the time to issue all those misleading and dishonest press releases.

There's a reason why the DI is called the Dishonesty Institute.

My student, Narad Rampersad, had a successful defense (or "defence", as they like to say in Canada) of his Ph. D. thesis yesterday. That's a good excuse to discuss some aspects of combinatorics on words.

In combinatorics on words, we are interested in words and their properties. By a word, I mean a finite or infinite string of symbols. The Norwegian mathematician Axel Thue initiated this field a hundred years ago in his study of infinite words avoiding squares and overlaps. A square is a word of the form xx, where x is a nonempty word. For example, the English word murmur is a square, with x = mur. Thue asked, is it possible to create an infinite word over a finite alphabet, such that it avoids squares (i.e., contains no squares)?

Over a two-letter alphabet, this can't be done: the first letter is 0, say. So, the next letter must be 1, otherwise we'd have the square 00. The third letter must be 0, for otherwise 011 would have the square 11. But then whatever you choose for the fourth letter gives a square.

Over a three-letter alphabet, however, it turns out you can construct an infinite word without squares. The construction is quite clever, and it was rediscovered by several people after Thue -- he published his work in a rather obscure Norwegian journal.

Thue also considered another kind of repetition avoidance: avoiding overlaps. An overlap is a pattern that is just slightly more than a square: it consists of two repetitions of a wordx, followed by the first letter of a third repetition. For example, the English word alfalfa is an overlap, because it consists of two copies of alf, followed by the first letter of alf.

Narad's thesis was entitled "Overlap-free words and generalizations", and he made several beautiful contributions to combinatorics on words. To describe one, I need the idea of a morphism, which is just a transformation of words defined by replacing each letter with a given word, and then joining all the results together. For example, consider the morphism μ defined as follows: replace each 0 with 01 and each 1 with 10. If I apply μ to a word like 011, I get 011010. I also need the idea of fixed point; a word is said to be a fixed point of a morphism if, when you apply the morphism, you get the same word back again. Thue discussed a special word

t = 01101001100101101001011001101001...

which is a fixed point of the morphism μ I just described. He proved the following amazing facts: first, the infinite word t contains no overlaps (we say it is "overlap-free"). Second, if an infinite binary word is overlap-free and is the fixed point of a morphism, then it either equals t or its complement, which is obtained by changing every 0 to 1 and vice-versa.

Narad generalized this last result of Thue. To explain his generalization, we need the notion of fractional power of a word. Consider a word like ingoing. We can consider this word to consist of ingo followed by the first three letters of the same word; in other words, it is a 7/4-power. More generally, a word is a k+p/q power if it consists of k repetitions of some block of length q, followed by the first p letters of that block. So the French word entente (which has been absorbed into English), is a 7/3 power.

What Narad proved is the following: the word t defined by Thue (and now called the Thue-Morse word) is the only one, other than its complement, that is 7/3-power-free and is a fixed point of a morphism. The proof is rather subtle and it appeared in International Journal of Foundations of Computer Science in 2005.

This is only one of many results contained in his thesis. I can't discuss them all, but I can't resist mentioning one other result, because it has a nice picture attached to it. Suppose we generalize our notion of infinite words to two dimensions: in other words, with every lattice point with non-negative integer coordinates, we associate some symbol. Then one can ask about avoiding squares in the plane: not just every row, column, and diagonal, but for every word defined by any line with rational slope. It turns out that one can indeed avoid squares in this case, as was shown by the Italian computer scientist Carpi in a beautiful 1988 paper; his construction used an alphabet of 16 symbols. Now instead of avoiding squares, suppose one only wants to avoid sufficiently large squares. Can we use a smaller alphabet in that case? Narad showed that if we want to avoid squares xx with the length of x greater than 2, then an alphabet of size 4 suffices. The construction can be illustrated by assigning each lattice point a square of a particular color, a different color for each symbol. Here's a portion of the result:



In January, Narad will be taking up an NSERC postdoc at the University of Winnipeg, to work with James Currie. Congratulations to Narad for a job well-done!

Tonight I debated Kirk Durston at the University of Waterloo on the topic, should a scientist believe in god? Eventually I'll post my slides and other information here, but for the moment, you can use this spot to post comments about the debate.

Here's my closing statement. I didn't get to read all of it because of time constraints (we were given only 5 minutes). If you read it, you will see the great debt I owe to P. Z. Myers and Carl Sagan.

The Manifesto Club has a new campaign, Attention Please, to point out the absurdity of some warning signs in public places. Week 1 has a small collection of photos of silly warning signs, including one on a cactus that says "Caution: These plants are covered in sharp spikes that may puncture the skin if touched. DO NOT HANDLE".

I think they could use a much larger set of submissions, so go to it!

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.

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.

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.

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?