Sam Trenholme's webpage
Support this website

The Galileo 7


November 5 2011

There is a classic episode from the original Star Trek named The Galileo Seven where Spock discovers that acting in a perfectly logical way while assuming others are just as logical does not work in the real world.

Likewise, the type of thinking used to solve logic puzzles like the the village adultery puzzle does not correspond to the thinking used to write a real-world program. In the village adultery puzzle, the "correct" solution is found only when one buys the flawed assumption that all of the women are perfectly righteous as well as perfectly rational, and that each woman can safely assume all of the other women will think exactly like her.

With real people in the real world, this never actually happens.

For example, when developing Deadwood, if I were able to use the same thinking used to solve a Smullyan-style puzzle, the program would have been finished years sooner than it really was. A lot of the testing and tuning of Deadwood is working around DNS servers whose behavior is anything but logical.

While these kinds of logic puzzles are fun, and can be solved with a bit of thinking once the assumption that everyone acts perfectly logically and knows everyone else acts perfectly logically is understood, they have little real-world value. When developing Deadwood, there were only a couple of times where I was able to come up with something really clever (the hash compression function and the prime number used to determine which DNS server we should contact next, as well as surveying the cryptographic literature to find a good secure pseudo-random number generator). Most of the coding was somewhat tedious detail work implementing small and simple versions of all of the libraries a recursive cache DNS server needs (the string libraries, the LRU used for storing cached records, associative array support, the DNS compression code, etc.)

Unfortunately, there is a somewhat incorrect idea that a good programmer is also trained to solve these kinds of logic puzzles. Some companies will ask a question like this during the interview, and will not hire someone who does not know how to solve such a puzzle.

In today's job market, I realize that there is a small but distinct chance that someone will ask me a question like this during the interview, which is why I have gone to the effort to figure out how these puzzles are constructed and what logic to use to solve them.

To post a comment about an entry, send me an email and I may or may not post your comment (with or without editing)