A step toward undecidability.

The Church-Turing Thesis tells us everything that can be done can be done by a computer. Cantor diagonalization suggests there are more problems than computer programs, which means there must be some problems we can’t solve. Tomorrow’s post will explore a particular unsolvable problem, but to get there without diagonalization we’ll need to understand quining.

Quine

The word “‍quine‍” was coined by Douglas Hofstadter in honor of Willard Van Orman Quine’s work on indirect self reference and the resulting Quine’s Paradox:

“‍Yields falsehood when preceded by its quotation‍” yields falsehood when preceded by its quotation.

A quine, then, is a technique for embedding self-referentiality without the need for a linguistic notion of “‍self‍” or “‍this‍”. Most often these days the usage is to describe a program as a quine if the program outputs its own source code.

Quines almost always confuse novices to a language. They typically make use of some sort of magic to encode quotation marks in quotations and they also usually use some kind of loop to get the source into a quoted string as well as outside of it.

In the example quine I used both "strings" and “‍strings‍”; most languages use some sort of encoding of characters instead.

Example Quine

x = "

thisProgram = “‍x = "‍” x “‍"‍” newLine x;
		doSomethingWith( thisProgram )

"; thisProgram = “‍x = "‍” x “‍"‍” newLine x; doSomethingWith( thisProgram )

Usable Quines

While most quines are created by curious folk exploring the limits of some language, they also have a useful purpose. They allow programs to perform introspection.

Introspection is a surprisingly useful thing once you have it. For example, the following randomly finds the fastest possible version of itself:

Self-Perfecting Program

repeat forever { if there is work to do { do the work } otherwise { generate a random program x; if x and this program perform the same task { if x is faster than this program { replace this program with x } } } }

There are myriad similar designs one might envision. Actually encoding them requires the use of a quine, but since quines are relatively straightforward to build this is no particular difficulty.

Unfortunately, as I’ll show in the next few posts, actually computing things like if two programs compute the same thing is not doable, in general.