Eric Hehner Replies

Eric Hehner apparently could not figure out how to post this reply to my blog because of some character limit, so he asked me to post it. Here it is. I'll reply below.

---

Wow! I merit a tirade by Jeffrey Shallit. Thank you, Jeffrey. I hope your blog piques interest in my upcoming lectures. You have kindly included links to the work in question, so I hope people will read the work and judge for themselves, rather than accept your opinion.

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. Your first direct volley is aimed at my paper “Beautifying Gödel”. The title comes from the fact that the paper was a contribution to a book titled Beauty is our Business. I set out to write the simplest, most elegant presentation that I could of one of Gödel's theorems. The paper does not suggest that there is anything wrong with Gödel's theorem. The simplifications come from our modern familiarity with the character string data type (so we don't have to encode programs as integers) and with programming language interpreters; these were unknown to Gödel. My presentation has been used by various authors and textbook writers (e.g. What Computing is All About, a textbook used at CalTech).

I am a fan of Torkel Franzén and his wonderful book Gödel's Theorem: an Incomplete Guide to its Uses and Abuses. His criticism of my paper was very mild (especially compared to his pointed criticisms of almost everything else). It seems to arise because he, like most mathematicians, is a platonist (he believes mathematical objects exist, independent of people; we just try to find out some truths about them) whereas I am a formalist (I believe mathematics is a formal language created by people to describe some aspects of the world). In particular, soundness is stated differently. Perhaps formalist mathematicians are “fringe”; if so, it's an august group that I am happy to be part of.

You cite my paper “the Size of a Set” as fringe mathematics. You say I deny “that it is reasonable to say that a set A is the same size as set B if A is equipollent with B”. Then a few sentences later, you say “But who cares what Prof. Hehner thinks is “reasonable”?”. When you quote the word “reasonable”, you are quoting yourself, not me; the word “reasonable” does not appear in the paper. You say “There are other problems with Hehner's paper”. First, I “present 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”. Your comment is entirely unfair. I first present the popular form of the proof, point out the problem, and repair it. I agree that the problem does not occur when the proof is correctly presented.

The next problem, you say, is that I “claim the proof is informal when in fact formalizing it is trivial”. The wordy proof is informal, and I formalize it. How is that a problem?

Finally, you say I “confuse the notions of cardinality and computability”. I most certainly do not. I present two analogous arguments, and point out the important difference that one talks about “having” a list, and the other about “generating” a list. Your criticisms are false and unfair.

Here is the conclusion of my paper; judge it, remembering that I speak from a formalist point of view: “It is popularly believed that Cantor's diagonal argument proves that there are more reals than integers. In fact, it proves only that there is no onto function from the integers to the reals; by itself it says nothing about the sizes of sets. Set size measurement and comparison, like all mathematics, should be chosen to fit the needs of an application domain. For all application domains that I know of, Cantor's countability relation is not the most useful way to compare set sizes.” How does that conclusion draw such ire?

Now let's get to the papers that upset you most: my claim that Turing's proof of the incomputability of the Halting Problem has serious flaws. You say: “If Prof. Hehner claims that this proof is flawed, then he must point to the exact line of the proof that he disagrees with.”. Yes! That is precisely the content of the paper (although it's not just a single line that I find fault with). Continuing, you say “Instead, what he does is translate this simple proof into his own private language in a flawed way, and then raise several objections to his own translation.”. By “translate” you mean formalize the proof. The “own private language” is the assignment statement, if-then-else, and while-loop. They are the basis for all current popular languages. I chose the language because it is standard. As for “in a flawed way”, formalization makes clear one's understanding of an informal, English-language proof, and one can never be sure that one has formalized correctly. After I had done my formalization, I read the formalization in Boyer and Moore's paper “a Mechanical Proof of the Unsolvability of the Halting Problem” JACM 31, 3, 441-458, 1984. I was delighted to see that they had formalized the problem the same way I had (except that they used LISP). That gave me confidence in my formalization. I added a section on the Boyer and Moore formalization and proof to my paper.

You say I “seem a bit confused” about what the computability hierarchy is. The paper begins with a very clear construction of the hierarchy. [Dear reader: judge for yourself.]

You cite a paper by Huizing, Kuiper, and Verhoeff, “which generously takes his work seriously and points out the flaws. If Prof. Hehner has a response, I have not seen it.”. So here is my response. I was the (one and only) referee for this paper; I accepted it. It makes good, valid points, and does not invalidate my paper, although they thought then that it did. I spent some time talking with them at the Turing100 celebration in Manchester last year. They suggested another way I could present my case; it became the paper “Reconstructing the Halting Problem”, which you cited.

How can I know if I am a crackpot? On the one hand, a person whose work and opinions I respect, Jeffrey Shallit, tells me so. On the other hand, there's a wonderful book named the Experts Speak by Navasky and Cerf that has a long list of major scientific achievements that were ridiculed by the reigning scientists (the “experts”) of the time. Usually, one is not called a “fringe” scientist just for making a mistake (I don't think I have made a mistake, but I can't be sure). You call me “fringe” because I am challenging an established result of computer science. One way science is distinguished from religion, at least in principle, is by not having any sacred truths that must not be challenged. Unfortunately, I am discovering, some scientists treat some of their truths as sacred, and become quite upset when they are challenged. Challenging sacred truths can be dangerous to one's reputation and career: the priests who protect their truths will attempt to assassinate your character by writing insulting blogs. That's why I waited until retirement to pursue this topic. Here is the real danger: if challenging basic accepted results becomes too costly (it's not easy to bear the insults), science loses its self-correcting character that distinguishes it from religion.

“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.” See you there!

---

My reply:

Eric Hehner:

You seem confused. I didn't call your work "fraud" in my post, I did not use the word "crackpot" there, and I never said a word about your "character", much less "assassinate" anything. For all I know you're probably a nice guy who is kind to your pets. My post was about your work, not you. I think your work on the topic of Cantor and Turing is junk, and I said so.

I'm certainly uninterested in a long back-and-forth about this, but I will say a few things. Your work (and the venue you publish it in) speaks for itself, I think. You also confuse "ire" with "amusement"; I think your criticism of Cantor's work is trivial, silly, and is likely to be completely ignored for those reasons and others.

Your presentation of the proof of the unsolvability of the halting problem (on page 1 of "Problems with the Halting Problem") is not the one I present in class. It is also not the one in any standard textbook on the subject that I looked at (e.g., Sipser, Hopcroft and Ullman, etc.). You certainly do not take the standard proof and point to the exact line that you disagree with. That is your obligation, and you didn't fulfill it.

Blogs are not the place to reply to the Huizing et al. paper. If you contest their conclusions, publish a paper specifying exactly where they went wrong. That's the "self-correcting" nature of science you seem to think highly of.

the priests who protect their truths will attempt to assassinate your character by writing insulting blogs: oh, please. I'm not a priest, just a guy with a blog who is pointing out your silly claims and is sorry that my university is giving you a venue. I didn't say anything about your character. By the way, you forgot to compare yourself to Galileo.

science loses its self-correcting character: you're confused. The self-correcting character is precisely that you offered a bogus refutation of the standard proof, and I'm pointing out that your refutation is bogus.