Wednesday, November 26, 2014

Barry Arrington: A Walking Dunning-Kruger Effect

The wonderful thing about lawyer and CPA Barry Arrington taking over the ID creationist blog, Uncommon Descent, is that he's so completely clueless about nearly everything. He truly is the gift that keeps on giving.

For example, here Barry claims, "Kolmogorov complexity is a measure of randomness (i.e., probability). Don’t believe me? Just ask your buddy Jeffrey Shallit (see here)".

Barry doesn't have even a glimmer about why he's completely wrong. In contrast to Shannon, Kolmogorov complexity is a completely probability-free theory of information. That is, in fact, its virtue: it assigns a measure of complexity that is independent of a probability distribution. It makes no sense at all to say Kolmogorov is a "measure of randomness (i.e., probability)". You can define a certain probability measure based on Kolmogorov complexity, but that's another matter entirely.

But that's Barry's M. O.: spout nonsense, never admit he's wrong, claim victory, and ban dissenters. I'm guessing he'll apply the same strategy here. If there's any better example of how a religion-addled mind works, I don't know one.

Sunday, November 23, 2014

The "Call for Pagers"

This is an actual solicitation I just received:

ijcsiet journal call for pagers november 2014

International Journal of Computer Science Information and Engg., Technologies


Dear Authors,

We would like to invite you to submit quality Research Papers by e-mail or or both. The International Journal of Computer Science Infor! mation and Engineering Technologies (IJCSIET).. As per the guidelines submit a research paper related to one of the themes of the Journals, as per the guidelines.

These solicitations seem to be competing to see who can have the stupidest-named journal and the most typographical errors in a single message.

Monday, November 17, 2014

It Takes One

So David Berlinski thinks climate scientists are "intellectual mediocrities and pious charlatans".

Well, he should know, since I suspect he might hold Official Membership Cards in both groups.

If you want to see intellectual mediocrity and charlatanism, just read Berlinski's essay "Gödel's question" in the creationist collection Mere Creation, published by that well-recognized press devoted to research in advanced mathematics and science, InterVarsity Press.

If you can't figure out what is wrong with it, you can read Jason Rosenhouse's takedown.

Saturday, November 15, 2014

Kirk Durston Does Mathematics!

Kirk Durston is a local evangelical Christian who likes to construct unconvincing arguments for his faith. Every few years he trots them out at my university.

Here is one of his more recent attempts, a discussion of infinity. Not surprisingly, it is a confused mess.

Durston's argument is based, in part, on a distinction that does not really exist: between "potential infinity" and "completed infinity" or "actual infinity". This is a distinction that some philosophers love to talk about, but mathematicians generally do not.* You can open any contemporary mathematical textbook about set theory, for example, and not find these terms mentioned anywhere. Why is this? It's because mathematicians understand the subject well, but -- as usual -- many philosophers are extremely muddled thinkers when it comes to infinity.

Here is how Durston defines "potential infinity": "a procedure that gets closer and closer to, but never quite reaches, an infinite end". So, according to Durston, a "potential infinity" is not a set but a "procedure". Yet the very first example that Durston gives is "the sequence of numbers 1,2,3, ... gets higher and higher but it has no end". The problem should be clear: a "sequence" is not a "procedure"; a (one-sided infinite) sequence over a set S is a mapping from the non-negative integers to S. From the beginning, Durston is quite confused. His next example is "the limit of a function as x approaches infinity". But a "limit" is not a "procedure", either. Durston also doesn't seem to understand that limits involving the symbol ∞ can be restated to avoid it entirely; the ∞ in a limit is a shorthand that has little to do with infinite sets at all.

He defines "actual infinity" or "completed infinity" as "an infinity that one actually reaches", which doesn't seem to have any actual meaning that I can divine. But then he says that "actual infinity" or "completed infinity" is "just one object, a set". Fair enough. Now we know that for Durston, an "actual" or "completed" infinity is a set. But what does it mean for a set to "reach" something? And if we consider the set of natural numbers, for example, what does it mean to say that it "reaches" infinity? After all, the set of natural numbers N contains no number called "infinity", so if anything, we should say that N does not "reach" infinity.

But then he goes on to say "First, a completed countable infinity must be treated as a single ‘object’." This is evidently wrong. For Durston, a "completed infinity" is a set, but that doesn't prevent us from discussing, treating, or thinking about its members, and there are infinitely many of them.

Next, he says "it is impossible to count to a completed infinity". That is true, but not for the reason that Durston thinks. It is because the phrase "to count to a set" is not defined. We never speak about "counting to a set" in mathematics. We might speak about enumerating the elements of a set, but then the claim that if we begin at a specific time and enumerate the elements of a countably infinite set at, say, once a second, we will never finish, is completely obvious and not of any interest.

Next, Durston claims "one can count towards a potential infinity". But since he defined a "potential infinity" as a procedure, this is clearly meaningless. What could it mean to "count towards a procedure"?

He then goes on to discuss four requirements of an infinite past history. He first asserts that "the number of seconds in the past is a completed countable infinity". Once again, Durston bumps up against his own claims. The number of seconds is not a set, and hence it cannot be a "completed infinity" by Durston's own definition. Here he is confusing the cardinality of a set with the set itself.

Next, he claims that "The number of elapsed seconds in the future is a potential infinity". But earlier he claimed that a potential infinity is a "procedure". Here he is confusing a cardinality with a procedure!

Later, Durston shows that he does not understand the difference between finite and infinite quantities: he claims that "the size of past history is equal to the absolute value of the smallest negative integer value in past history". This would only be true for finite pasts. If the past is infinite, there is no smallest negative integer, so the claim becomes meaningless. So his Argument A is wrong from the start.

At this point I think we can stop. Durston's claims are evidently so confused that one cannot take them seriously. If one wants to understand infinity well, one should read a basic text on infinity and set theory by mathematicians, not agenda-driven religionists with little advanced training in mathematics.

* There are certainly some exceptions to this general rule. The "actual"/"potential" discussion started with Aristotle and hence continues to wield influence, even though mathematicians have had a really good understanding of the infinite since Cantor. Cantor met with resistance from some mathematicians like Poincaré, but today these objections are generally regarded as groundless.

Friday, November 14, 2014

Yet Another Dubious Journal Solicitation

This one was spammed to almost everybody in our School of Computer Science here at Waterloo on Wednesday:

Dear Dr. ,

Greetings from the Journal of Advances in Robotics and Automation!

Hope you are doing well!

The Journal is in need of your fortitude. We would like to invite you to send us your valuable contribution (research article, review article, Opinion article, Editorial or short communication), to publish in our journal and improve it for indexing.

It would be highly appreciable if you could submit the article before or till 30 th November. You can visit our journal website for any details

Please submit the article to the below link or you can mail to the below link.

Please help in this Regard.

With Regards,

Rachle Green

Editorial Assistant


All the warning signs are there:

1. Spam sent to everybody without discrimination, including those (like me) who have nothing to do with robotics or automation.

2. Bizarre capitalization like "Regard".

3. Bizarre word choice like "fortitude" and "highly appreciable".

4. Ridiculously rapid deadline for submission.

5. A likely bogus name for the "Editorial Assistant". The first name "Rachle" is extremely uncommon.

I do not recommend having anything to do with this journal.

Wednesday, November 12, 2014

Alan Cobham: An Appreciation

This year, 2014, marks the 50th anniversary of a talk by Alan Cobham that is often regarded as the birth of the class P, the class of polynomial-time solvable problems.

Cobham's invited half-hour talk took place during the Congress for Logic, Methodology and Philosophy of Science at the Hebrew University of Jerusalem, which was held from August 26 to September 2 1964. His paper, which he delivered on the last morning of the conference (September 2), was entitled "The intrinsic computational difficulty of functions". It later appeared in the proceedings of that conference [1], which were published in 1965.

The paper introduces a number of fundamental ideas and questions that continue to drive computational complexity theory today. For example, Cobham starts by asking "is it harder to multiply than to add?", a question for which we still do not have a satisfactory answer, 50 years later. Clearly we can add two n-bit numbers in O(n) time, but it is still not known whether it is possible to multiply in linear time. The best algorithm currently known is due to Fürer, and runs in n(log n)2O(log* n) time.

Cobham then goes on to point out the distinction between the complexity of a problem and the running time of a particular algorithm to solve that problem (a distinction that many students still don't appreciate).

Later in the paper, Cobham points out that many familiar functions, such as addition, multiplication, division, square roots, and so forth can all be computed in time "bounded by a polynomial in the lengths of the numbers involved". He suggests we consider the class "ℒ", of all functions having this property. Today we would call this class P. (Actually, P is usually considered to consist only of the {0,1}-valued functions, but this is a minor distinction.)

He then goes on to discuss why P is a natural class. The reasons he gives are the same ones I give students today: first, that the definition is invariant under the choice of computing model. Turing machines, RAMs, and familiar programming languages have the property that if a problem is in P for one such model, then it is in P for all the others. (Today, though, we have to add an asterisk, because the quantum computing model offers several problems in BQP (such as integer factorization) for which no polynomial-time solution is known in any reasonable classical model.)

A second reason, Cobham observes, is that P has "several natural closure properties" such as being "closed in particular under ... composition" (if f and g are polynomial-time computable, then so is their composition f ∘ g).

He then mentions the problem of computing f(n), the n'th prime function, and asks if it is in P. Fifty years later, we still do not know the answer; the fastest algorithm known runs in O(n½+ε), which is exponential in log n.

He concludes the paper by saying that the problems he mentioned in his talk are "fundamental" and their "resolution may well call for considerable patience and discrimination" --- very prescient, indeed.

Like many scientific ideas, some of the ideas underlying the definition of the class P appeared earlier in several places. For example, in a 1910 paper [2], the mathematician H. C. Pocklington discussed two different algorithms for solving a quadratic congruence, and drew a distinction between their running times, as follows: "the labour required here is proportional to a power of the logarithm of the modulus, not to the modulus itself or its square root as in the indirect process, and hence see that in the case of a large modulus the direct process will be much quicker than the indirect."

In 1956, a letter from Gödel to von Neumann discussed the possibility that proofs of assertions could be carried in linear or quadratic time and asked specifically about the number of steps required to test if a number n is prime. Today we know that primality can indeed be decided in polynomial time.

About the same time, Waterloo's own Jack Edmonds was considering the same kinds of ideas. In a 1965 paper [3], he drew a distinction between algorithms that "increases in difficulty exponentially with the size of the" input and those whose "difficulty increases only algebraically". He raised, in particular, the graph isomorphism problem, whose complexity is still unsolved today.

For some reason I don't understand, Cobham never got much recognition for his ideas about P. (Neither did Edmonds.) Stephen Cook, in a review of Cobham's paper, wrote "This is perhaps the best general discussion in print" of the subject. But, as far as I know, Cobham never got any kind of award or prize.

Cobham did other fundamental work. For example, a 1954 paper in the Journal of the Operations Research Society on wait times in queues has over 400 citations in Google Scholar. In two papers published in 1969 and 1972, respectively [4,5], he introduced the notion of "automatic sequence" (that is, a sequence over a finite alphabet computable, given the base-k expansion of n, using a finite automaton) and proved most of the really fundamental properties of these sequences. And in a 1968 technical report [6] he discussed proving transcendence of certain formal power series, although his proofs were not completely correct.

Alan Belmont Cobham was born on November 4 1927, in San Francisco, California. His parents were Morris Emin Cobham (aka Emin Maurice Cobham) (October 2 1888 - February 1973), a silk merchant, and Ethel Carolina Rundquist (June 24 1892 - Nov 1977), an artist. He had a older sister, Claire Caroline Cobham (June 18 1924 - November 29 2000), who worked for Boehringer-Ingelheim Pharmaceuticals. In the 1940 census, Alan was living in Palm Beach, Florida, where his father was a hotel manager.

Cobham's parents in 1920.

Sometime between 1940 and 1945, Alan's family moved to the Bronx, where Alan attended the Fieldston School. Below is a picture of Alan from the 1945 Fieldston Yearbook.

Alan attended Oberlin College. In the 1948 Oberlin College yearbook, he appears in a photo of the Mathematics Club (below). He is in the front row, 3rd from the right.

Later, Alan transferred to the University of Chicago. He worked for a time in the Operations Evaluation Group of the United States Navy in the early 1950's. He went on to do graduate work at both Berkeley and MIT, although he never got a Ph.D. He also worked at IBM Yorktown Heights from the early 1960's until 1984. One of his achievements at IBM was a computer program, "Playbridge", that was, at the time, one of the best programs in the world for playing bridge; it was profiled in an October 7 1984 article in the New York Times. In the fall of 1984, Alan left IBM and became chair of the fledgling computer science department at Wesleyan University in Middletown, Connecticut, a post which he held until June 30 1988.

I interviewed Alan Cobham in 2010. I was hoping to find out about the reception of his paper in 1964, but unfortunately, he was clearly suffering from some sort of mild dementia or senility, and could not remember any details of his work on P. When I asked him what he did to keep himself busy, he said, "I watch a lot of TV."

Alan passed away in Middletown, Connecticut, on June 28 2011. As far as I can tell, he never married, nor did he have any children.


[1] A. Cobham, The intrinsic computational difficulty of functions, in Y. Bar-Hillel, ed., Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress, North-Holland Publishing Company, Amsterdam, 1965, pp. 24-30.

[2] H. C. Pocklington, The determination of the exponent to which a number belongs, the practical solution of certain congruences, and the law of quadratic reciprocity, Proc. Cambridge Phil. Soc. 16 (1910), 1-5.

[3] J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965), 449-467.

[4] A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory 3 (1969), 186-192.

[5] A. Cobbham, Uniform tag sequences, Math. Systems Theory 6 (1972), 164-192.

[6] A. Cobham, A proof of transcendence based on functional equations, IBM Yorktown Heights, Technical report RC-2041, March 25 1968.

This is a draft of an article I am preparing. I would appreciate feedback and more information, if you have it, about Alan Cobham.

Tuesday, November 11, 2014

Mormon Church Leaders Come Clean? Hardly

A new article in the New York Times suggests that the Mormon Church is suddenly becoming transparent about the more ridiculous and appalling aspects of its history.

As evidence they point to an essay, published on the Church's website, admitting that the Church's founder, Joseph Smith, had as many as 40 wives.

Well, I suppose it's a start, but the reporter is far too generous to the Church. I wonder if we can hope to see some forthright admission that Joseph Smith was a known and convicted conman; that some of the Egyptian documents he claimed to have "translated" are not even remotely what he claimed; that large sections of Mormon holy texts are evidently plagiarized; that DNA evidence clearly shows that the Church's claims about native Americans are without foundation, and so forth.

Nope, we can't. For example, their article on DNA is full of excuses why the definitive results aren't really definitive after all.

Meanwhile, more and more people are leaving the Mormon Church because they can't get honest answers to their questions.

Mormon beliefs, like much of Christianity, are without foundation. The big difference is that Mormonism makes lots of claims that are subject to clear refutation and that the founding of the religion is so recent that its dubious origins are much easier to study.

Saturday, November 08, 2014

Big Surprise: Wind Turbines Not Evil After All

Your tax dollars at work: Health Canada spent $2.1 million to test the wacky proposition that wind turbines have a negative effect on health.

The result should not surprise anyone who spent a few minutes thinking about it: no ill effects were found.

The only reason why they had to do this study at all is likely due to complaints from wacky wind turbine opponents, such as retired pharmacist Carmen Krogh.