Wednesday, December 27, 2006

The Greatest Innovation of Theoretical Computer Science

Spiked magazine has asked me to contribute 200 words on the subject of the "greatest innovation in my field". Here's my answer:


In theoretical computer science, the greatest innovation is the realization that algorithms are mathematical objects, and can be rigorously analyzed in terms of their consumption of scarce resources, including space, time, and randomness.

One of the first to analyze an algorithm was the French mathematician Pierre-Joseph-Étienne Finck (1797-1870). In an 1841 book, he showed that the Euclidean algorithm for computing the greatest common divisor
of two integers uses a number of division steps that is linearly bounded in the number of digits of the inputs. Finck's work is all but forgotten today, but I discussed it in a paper in Historia Mathematica in 1994.

In recent times, much of the credit for the development of algorithm analysis certainly belongs to Donald Ervin Knuth (b. 1938), who in a series of books entitled The Art of Computer Programming, popularized many of the tools now used routinely to analyze algorithms. Almost overnight, algorithm analysis changed from a purely engineering approach involving coding and testing, to a rigorous branch of mathematics where the challenge is proving theorems.

Is Science the New Religion?

My local newspaper (and I use that term generously), the Kitchener-Waterloo Record, has reprinted this George Johnson article from the New York Times. The original headline, as given in the NYT, was "A Free-For-All on Science and Religion". But the Record chose to give it a different headline: "Could science be the new religion?"

Here's my response:

Dear Editor:

With regard to "Could science be the new religion?", Record, December
27, 2006:

I'll believe science is the new religion when

- we exchange gifts on Darwin's birthday
- we get a national holiday to commemorate the discovery of DNA
- scientists get the same access to the White House as Billy Graham does
- St. Mary's Hospital hangs pictures of Pasteur in all its rooms
- and the Record devotes as much space to science coverage as it
does to religion.

Until then, let's keep them separate.

Tuesday, December 19, 2006

My University Sponsors "Healing Prayer" Sessions

My university, the University of Waterloo, is sponsoring sessions on "healing prayer". Imagine my surprise!

Here are the details: our university has a Recreation Committee. Most of they events they sponsor are things like outings to the local ski hill, or ASL classes. However, they have also been sponsoring some more questionable events, featuring topics such as Reiki, therapeutic touch, and Feng Shui.

The most recent event was a session on "healing prayer". Here is how the session was described on the UW Recreation Committee (UWRC) web site, until recently:

Monday, December 18, 2006: "Life Series" - Healing Prayer with Dr. Clifford Blake (First of Five Lessons). Humans have battled sickness, disease and calamity as long as they have been on earth. Lesson 1: A survey of some spiritual healing methods. An opportunity will be given to share experiences. Cost: no charge.


Oddly enough, although the talk has since vanished from the UWRC web site, the first session was still held yesterday. (I have been trying to find out from the UWRC why the talk descriptions have vanished. So far, no reply.)

Reader, I ask you to look at my summary of what Prof. Blake said in his talk, and tell me, is this the kind of talk our university should be sponsoring? (My comments below are in red.)

First, some background. The speaker, Clifford Blake, is a professor in the Department of Management Sciences. According to this page, Prof. Blake "has counselling ministries in spiritual and psycho-social development, and the empowerment of individuals, with a special focus on youths. He is actively involved in preaching, teaching and counselling in his local church and currently operates an independent counselling and healing ministry. At the community level Dr. Blake presents seminars on Black History and the African Genetic root, based on a synthesis of Holy Scripture, DNA research findings and fossil discoveries."

He began by stating his talk would be based on his scientific and religious background. Prayer, he said, has been used for thousands of years to overcome difficulties. But it hasn't been used as Biblical teachings prescribe, and so the results haven't been as good as they could be. He spoke of his own ministry and testimonials about healings. A man who had cancer, he said, was healed through a combination of chemotherapy and his healing methods. It was the combination of all, he asserted, that resulted in the cure. He advocated "magnetic methods" and "energy methods"; combining them is more efficacious.

He cautioned that traditional methods [by this he evidently meant conventional medicine] are excellent when it comes to analysis, but one shouldn't take them without question. Get other opinions: what are the side effects?

He then asked for testimonials from the audience. One participant advocated "Kriya Yoga" as "the fastest way to God". The miracles that she witnessed "could fill volumes". Someone who had Parkinson's is now almost symptom-free. A woman she knew had a stroke and was mostly paralyzed, but thanks to Kriya Yoga, she has now recovered. Additional examples were given.

Another participant discussed her experience being on a local bus where the bus engine died. She prayed, she said, and the bus engine then started up. When you put you hand on someone and pray, you can feel electricity.

Prof. Blake discussed other examples of healings he has participated in. A person at the university with a relative with obsessive-compulsive disorder was "completely cured" after one month visiting with Prof. Blake. A student with
"fractured legs" was able to walk "immediately" after being touched by Blake. He acknowledged that he could not prove he was responsible for the healing, but "if someone has a chronic condition for many years, and improves after my sessions, then that's pretty good evidence". A woman has x-rays before and after proving that a fracture was miraculously healed. He can bring letters from a woman in British Columbia who had leukemia; after he gave her a prayer in a letter, she was healed.

Prof. Blake then said he did not counsel people to not go to doctors. He then discussed "facts": drug companies keep their side effects a secret. For example, he said a recent study in the US showed breast cancer was down because women had decreased their estrogen replacement therapy. He had a relative who died of breast cancer after taking this therapy.

He then asked, what is the 3rd highest cause of death in the US. It is "iatrogenic causes" [meaning caused unintentionally by a physician]. A study in JAMA, he said, listed 225,000 deaths a year come from these causes, including 12,000 deaths from surgery, 7,000 deaths from medication, 80,000 from nosocomial infections, and 106,000 from "non-error adverse effects". He then asserted that these figures are "restricted information" and is "not published in general". He claimed that in order to read this study, he had to state he was "Dr. Blake" in order to get to the web site, because it was only available to doctors and not to the general public. A participant from the audience stated that the results of such a study would never be published in the local paper, the Kitchener-Waterloo Record.

[The claim about "restricted information" is false. There was no need for Prof. Blake to represent himself as "Dr. Blake" in order to gain access, as our university has a subscription to JAMA (the Journal of the American Medical Association), which is available for free to all members of the university community. In a few minutes, I was able to find the "study" Prof. Blake was referring to. It is not a study, but a "commentary" by Barbara Starfield [JAMA, Vol. 284, No. 4 (2000), 483-485] that discusses a study, "To Err is Human", published by the Institute of Medicine in 1999. Contrary to Prof. Blake's assertion that this was "restricted information" and the participant's claim that the results would not be published in our local paper, I was able in a just a few minutes to find dozens of references to the study in mainstream media, including one in our local newspaper.]


Prof. Blake then went to discuss his sister, who died "because she had diabetes and her liver was irreversibly damaged from medication".

He then discussed results on acupuncture: 50-90% report relief. Tai Chi is also useful.

He cited a study that said religious practices are useful in lowering depression [Braam, Psychological Medicine V. 31 No. 5 (2001), 803-814]. He talked again about "energy" and I asked what he meant by energy.

Prof. Blake stated that energy is a "wave pattern" that makes up our bodies. When we are sick, it is because our organs are "not vibrating at the frequency they were designed to operate at". Doctors are working on that, he alleged. The laying on of hands works because it "corrects malfunctioning energy". But you can't always tell if healing works, because according to the uncertainty principle, introducing a measurement changes the way the system operates.

He described a man with severe knee problems that he saw. The man came in with a cane, Prof. Blake laid hands on him and said a benediction, and the man walked out without his cane. People live healthier lives with religion.

Audience members asserted that "drug companies were only interested in profits".

Prof. Blake asserted that "Einstein was a very religious person" and "wanted scientists to become more religious".
[ I pointed out that what Einstein meant by religion was not what most people meant. For example, Einstein said in a 1954 letter, "It was, of course, a lie what you read about my religious convictions, a lie which is being systematically repeated. I do not believe in a personal God and I have never denied this but have expressed it clearly. If something is in me which can be called religious then it is the unbounded admiration for the structure of the world so far as our science can reveal it."]

Prof. Blake concluded by saying in the next session, he would discuss how prayers can be more effective and how you can get more consistent results from prayers. In my informal talk with him after the sessions, he asserted that this was due to his special recipe for herbs and oils that one must anoint someone with in order to heal, and the fact that only specially gifted people (presumably Prof. Blake is one of them) have the power to heal.

Tuesday, December 12, 2006

Skeptics Canada Opens an Office

I just received some good news in an e-mail message from Skeptics Canada: they are going to open an office in Toronto starting on January 1, 2007. The office will be at 873 Broadview Avenue, just north of Danforth. This is a great step forward for organized skepticism in Canada. If you're interested in fighting against irrationality in all its forms, consider joining Skeptics Canada.

Friday, December 01, 2006

The Prime Game

First, the game.

Ask a friend to write down a prime number. Bet them that you can always strike out 0 or more digits to get one of the following 26 primes:

2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049.

For example, if your friend writes down 43, you can strike out the 4 to get 3. If your friend writes down 946969, you can strike out the first 9 and the 6's to get 499.

(There's not always a unique way to do this, and of course it works with some non-primes, too: if your friend writes down 35, which isn't a prime, you can strike out the 3 to get 5 or vice versa. But if someone gives you a number where you can't strike out some subset of the digits to get a prime on the list above, then that number isn't prime. For example, you can't strike out any subset of the digits of 649 to get a prime on the list, but 649 isn't prime.)

I published this strange result in the Journal of Recreational Mathematics in 2000; there's a copy on my papers page. Believe it or not, there's actually some interesting mathematics behind it.

Let's say that a string of symbols x is a subsequence of a string of symbols y if you can strike out some symbols of y (not necessarily contiguous) to get x. ("Subsequence" seems to be the preferred term in North America, but in Europe they call this a "subword". However "subword" is used in North America to mean "contiguous subblock".) The relation "x is a subsequence of y" is a partial order, meaning it shares the following properties of the ordinary <= relation on integers:

  • x is a subsequence of x;

  • If x is a subsequence of y and y is a subsequence of x, then x=y.

  • If x is a subsequence of y and y is a subsequence of z, then x is a subsequence of z.

We now call two strings comparable if x is a subsequence of y, or vice versa; otherwise, we say x and y are incomparable. A set is pairwise incomparable if every pair of elements is incomparable.

Now, a very neat result about the subsequence partial order is that every pairwise incomparable set is finite. This isn't obvious, and it isn't true for every partial order. (For example, it isn't true for the order where "subsequence" is replaced by "subword".) You may enjoy trying to prove this.

We need one more concept: the minimal element. A string x in S is said to be minimal for S if whenever y in S is a subsequence of x, then y=x. Given a set of strings S, it's not hard to see that the set of minimal elements of S is pairwise incomparable. So it must be finite. And every string in S has the property that some minimal element is a subsequence of it.

Now, to get the prime game, let S be the set of strings representing primes in base 10. The list of 26 primes above is the set of minimal elements for S.

Determining the set of minimal elements isn't always easy. For example, if instead of the primes we use the decimal representations of the powers of 2, then no one currently knows how to compute the set of minimal elements. It's probably {1,2,4,8,65536}, but proving this seems quite hard.

A neat consequence of this result is that, given any language L, the set of all subsequences of strings in L is regular. We can't always easily determine the regular expression or automaton for L, but we know it exists.

Here's a link to a file of cards you can print, cut out, and perhaps laminate, with the prime game on them. Enjoy.