by Scott Aaronson
A CAPTCHA (Completely Automated Public Turing test to Tell Computers and Humans Apart) is a test that a computer program can generate and grade, and that humans can pass, but that current computer programs cannot pass. A user might be asked, for example, to pick out three words in the following image:
Such tests are used by Yahoo! and other Internet portals to deter robots from abusing their services, for instance by registering for thousands of free email accounts and then sending spam from them. For more on CAPTCHAs, see www.captcha.net or an excellent NYT piece by Sara Robinson.
The trouble with the current tests is that it's difficult to know how secure they are. Indeed, "Gimpy," the program that generated the above image, was recently broken by Greg Mori and Jitendra Malik at Berkeley. So the obvious question arises, does there exist a CAPTCHA that is unconditionally secure against any machine, present or future?
I am pleased to report an affirmative answer. And no, it isn't the "Voight-Kampff machine" from the movie Blade Runner. Instead it's inspired by the books of Roger Penrose -- The Emperor's New Mind and Shadows of the Mind. You can try out my CAPTCHA below.
Given a formal system F that contains Peano arithmetic, consider the following Gödel sentence, which asserts its own unprovability in F.
Is G(F) necessarily true assuming the axioms of F?