Quines

A quine is a computer program that prints its own source code. Writing a quine is not as easy as you might think.

To learn how to write quines, I made use of David Madore’s discussion of quines and Introduction to the Theory of Computation, by Michael Sipser. However, I prefer Sipser’s discussion. I found it to be a lot clearer than Madore’s.

Sipser does not talk about computer programs. Instead, he talks about Turing machines. A computer program corresponds to a Turing machine. So, a quine corresponds to a Turing machine that outputs a description of itself.

Let QUINE be a Turing machine that outputs a description of itself. QUINE has two parts, C and D, each of which is itself a Turing machine. C outputs a description of D, and D outputs a description of C. So, QUINE outputs a description of its entire self.

D runs first. D outputs onto its tape a description of C. Refer to that description of C as <C>.

Let q(w) be the description of a Turing machine that outputs w. q(w) is a computable function. In fact, given any string w, it is easy to construct a Turing machine P_w that outputs w. On any input, P_w simply outputs w onto its tape, ignoring the input.

Now, C reads <C> off D’s tape. Then C computes q(<C>). So, now C has the description of a Turing machine that outputs <C>. But that’s D! So, now C can output a description of D.

So, a quine has two parts, the code and the data. The data represents the code. The code uses the data to print the code and the data.

I wrote a quine in C and a quine in Python. To verify that the C program is a quine, type the following commands at the terminal:

gcc -o quine quine.c
./quine > qoutc
diff qoutc quine.c

To verify that the Python program is a quine, type the following commands:

python quine.py > qoutp
diff qoutp quine.py

You will find in both cases that diff produces no output, which means that there are no differences between the programs’ outputs and their source code.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s