Quines - computations which produce a representation of themselves - are an intriguing, albeit theoretically uncomplicated class of computational objects. Kleene proved that given a computation model that is: (a) sufficiently powerful (b) has a way of outputting arbitrary constant programs for itself (i.e., by printing them on a tape), there exists a program

that outputs a representation of

For example, consider the following C program:
Image quine

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]:

$\displaystyle T(x,y)=\left\lfloor \mbox{mod}\left(\left\lfloor \frac{y}{17}\rig... ...r 2^{-17\lfloor x\rfloor-\mbox{mod}(\lfloor y\rfloor,17)},2\right)\right\rfloor$

(1)

It is defined over $\mathbb{R}^{2}$ , and its image is $\{0,1\}$ .

If we take $y_{0}=17t$ and plot the function in a rectangle of the form $[0,k]\times[y_{0},y_{0}+17]$ , 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 reproduce this behavior using algebraic expressions. Specifically:

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 ``'')
Using and , we can make a formula that prints a number twice: once as a bitmap, and one in its number representation.

Let's define

as a bitmap representing $P(Q)+N(Q)\:$ for $\: Q=\ldots$ , where the value of

is not given, and

will plot the representation of

at the position of the `` $\ldots$ ''. Then we'll look at the formula

$\displaystyle P(Q)+N(Q)\;$ for $\displaystyle \; Q=b$

(2)

It evaluates to

, that is, a bitmap representation of `` $P(Q)+N(Q)\;$ for $\; Q=b$ '', which is equal to (2).

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:

$\displaystyle b_{i}=\left\lfloor \mbox{mod}\left(t\cdot2^{-i},2\right)\right\rfloor$

(3)

Let us then define the generalized Tupper function as a function of

, that also receives a parameter

- the number to be displayed, and the desired image height

$\displaystyle T_{t,h}(x,y)=b_{h\left\lfloor x\right\rfloor +\mbox{mod}\left(\left\lfloor y\right\rfloor ,h\right)}(t)$

(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 $T_{t,h}(x,y+h)=T_{t,h}(x,y)$ . Since we want to draw bitmaps inside a rectangle, we will need to confine it to $0\le y\le h$ - that is, to multiply it by a function $W_{h}(y)$ that is for $0\le y<h$ and 0 elsewhere. One simple way of defining it is:

$\displaystyle W_{h}(y)=\sum_{i=0}^{h-1}\delta(y-i)$

(5)

Where $\delta$ is Kronecker's delta (defined as: $\delta(x)=\left\{ \begin{array}{cc} 1 & x=0\\ 0 & x\ne0\end{array}\right.$ ). Then the following function will draw a given bitmap of a given height with its lower-left corner at the origin .

$\displaystyle B_{t,h}(x,y)=T_{t,h}(x,y)\cdot W_{h}(y)$

(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 $x_{0}$ and $y_{0}$ :

$\displaystyle P_{t,h,x_{0},y_{0}}(x,y)=B_{t,h}(x-x_{0},y-y_{0})$

(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 $B_{0}$ that contains a representation of the numeral 0 and $B_{1}$ 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 $d_{i}$ for $i=0,\ldots,k$ , beginning with the point $(x_{0},y_{0})$ . Then if $d_{i}=0$ , we may draw it as

$\displaystyle P_{B_{0},h,x_{0}-iw,y_{0}}(x,y)$

(8)

And if $d_{i}=1$ , we may draw it as

$\displaystyle P_{B_{1},h,x_{0}-iw,y_{0}}(x,y)$

(9)

To make a generic formula, we'll again use the $\delta$ function:

$\displaystyle P_{\delta(d_{i})\cdot B_{0}+\delta(1-d_{i})\cdot B_{1},h,x_{0}-iw,y_{0}}(x,y)$

(10)

In order to display the sequence for all $d_{i}$ s, we'll sum the expressions of the form (10):

$\displaystyle \sum_{i=0}^{k}P_{\delta(d_{i})\cdot B_{0}+\delta(1-d_{i})\cdot B_{1},h,x_{0}-iw,y_{0}}(x,y)$

(11)

In order to display the first bits of the number , we'll just replace $d_{i}$ with $b_{i}(n)$ :

$\displaystyle N_{n,{k,x}_{0},y_{0}}(x,y)=\sum_{i=0}^{k}P_{\delta(b_{i}(n))\cdot B_{0}+\delta(1-b_{i}(n))\cdot B_{1},h,x_{0}-iw,y_{0}}(x,y)$

(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 $k=500\times500$ 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 $Q=\ldots$ '' 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 functions

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

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

Footnotes

...Vergil: The author would like to thank Yonatan Ben-Ya'akov for presenting the central question of this memoir, as well as providing important feedback for its Hebrew draft.
...: Any constant point in $\mathbb{R}^{2}$ would do, as long as it's always the same