

For example, consider the following C program:
Although C presents a powerful (Turing Complete) computational model, we should not see that as imperative to building a quine. The only property necessary for building a quine in the presented construction of a computational model is the ability to substitute an expression.
Please note that the underlying theory is completely given by Kleene's Recursion Theorem[1]; the only purpose of this article is to demonstrate a derivative of its proof in a way easily accessible to students of computation. A similar proof for Turing Machines is available at [3].
Tupper's Formula
Jeff Tupper has presented the following ingenious function[2]:
![]() |
(1) |
It is defined over
, and its image is
.
If we take and plot the function in a rectangle of the
form
, the resulting plot will be a
bitmap of the bit representation of
, spread over lines of length
. The details of how it works are left to the reader as an easy
exercise.
Tupper proceeded to plot the function for a (relatively big)
and
, so chosen that the resulting plot is a plot of
itself. His usage is not self-referential in the sense that the information
necessary for the plot is provided as an input to the computation
-
.
In light of that, we're compelled to ask the following question: is
it possible to construct a formula that would plot its own representation
around the origin ?
Plan of Action
Let's analyze how the aforementioned C quine works:
- It encludes a string that represents the whole body of the quine, and has itself escaped;
- It prints the string twice: once as a body and once as a representation of itself.
- We can encode the bitmap representation of an algebraic expression
as a number;
- We can make a formula
that is able to draw a number as a bitmap in the given rectangle.
- Using
, we can make a formula
that knows how to plot arbitrary binary numbers (i.e., produce a graph that looks like ``
'')
- We can make a formula
- Using
and
, we can make a formula that prints a number twice: once as a bitmap, and one in its number representation.







It evaluates to



Technical Details
The two technical goals for this section are to find algebraic expressions
for and
as required above.
The following expression represents the th bit of a number:
![]() |
(3) |
Let us then define the generalized Tupper function as a function of



![]() |
(4) |
This function will plot the desired number in the rectangle of
height
and arbitrary width. The zeroth bit of
will be at
the lower-left corner (if we use Cartesian coordinates), the first
will be above it, and the
th will be to the right of the 0th.
An undesirable quality of is the fact that it
-periodical
in y, that is
. Since we want to draw
bitmaps inside a rectangle, we will need to confine it to
- that is, to multiply it by a function
that is
for
and 0 elsewhere. One simple way of defining it is:
![]() |
(5) |
Where is Kronecker's delta (defined as:
). Then the following function will draw a given bitmap
of a
given height
with its lower-left corner at the origin
.
![]() |
(6) |
It will be useful to us next to learn how to draw a bitmap starting
with any point, and not just the origin. In order to do that, we will
add 2 more parameters, which we will call and
:
![]() |
(7) |
This concludes our original goal of being able to draw a bitmap at any point in the screen.
In order to draw numbers (in a binary representation), we will begin
with bitmap that contains a representation of the numeral
0 and
which contains a representation of the numeral
.
Let's assume they both have the height
and width
.
Let's say we want to plot a sequence of digits for
,
beginning with the point
. Then if
, we
may draw it as
![]() |
(8) |
And if , we may draw it as
![]() |
(9) |
To make a generic formula, we'll again use the function:
In order to display the sequence for all s, we'll sum the
expressions of the form (10):
![]() |
(11) |
In order to display the first bits of the number
, we'll
just replace
with
:
![]() |
(12) |
This concludes our second technical goal of finding an expression
for .
Final Remarks
Since the expressions above are quite lengthy, even if not complex,
there does not seem to be a particular didactic purpose in writing
down the formula (2) down to the last
symbol. Judging by all the formulas in this article fitting on a single
computer screen, the author considers it likely that the bitmap for
(2) would require no more than
pixels.
In conclusion several more question may be posed:
- Is it possible to ``compress'' the bitmap, so that less bits are necessary to display formulas? Would it necesserily require recursion?
- Is it possible to present the equation in inline form, that is avoiding
the ``for
'' clause?
Bibliography
- 1
- Wikipedia entry for ``Kleene's Recursion Theorem'',
http://en.wikipedia.org/wiki/Kleene's_recursion_theorem, fetched
on February 23rd, 2007.
- 2
- Wikipedia entry for ``Tupper's Self-Referential
Formula'', http://en.wikipedia.org/wiki/Tupper's_self-referential_formula,
fetched on February 23rd, 2007.
- 3
- ''Quines and the recursion theorem'', http://www.cs.pomona.edu/ joev/courses/f05/cs081/supplements/recursion.pdf, fetched on February 23rd, 2007.
About this document ...
Construction of a Quine using real functionsThis document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 -font_size 14pt Tupper-English.tex
The translation was initiated by Uri Yanover on 2007-03-17