Quines II

In my first real post, I mentioned that I was reading Gödel, Escher, Bach: an Eternal Golden Braid, by Douglas Hofstadter. I promised that as soon as I got to the section on quines (the subject of that first post) I’d write a followup about what Hofstadter thought about self-replicating programs. Unfortunately, I read right through that section, entirely forgetting about my promise. In this post I plan to atone for my forgetfulness and talk about Hofstadter’s take on quines, but only after taking a few paragraphs to wax enthusiastic about the book.

I first remember hearing about GEB from my intro computer science instructor. He said that it’s the kind of book everyone’s begun at one point or another, but that almost no one ever makes it all the way through. This isn’t that surprising; the book is 742 pages long, not counting the notes, index, or annotated bibliography. When my parents bought it for me this winter, then, of course I had to make sure I read it cover to cover. As soon as I finished the book I was reading at the time, I picked it up and vowed not to start another book until I had finished GEB.

At long last, after seven months of sneaking a few pages wherever I could, all too often long after I should have been asleep¹, that time has come. On Friday the thirteenth of July, 2007, I read the final page of the final (hilarious) dialog between Achilles, Mr. Tortoise, the Crab, the Author, Charles Babbage, and Alan Turing. Moreover, I had successfully managed to avoid reading another book during the entire time² I was reading GEB.

It really is excellent. While Hofstadter’s mostly interested in self-referential loops and the fundamentals of intelligence (there’s a strong connection between the two, at least according to him), he dips into all sorts of fascinating topics along the way. This includes, as the title suggests, math, visual art, and music. Although the book does deal with artifical intelligence and touches a bit on programming, this by no means limits the breadth of people who would be interested in it. I heartily recommend it to anyone who enjoys a good think now and then, and especially to those fond of word games, puns, and puzzles.

On to quines. The first thing I noticed upon reading Chapter XIV and the dialog before it, Air on G’s String, was that Hofstadter didn’t actually coin the term “quine.” Or rather, he did, but he used the term to mean something other than a self-reproducing program.

One of the things Willard Van Orman Quine is famous for is a particularly tricky sentence. It is as follows:

“yields falsehood when preceded by its quotation” yields falsehood when preceded by its quotation

Is this sentence true? Think about it. If it is true, then when the sentence “yields falsehood when preceded by its quotation” is preceded by its quotation, it’s false. But we just supposed that that very sentence was true! This is a contradiction, so it must be the case that the tricky sentence is false, right? Well, if it’s false, then when the sentence “yields falsehood when preceded by its quotation” is preceded by its quotation, it’s true. Another contradiction! Whatever shall we do?

This is actually an undecidable sentence. It is neither true nor false. It’s very similar to the classic Epimenides paradox, “this sentence is false.” The tricky bit is that Quine’s sentence doesn’t explicitly use the term “this;” it refers to itself indirectly, by referring to its quotation³.

What does all this have to do with GEB? Well, what Hofstadter actually defines the word “quine” to mean is “to precede a sentence with it’s quotation.” Not only is this not the same thing as a program that reproduces itself, it’s a whole different part of speech. Using Hofstadter’s definition, you might say:

Quine quined the phrase “yields falsehood when preceded by its quotation”

Hofstadter introduces this definition in quite an amusing way. The term is actually coined by a character in one of his dialogs, Mr. Tortoise:

I believe I’ll call it “to quine a phrase”, to quine a phrase⁴.

Interestingly, the attribution to Hofstadter of the use of “quine” to mean “a self-replicating program” isn’t entirely random. Two chapters after the dialog in which he quines coins the phrase, he talks about what he calls “self-reps.” These are what are now known as quines: programs which print themselves. He gives an example in an example language of his own creation called BlooP:

DEFINE PROCEDURE "ENIUQ" [TEMPLATE]: PRINT [TEMPLATE, LEFT-BRACKET,
QUOTE-MARK, TEMPLATE, QUOTE-MARK, RIGHT-BRACKET, PERIOD].

ENIUQ
  ['DEFINE PROCEDURE "ENIUQ" [TEMPLATE]: PRINT [TEMPLATE, LEFT-BRACKET,
    QUOTE-MARK, TEMPLATE, QUOTE-MARK, RIGHT-BRACKET, PERIOD].

    ENIUQ'].

This should be reasonably straightforward, even for those unfamiliar with BlooP (which is a set containing most people). The idea is similar to quining a phrase, but backwards (hence the name “eniuq” for the procedure): it’s a sentence followed by its quotation.

I think this is something of a general form for quines. Here it is translated into Ruby:

def eniuq(template)
  print(template, ?(.chr, 39.chr, template, 39.chr, ?).chr)
end

eniuq('def eniuq(template)
  print(template, ?(.chr, 39.chr, template, 39.chr, ?).chr)
end

eniuq')

Of course, this relies on the fact that 39 is the numeric code for a single quote. Hofstadter’s takes a different route; he just had a predefined constant “QUOTE-MARK” that allowed him to avoid that. The principle, though, is the same. In fact, it’s the same principle as Quine’s quine. Self-reproducing programs need a way to refer to the quote character without explicitly using it, just as Quine’s self-contradicting sentence manages to refer to itself without explicitly using the term “this.”

¹ I tended to do most of my reading at hours much like the one at which I’m typing this entry.

² Within reasonable bounds, of course. I did browse a little here and there; the point of the vow was to prevent me from putting off this book to read another, as I so often do, and in that sense I stuck to it entirely.

³ This is actually the principle Kurt Gödel used to prove that mathematics couldn’t be both consistent and complete. I’ll leave you to guess which book I’d suggest you read for more information, but I do suggest following up on my hypothetical suggestion. Gödel’s theorem is wonderful.

⁴ I’ve never understood the bad rap puns always get. I’ve always thought that puns, when done well, were one of the most clever sorts of jokes. They allow you to pack much more meaning into a single word than you would otherwise have been able to, while being funny to boot.