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.