Tuesday, October 29, 2013

More Bad Math in a Jack Reacher Novel

This is getting to be a series! In 2007 I criticized Lee Child's Jack Reacher hero for suddenly gaining the ability to perform lightning mental calculation, and for treating boring problems as if they were mathematically significant. Last year, I pointed out that (at least in one edition) Jack computed the decimal expansion of 1/81 incorrectly.

Well, happy 53rd birthday to Jack, who was born on October 29 1960. But I can't help complaining about yet another mathematical error, this time in Child's latest book, Never Go Back. On page 379 of the Canadian edition, Reacher muses,

"His ears had the center whorls intact like any other guy, but the flatter parts around them had been cut away, probably with scissors, very tight in, so that what was left looked like pasta, like uncooked tortellini florets, shiny, the color of a white man's flesh. Not exactly hexagons. A hexagon was a regular shape, with six equal sides, and Shrago's stubs had been trimmed for extreme closeness, not geometric regularity. They were irregular polygons, more accurately."

Sorry, but a hexagon is not necessarily a "regular shape"; that would be a regular hexagon. A hexagon is any polygon with 6 sides; there's no symmetry implied.

Sunday, October 27, 2013

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.

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.

Wednesday, October 23, 2013

They Offer Nothing But Lies, 4

I only had the chance to catch about 15 minutes of Stephen Meyer on the Michael Medved show today (and of that 15 minutes, probably about half the time was devoted to ads -- how do people stand listening to that?), but in that brief time I heard three lies.

Meyer made his usual false claim about "information" and how it can't be generated through evolution. Of course it can; any random process will generate "information" in the sense used by mathematicians and computer scientists. The creationist version of "information" espoused by Meyer is different, but even there it is easy to see that mutation can generate it (take a program that does something and change one character so it doesn't compile; then a mutation that restores the function will create creationist information).

Meyer made a false claim about Dawkins only being interested in genes and not being interested in organisms. Of course, that's a lie, and anyone who has read Dawkins (e.g., The Extended Phenotype) knows this to be the case.

Meyer also repeated his usual lie about how "Darwinists" expected there to be junk DNA and how recent findings by "ID scientists" (as if there is such a thing!) show the Darwinists to be wrong. (Larry Moran has discussed this false claim many times, so there's no point to discussing it again.)

Three lies in 15 minutes. That's pretty good, even for Meyer.

Monday, October 21, 2013

Suspect Journals

The new "open access" movement has spawned too many doubtful journals. Here's a useful list of suspect journals and publishers.

Saturday, October 19, 2013

Local 9/11 "Truthers" Make Documentary

I'm sorry I missed the event last week where the local 9/11 truthers presented their truther "documentary".

It amazes me that there are folks who are still flogging their silly conspiracy theory, and that some people actually take them seriously. That Osama bin Laden was responsible for 9/11 is documented in great detail in books like The Looming Tower and is established beyond reasonable doubt.

To get some idea of the ragtag bunch of people who endorse this crap, take a look here: a professor of public administration, a professor of economics, a professor of physics, a professor of economics, a professor of mathematics, and a professor of English. Not a single person with any expertise in politics, Middle East studies, architecture, or building design among the endorsers.


Friday, October 18, 2013

Discovery Institute Hires World's Worst Journalist™

Exciting news! The Discovery Institute, not content with such luminaries as Casey Luskin, John G. West, and David Klinghoffer, has reached even further into the bottom of the barrel.

Yes, believe it or not, they've hired Denyse O'Leary, the world's worst journalist™, to write for them.

We can look forward to hours of fun: mangled syntax, clichés, punctuation chosen at random, repetition of signature buzzwords like "Brit toff" and "tenure bore", unfounded accusations of racism and Nazism against reputable scientists, neologisms that only O'Leary understands, and a thorough misunderstanding of anything she discusses -- not to mention that Denyse never ever interviews anyone she disagrees with.

Congratulations to both the DI and Denyse! You definitely deserve each other.

Tuesday, October 15, 2013

The Pleasures of Editing a Journal

The following exchange is fictional, but not by much. It is based on several different experiences I've had as editor of the Journal of Integer Sequences.

From Joe Smith:

Here is my submission, entitled "1 + 1 = 2", to the Journal of Integer Sequences. It gives a simple, new, and cute proof of this famous theorem which I know you will want to publish.

My response:

I'm sorry, this is simply too trivial to publish in the Journal.

Smith's response:

How disgraceful that an honest person seeking to publish their work in a forum belonging to an elite that think they hold the absolute truth, and deliver their decision based on an incredibly deprecatory pseudo review, are frustrated by your dishonest response!

I will give you one week to accept this paper. If not, I will destroy the reputation of the Journal.

My response:

I'm sorry, the decision stands.

Smith's response:

Can you please suggest another journal where I can publish my result?