Home
Tutorials
Code Snippets
Code Samples
Downloads
The Forum
Links

The Blog
Our Projects
Guest Book
About
Contact

ShOuT b0X:
::Add RageStorm to Favorites!::

The Blog | Our Projects | Guest Book | About | Contact

 
Tutorial - A Formula That Plots Itself
Author:Vergil
Category:Miscellaneous
Uploaded at:17-Mar-07
Views:6298

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 $ f$ that outputs a representation of $ f$.

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 $ t$, spread over lines of length $ k$. 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) $ t$ and $ k=105$, so chosen that the resulting plot is a plot of $ T(x,y)$ 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 - $ t$.

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 $ (0,0)$[*]?

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 $ P$ that is able to draw a number as a bitmap in the given rectangle.
    • Using $ P$, we can make a formula $ N$ that knows how to plot arbitrary binary numbers (i.e., produce a graph that looks like ``$ 101010$'')
  • Using $ P$ and $ N$, we can make a formula that prints a number twice: once as a bitmap, and one in its number representation.
Let's define $ b$ as a bitmap representing $ P(Q)+N(Q)\:$for$ \: Q=\ldots$, where the value of $ Q$ is not given, and $ N$ will plot the representation of $ Q$ 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 $ P(b)+N(b)$, 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 $ P$ and $ B$ as required above.

The following expression represents the $ i$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 $ (x,y)$, that also receives a parameter $ t$ - the number to be displayed, and the desired image height $ h$:

$\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 $ t$ in the rectangle of height $ h$ and arbitrary width. The zeroth bit of $ t$ will be at the lower-left corner (if we use Cartesian coordinates), the first will be above it, and the $ h$th will be to the right of the 0th.

An undesirable quality of $ T$ is the fact that it $ h$-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 $ 1$ 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 $ t$ of a given height $ h$ with its lower-left corner at the origin $ (0,0)$.

$\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 $ 1$. Let's assume they both have the height $ h$ and width $ w$.

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 $ k$ bits of the number $ n$, 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 $ N$.

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:

  1. Is it possible to ``compress'' the bitmap, so that less bits are necessary to display formulas? Would it necesserily require recursion?
  2. 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)

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


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
User Contributed Comments(1)
 [1] CamachoBettie23 | 2010-07-23 18:22:56

Don't you understand that it is high time to receive the <a href="http://bestfinance-blog.com">loans</a>, which will make you dreams real.
NOTE:
Comments that will hurt anyone in any way will be deleted.
Don't ask for features, advertise or curse.
If you want to leave a message to the author use the contacts,
if you have any question in relation to your comments please use the forum.
Comments which violate any of these requests will be deleted without further
notice. Use the comment system decently.

Post your comment:
Name:
email:
Comment:
::Top 5 Tutorials::
Embedded Python[78752]
2D Rotated Rectangles Collision Detection[65752]
Keyboard Hook[62284]
UDP[44147]
HTTP Proxy[31797]

::Top 5 Samples::
2D ColDet Rotated Rectangles[9499]
PS2 Mouse Driver[5619]
Reading FAT12[4453]
Wave Format Player[4435]
CodeGuru[4124]

::Link to RageStorm::

::Affiliates::
AngelCode
YOV408 Technologies
FireStorm


All rights reserved to RageStorm © 2009