Thursday, October 24, 2013

Eric Hehner's Fringe Computer Science


Fringe science -- making claims, with little evidence, that nearly everyone who works in the field recognizes as wildly wrong -- is nothing new. In archaeology, fringe science includes promotion of artifacts like the Vinland Map (now completely discredited) and the Kensington Runestone (likewise discredited). There are two very good books discussing fringe archaeologists and their "methods": Stephen Williams, Fantastic Archaeology and Kenneth Feder's Frauds, Myths, and Mysteries: Science and Pseudoscience in Archaeology.

You would think that in a field like mathematics, it would harder to be fringe. People don't normally debate whether 1 > 2, or whether ½ is a rational number. Nevertheless, there is a surprising amount of fringy mathematics. I'm thinking, for example, of circle-squarers, who continue to try to construct π with straightedge and compass long after Lindemann's proof that it cannot be done. In 1977, the Journal für die reine und angewandte Mathematik published a fringy proof of Goldbach's conjecture that, needless to say, is not widely accepted.

While most people engaged in fringe mathematics are amateurs, there are a few professionals. It used to be pretty hard to publish fringe mathematics in journals, but with the rise of open access journals of questionable credentials, it has become a lot easier. Not all fringe mathematics is wrong, but most of it is.

Up until now, I hadn't seen too much fringe computer science. But now I have. And to make things worse, we have apparently asked the author of these fringe works to come speak at our university.

The work in question is that of Eric C. R. "Rick" Hehner, an emeritus professor at the University of Toronto. Hehner worked in what is called "formal methods", which concerns logical formalisms for computer science constructs, such as those in programming languages. On his web page, you can find a list of his publications.

Hehner seems to have done some reasonable work in the past, although I'm probably not the very best judge. Some other people apparently disagree. For example, Hehner lists a paper called "Beautifying Gödel" as among his very best; yet the late Torkel Franzen, an expert on Gödel's theorem who published an eponymous book on the subject, said that Hehner's paper "contains some odd misunderstandings" and exhibits "some standard confusion regarding the soundness condition needed".

Lately, however, Hehner's work can, I think, fairly be characterized as "fringe computer science". For example, he claims that our modern understanding of uncomputable problems, such as the halting problem is completely wrong and that the standard proof of unsolvability, taught in nearly every undergraduate course on the theory of computation, is bogus. (Another version of Hehner's claims is here.) As a result, Hehner denies the existence of something he calls the "computability hierarchy" (although he seems a bit confused about what that is). At the end of this piece, Professor Hehner reveals that his focus on the halting problem dates from the 1980's.

Prof. Hehner has recently branched out into another favorite of the fringe mathematician, Cantor's proof of the uncountability of the reals. Prof. Hehner's paper is not the worst anti-Cantorian work I have read --- it seems that, at least, Hehner does accept that Cantor's proof is correct. He just denies that it is reasonable to say that a set A is the same size as set B if A is equipollent with B. (There are other problems with Hehner's paper, such as (1) presenting the minor technicality of some numbers having two different base-k representations as something that has to be "repaired", when in fact this problem simply does not occur in Cantor's proof when correctly presented; (2) claiming the proof is informal when in fact formalizing it is trivial; (3) confusing the notions of cardinality and computability.) But who cares what Prof. Hehner thinks is "reasonable"? There's a lot of beautiful and interesting mathematics that arises from this definition, and mathematicians find it useful. If Prof. Hehner does not, he is free to make a case for a better definition. But he does not, not in any serious way. In this sense, his case is entirely a negative aesthetic one: he doesn't like Cantor's definition, and can't imagine why anyone else would. This is not a basis for good science.

The reception of Prof. Hehner's claims about computability and Cantor -- which would be revolutionary if accepted -- has been, I think it is fair to say, silent or negative. There are only a handful of citations of the relevant papers, mostly self-citations. One exception is this paper by Huizing, Kuiper, and Verhoeff (behind a paywall, probably, if you aren't at a university) which generously takes his work seriously and points out the flaws. If Prof. Hehner has a response, I have not seen it.

Professor Hehner seems unhappy that his work is not treated seriously, and that some people who object to it do not always point out specific problems with his reasoning. But I think he's got it exactly backwards. The uncomputability of the halting problem has a proof, and we teach that proof in most introductory courses in theoretical computer science. The proof doesn't have many steps, the steps are very simple, and it is accessible to any bright junior-high school student. If Prof. Hehner claims that this proof is flawed, then he must point to the exact line of the proof that he disagrees with. Instead, what he does is translate this simple proof -- as in this video -- into his own private language in a flawed way, and then raise several objections to his own translation. This tactic is well-known as the "straw man". It is not a serious scientific attack on our understanding of the problem.

It is our unfortunate duty to host this nonsense at the University of Waterloo at 4 PM on Thursday, November 28, in DC (Davis Centre) 2585. The public is welcome. If it had been up to me, I would not have extended an invitation to Prof. Hehner to speak on this topic because (1) I am not convinced, based on what I've read, that he has a deep understanding of the material and (2) I do not think, based on what I've read, that he has anything interesting to say. But a great feature of a university is that all kinds of ideas, from the well-supported to the fringe, can be discussed.

Sometimes, though, we pay the price.

7 comments:

nwrickert said...

I had not come across Hehner. But I have engaged in discussion, mostly on usenet groups, with people with similarly odd ideas about mathematics. Some of them have a background in computer science.

I have also come across people who think that an accountant is a mathematician. It would not surprise me to find computer scientists with that view.

I suggest you sit back and quietly regard him with amusement during his presentation. It is not worth spending any effort on trying to set him straight.

Unknown said...

One must concede that the guitar is an unusual research instrument in CS. :)

Marty Kalin
Professor, School of Computing
DePaul University

Ramanujan said...

"I didn't call your work "fraud" in my post."

I don't think Hehner claimed you did. All he said was "I'll pass over the parts where you ridicule me by associating me with fraudulent archaeology and people who think 1>2 and circle-squarers."

Hehner writes: "How can I know if I am a crackpot?"
Shallit responds: "I did not use the word "crackpot" there."

It was pretty darn close when you wrote the following: "Prof. Hehner has recently branched out into another favorite of the fringe mathematician, Cantor's proof of the uncountability of the reals." In that sentence was a link to: "theres-almost-more-cantor-crackpottery".

"You also confuse "ire" with 'amusement'."

I challenge any unbiased reader to find anything in your post that portrayed you as amused. Maybe you didn't express ire, but definitely not amusement. To call him "confused" in this case fits your M.O. though.

"I never said a word about your "character", much less "assassinate" anything."

Perhaps you should've tried harder not to mention Hehner's work so soon after writing "People don't normally debate whether 1 > 2, or whether ½ is a rational number." Pointing out such mathematical stupidity points to a mathematician's very being, not just his mathematical prowess.

Jeffrey Shallit said...

Ramanujan:

I can see that you have the courage of your convictions, so much so that you adopt a pseudonym.

If you have to do things like look at the titles of posts by other people that I link to, in order to make your points, that just shows how terribly weak your arguments are. How much more contrived can you get?

If I wanted to use your tactics, I could just as well point out that your use of the expression "M. O." is normally associated with crimes, so you are essentially making a criminal accusation against me.

All this is a distraction from the main point, which I guess is your goal.

Jeffrey Shallit said...

Ramanujan:

Oh, and next time? Try making your comment on the post it refers to.

Jeffrey Shallit said...

Perhaps you should've tried harder not to mention Hehner's work so soon after writing "People don't normally debate whether 1 > 2, or whether ½ is a rational number."

The point, which you evidently missed, was to explain why fringe mathematics is rarer than fringe archaeology, for example: it's because there is usually virtually unanimous agreement about mathematical claims, especially very simple ones.

In my opnion, Hehner's claims about the incorrectness of the standard proof of uncomputability of the halting problem are roughly comparable to denying that 1 = 0.999999... .

Eric Hehner said...

Please see my reply, and Jeffrey's reply to my reply. It is his next post in this blog series.