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. I describe Turing machines in more depth in my informal explanation of the P=NP? problem.

Let’s say that we have a Turing machine that outputs a description of itself. QUINE, our Turing machine, has two parts, C and D. Both C and D are themselves Turing machines. 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 a description of C onto its tape. Let’s refer to that description of C as [C].

C reads [C] off D’s tape and computes the function q([C]). q(w) is the description of a Turing machine that outputs w. So, after C computes q([C]), C has the description of a Turing machine that outputs [C]. But that’s D! So, now C can output a description of D.

Where does q(w) come from? In fact, q(w) is easy to compute. Given any string w, it is easy to construct a Turing machine that outputs w. The Turing machine simply ignores any input and outputs w onto its tape.

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. You can see that each program is divided into two parts. There is code that processes the contents of a variable, and the variable stores a representation of the code.

To verify that the C program is a quine, type the following commands at the terminal:

gcc -o quine quine.c    
diff <(./quine) quine.c    

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

diff <(python quine.py) 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.

To see more programs that I’ve written for this blog, visit my GitHub.