Conway

John Conway is a British mathematician who studied and taught at Cambridge University and is now a professor at Princeton. In the programming community Conway is best known as the inventor of the Game of Life, one of the earliest examples of cellular automata, but he has made significant contributions to mathematics throughout his career.

In 1969, Conway introduced surreal numbers, which include real numbers and ordinal numbers. Every real number is surrounded by surreals, which are closer to it than any other real number. In 1974, Donald Knuth described surreal numbers in his book Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness. The book is notable because Knuth presents the idea of surreal numbers by way of a fictional dialogue.

In 2004, Conway and Simon Kochen, another Princeton University mathematics professor, proved the Free will theorem. The theorem states that if humans have free will, then elementary particles like atoms and electrons must have free will as well.

Conway is also known for being the inventor of the Doomsday algorithm for calculating the days of the week, the puzzle games Sprouts and Phutball, and for providing all 240 solutions for the Soma Cube.

Conway's recent lectures on mathematics and geometry, including his ongoing (at the time of this writing) lecture series on Free Will and Determinism are available for free download through Princeton University.

Books by John Conway
On Numbers and Games
Winning Ways for Your Mathematical Plays, Vol. 2

Worst CAPTCHA ever?

For those of you who don't know, a CAPTCHA is program that can tell whether its user is a human or another computer. They're those little images of distorted text that you translate when you sign up for Gmail or leave a comment on someone's blog. Their purpose is to make sure that someone doesn't use a computer to sign up for millions of online accounts automatically, or to spam blogs randomly with cries for help from Nigerian princes. They make sure an actual human is filling out the form. They work based on the principle that no computer program can (currently) read distorted text as well as a human can.

I have a confession to make. I fail this scaled-down version of the Turing test on a regular basis. There's probably software out there that can outperform my current success rate of just about 2/3. Then there are those challenges that are impossible for human and computer. Just today I was presented with the following CAPTCHA, presumably containing two words.

The image was presented by reCAPTCHA, probably the best anti-bot service in widespread use on the internet. reCAPTCHA works by taking scanned images from books that Optical Character Recognition (OCR) software finds difficult or impossible read and presenting it in CAPTCHAs deployed all over the internet in order to get humans to read the words that the OCR software can't. The goal is to get a bunch of scanned books efficiently translated into digital form. It's a really clever and elegant solution to two problems in one.

Fortunately for enterprising young programmers, the CAPTCHA half of this problem is far from being solved. The line between what a human can read easily and what a software application can read is blurred and constantly changing. New ideas in the battle against Nigerian princes are always welcome.

---

UPDATE: After receiving a comment from Ben Maurer, the chief engineer at reCAPTCHA (and after Googling him to make sure he really is) it seems I have to eat a little crow. After spending enough time on the reCAPTCHA site for a statistically significant sample, I've determined that the image above is an outlier. My guess is that the word on the left is a scanned image or drop cap. Thanks, Ben, for straightening me out on this.

Bruce Schneier is amused.

I threw a foam brick at my TV set this past Monday evening during 24, at the mention of a backdoor designed into the Blowfish cipher. I'm a long-time fan of the show, but not for its steadfast attention to technical details. The show's creators seem to believe that all you need in order to crack any encryption algorithm is an "open socket" and a high enough security clearance.

Bruce Schneier, the designer of the Blowfish algorithm, was gracious in mentioning the episode on his security blog, even providing an excerpt from the show's transcript.

In a response to a comment, Bruce had this to say:

I've never seen the show, and don't really care to. As to how it feels: it feels surreal. I'm not proud to be mentioned, angry they claimed I put a back door in, annoyed they get the details wrong. If anything, I am amused by the whole situation. It's, well, it's surreal.

I won't be surprised if next season's villain on 24 has a manly beard, twin automatic machine pistols, and the uncanny ability to decrypt a box of Alpha-Bits.

Photo courtesy of Bruce Schneier Facts.

National Pi Day

On Wednesday, the U.S. House of Representatives approved a resolution (H.RES.224) sponsored by Rep. Bart Gordon (D, Tenn.), that officially designates March 14th (3/14) National Pi Day. The resolution is aimed at encouraging "schools and educators to observe the day with appropriate activities that teach students about Pi and engage them about the study of mathematics."

In celebration of this nerdy new holiday, tomorrow I plan to dust off my old copy of A History of Pi, and fascinate my friends and family with choice anecdotes about everyone's favorite transcendental number.

C++ Snippets: Time Part 2

In my previous post about telling time in C++, I showed how to display the current Linux system time in a human-readable format. Today I want to go a little bit beyond that and explain how to customize that format.

If you read my previous post, you saw that the asctime function always returns the time in the same format (Thu Mar 12 18:30:50 2009). That's much better than displaying the time in the number of seconds since January 1, 1970, but it still leaves room for improvement.

I'm going to show you how to create a custom format to display the date and time however you choose using the strftime function from the ctime library. I want to rearrange things so the time above would be displayed as:

Thursday, March 12, 2009 06:30:50 PM

First, let's take a look at the arguments that strftime takes.

char *str - A buffer that will hold the formatted output. Strftime was originally a C function, so we can't just return a string. That's okay, though, we'll just make the buffer big enough to hold any time and date in our specified format.

size_t maxsize – The maximum number of characters that will be copied to the output buffer. This should be the same value as the size of the buffer used as the first input parameter.

const char *fmt – Specifies exactly how we want the time to be formatted. There are some special format codes that I'll go over next, but be aware that normal text can be included as well.

struct tm *time - The time value we want to format.

In order to display the time in the desired format, we'll use the following format specifiers:

%A - full weekday name
%B - full month name
%d - day of the month
%Y - year in (with the century)
%I - hour in 12 hour format
%M - minute as a number
%S - second as a number
%p - locale equivalent of AM/PM

We'll combine all of these format codes together, along with normal text delimiters (commas, colons, and spaces) to form one long format string.

%A, %B %d, %Y %I:%M:%S %p

Finally, here's the code:

#include <iostream>
#include <ctime>

using namespace std;

int main ()
{
  struct tm * timeinfo;
  char buffer [80];
  time_t seconds = time(NULL);

  timeinfo = localtime( &seconds );
  char format[] = "%A, %B %d, %Y %I:%M:%S %p";

  strftime(buffer, 80, format, timeinfo);
  cout << "Local time: " << buffer << endl;

  return 0;
}

After compiling the code snippet above, you should see output similar to the following:

$ ./a.out
Local time: Thursday, March 12, 2009 06:53:13 PM