An Amusing New Paradox

What could be more amusing than trying to write a program to solve a fiendishly difficult puzzle?

Don Woods, who is well known as the co-author of Adventure (the cave-exploration game that went viral in the 1970s) as well as INTERCAL (the worst-ever programming language), came up with another insanely great and delightfully preposterous creation in 2000 – an innocuous little broadside entitled "Twenty Questions".

Twenty Questions is a multiple-choice exam, which starts out as follows:

"1. The first question whose answer is A is (A) 1  (B) 2  (C) 3  (D) 4  (E) 5."

And the other nineteen questions get progressively worse and worse, leading to a grand climax. The original version of this questionnaire had problems, and it was "cooked" by several people. In fact, the task of finding the best possible list of answers has turned out to be an exceedingly difficult challenge to computer programmers, who haven't been able to avoid bugs in their code. In fact, every one of the many contributors whose work has been published so far has made serious errors. With a small change to Woods's original specification, the questions can now be optimally answered for the first time. But with two more tiny changes, a mystery arises, which challenges everything the speaker thought he knew about logic. He will give an explanation that, thank goodness, resolves the paradox – or does it?

[This lecture is dedicated to George Boole and Ada Lovelace, on the occasion of their 200^th birthdays, as well as to Lewis Carroll, on the 150^th anniversary of Alice's Adventures.]