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

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.

### Like this:

Like Loading...

*Related*