::Add RageStorm to Favorites!:: Tutorial - A Formula That Plots Itself
Author:Vergil
Category:Miscellaneous
Views:8825

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: 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; 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 .

# Tupper's Formula

Jeff Tupper has presented the following ingenious function: (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 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 for , where the value of is not given, and will plot the representation of at the position of the ''. Then we'll look at the formula for (2)

It evaluates to , that is, a bitmap representation of for '', 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: (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 : (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: (10)

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:

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 '' 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.

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 would do, as long as it's always the same
  CamachoBettie23 | 2010-07-23 18:22:56Don't you understand that it is high time to receive the loans, which will make you dreams real.
NOTE:
Comments that will hurt anyone in any way will be deleted.