Tupper’s Self-Referential Formula Explained

How does Tupper’s Self-Referential Formula Work? I should begin by mentioning that I am not an expert in interval mathematics. As of 5 minutes ago, I didn't even know it existed! I realise that there are people out there who may have spent a lifetime in this pursuit, however, I am only writing this article because, 1. I am a blogger, and 2. There might be some hits in this for me. :-)

Except for Shreevatsa's excellent blog, there were no other sites even remotely explaining or showing how the formula worked, so I figured that perhaps this is an opportunity to make some great original content by showing how the formula works, after all I am no ordinary Brit blogger.

My highest mathematics qualification is a Woodwork School Report -- the only qualification that I am very proud of because the teacher was honest. :-) I was the clever one of course because at least you can make something useful like a coat hanger or a guitar bracket... :-) It is far better than sitting in a stuffy building wasting reams of paper and destroying the rainforest simultaneously, performing long division like a lab rat.

I am going to make this article as simple as possible so that it might be interesting for people with very basic mathematics knowledge to follow, and plot Tupper’s Formula. I hope that it will be something that students can follow also to re-create similar results if they so wished, bit like a dummies guide.

In this multi-page article I use the term "Tupper" for short, which is a more widely used and accepted term, but of course I mean Mr Tupper. Manners maketh a man after all. After reading Mr Tupper’s scientific papers, which I enjoyed very much, my sum total experience of interval mathematics can be aptly expressed as:

5 minutes ≤ experience ≤ 6 minutes, followed by 2 ≤ aspirins ≤ 4

For the advanced mathematician, it should also be noted that the pain ratio of understanding interval arithmetic can be further characterised by the following statement.

Subtract ((5 minutes, 6 minutes), (2 aspirins, 3 aspirins)) = (5 minutes↓ - 3 aspirins, 6 minutes↓ - 2 aspirins)

This is where the arrow sign ↓ means that you end up on the actual floor and not the floating-point floor, although at some point you might actually feel like you are floating, within boundary limits of course. I hope that has made it very clear. Actually, I am just kidding, as this is extremely simple stuff.

Interval Arithmetic

Interval arithmetic is a very interesting branch of mathematics. Human beings tend to think in terms of actual quantities; it is not very often that they think in terms of upper and lower bounds of those quantities. Nevertheless, there is a completely new way of thinking that you have to get used to first before you can even start to appreciate the formula.

Of course the next time the wife asks you when you are going to be washing the dishes you could smugly give her an interval arithmetic reply 1 day ≤ wash ≤ 5 days which will correctly result in a frying pan stuck on your head. Although it will be painful, it certainly defines well, and you will understand the true nature of interval arithmetic.

Interval Arithmetic Example: Here is another example of interval arithmetic. Let us say that the wife asks you a direct question, "How many cans of cola did you drink last night?"

Have you noticed how human beings become experts in interval arithmetic when they need to lie? Obviously, it is not in your best interests to give her the precise figure, which is what she is expecting, but instead you give her the convenient interval arithmetic answer of: 2 ≤ cans ≤ 5.

Obviously, she is going to be wondering what that means. "Well, what does that mean? Did you drink two cans?" She snaps back. The number 2 falls within the region and therefore satisfies the inequality condition of the formula. Therefore, your answer should be, yes. Obviously, you should keep your answers short from this point forward for obvious reasons... :-)

However, human beings hate vagueness and therefore she is going to be persistent and ask another question, "Well, did you drink 4 cans?" Again, your answer should be a short yes, because the number 4 satisfies the inequality condition. Then, frustrated she will ask, "Did you have 6 cans?" There, your answer should be no, because the number 6 does not satisfy the condition, it falls outside the interval range.

As you can see, interval arithmetic can be very annoying to many mathematicians and their families because it deals in working with boundary limits and not actual values. There is an ideal comedy sketch somewhere in here for Sheldon to use, in "The big bang theory".

The Inequality Formula

How Tupper’s Self-Referential Formula Works: It works in exactly the same way that I described in the examples above. It is an interval arithmetic formula, or inequality formula in x and y, and when the output of the formula satisfies the inequality condition, then x and y are considered to be solutions of the equation.

The precise value produced by the formula is not so important, only that it meets the condition of being greater than 0.5. Therefore, there is no equal sign anywhere. From the equation you will probably be getting inkling that the output might very well be binary in nature and the 0.5 is just a threshold fixed value between one and zero.

It appears binary to me because the mod 2, and mod 17, sequences gives that indication straight away. When looking at the power of 2, there is further suspicion that this is indeed binary, which is probably what most people were thinking as well. However, suspicions are no good, and I need hard applicable results, hence another reason to waste a bit of time.

From a computer algorithm perspective this makes things very easy, because you simply plug values of x and y into the equation and if the result is greater than 0.5 then we make the pixel black. If it is less than 0.5 then we make the pixel white. Expressing this differently, when the output of the formula meets the condition, then x, and y values are solutions and therefore represented by a black pixel. When x and y do not meet the condition and fall outside the range of the inequality, they are not the solutions, and represented by a white pixel.

When you plot these pixels, they build a monochrome bitmap image of the formula itself. Although many people seem to think that this is a self-referential formula, it is not because there is one main thing missing from the bitmap image. Can you guess what it is? Yes, the large constant, which is also a part of the formula, is not in the image. Therefore, it is not truly self-referential, but perhaps semi-referential within certain bounds. :-)

Mr Tupper does not mention anywhere in his paper about his objective being to make a self-referential algorithm, nor does he mention it being a "quine", that other Blogger’s seem to be mentioning.

In his excellent paper, he discusses a new and better way to graph functions, which holds a lot of merit. Moreover, I think he used those ideas in the creation of GraphEq, which is the best graphing package currently available and ideal for research students if they require accuracy and precision.

How to read the Formula

If you are not experienced in mathematics, (or experienced as the case may be) you probably will not even know how to read this formula let alone know where to begin. Most people tend to read it as if it were a written passage, from left to right... Obviously, it will not make sense if you did it that way. Therefore, with the magic of my animation, I am able to show you for the first time how a Jedi reads it. :-)

The animation above shows how the functions arrange within each other. I did not get an overpriced education, but hopefully this is how you might be seeing it as well. It also just happens to be the order in which to process the formula if you were ever wondering. I have deconstructed the formula exactly like this and replaced successive stages by a variable.

Mr Wizard! Get me out of here!

In many ways, the structure of the formula is a bit like the Matryoshka Doll, also known as the Russian Doll. This is where one doll is inside another doll, made by a Russian inventor Sergey. Not the founder of Google though! Similarly, the result of the inner function feeds the outer function and so forth until the outermost function produces either one or zero, which the inequality takes care of.

Hence, all you have to do is to disassemble it into individual stages to get the computer algorithm as shown below. Disassembling is something I am very good at as I love taking technology apart to figure out how it works.

As you can see in this formula, you have operators inside an operator, and a pair of mod functions also thrown in for good measure..

Modulo arithmetic is also another interesting branch of mathematics to which many mathematicians have devoted their lives. You could spend a whole lifetime just studying mod operations, and get absolutely nowhere.

The Cyberdyne T2000 Unit

The Cyberdyne T2000 unit would see it like this. Just a little bit faster on a good day without the fizzy cola drinks of course. :-) If you are just a mere human, you will not understand it, therefore this animation might help to train the brain a little. If you stare at the sequence of steps the way I am animating them, and then look at the static image in the banner at the top of this page, hopefully your mind will be trained enough to draw your eyes to the mod sequence in the power of 2. That is where you need to start.

Tupper’s Jedi Mind Power: At the risk of sounding like Master Yoda, if y is a positive integer number, then why floor? Hmm? Obfuscating I think, this Padawan is.

The reason why I think that is because mod (⌊y⌋, 17): y contains the constant k when the bitmap offset is zero or y = 0. Therefore, if you are using the casting or division by factors approach and doing this in your head, then mod(y, 17) will return a zero. It produces a zero because it divides k completely by 17, just do not do it too often in your head otherwise you will need a heatsink. :-) When you add 1 to the value of y, then its contents will be k + 1, which is the pixel offset, and when you run that through the mod function again in the next loop the result will obviously be 1, because that is the remainder! When the offset is 2, y = k + 2 which runs through the mod function producing a remainder of 2. This is going to happen all the way up to 16... Do you follow? Therefore, the whole of that mod sequence is simply a glorified counter, which counts from 0 to 16!

Now, obviously x is going to be a counter implementation counting from 0 to 105 that you are expected to sweep in order to plot the display output. Since x is a positive integer value, then why floor x? In addition, for the same reason why floor the result of the second mod function? A mod by its very nature will return an integer value because it is the remainder. If it is an integer value, then why floor? However, his paper did mention using a high-precision floating-point package, therefore this might be a general-purpose formula designed for all types of software packages...

I was scratching my head until 5 minutes↓ - 3 aspirins later I reached further down to the branch-cut and tracking section of the paper when the whole thing fell into place, and this is what I saw.

As you can see, written like this it makes perfect sense, and indicates the true reason to have floor functions. Slow I must be getting, in my old age... :-)

Peter’s Deconstruction of Tupper’s Formula

The formula can be re-written like this as explained in the Simplification of Tupper’s Formula for Graphing page that you should also read after reading this.

You actually do not need to do any of this because it is clear and obvious as explained, but for the brain-cell challenged, who just wants to see Tupper’s formula plot something I figure I might as well show the steps.

In order to plot Tupper’s self-referential formula: You will first need to deconstruct the formula to build a computer algorithm for decoding the bitmap data stored in the constant k. In these steps, I am using my substitution method to show you how this "Russian Doll" of a formula works.

As you can see, the final substitution is j and its comparison with 0.5.

Deconstruction of Tupper’s formula:

As you can see, I am starting out from the innermost function in y and moving to the outer functions, similar to my animation. A letter of the alphabet substitutes each inner function, hence the sequence a, b, c... and so forth. This is exactly as shown in my animated graphic, which I hope helped to visualise.

The sequence is very important, because you would write the lines of code for your decoding program in the same sequence to plot the function. As you can see the very first variable is a. The value of that is fed to the sub formula below it and its result is b... and so on until you get to the final variable "i" where a simple comparison operation is performed on the result.

Exercise: You can also re-construct this equation by substituting the variables into the equation, in reverse order. Wow! Peter, how can we ever repay you? I hear you exclaim. Well you can repay me by donating to my charity using the link below. Have a go at rebuilding the equation yourself on a piece of paper just to see for fun, if you cannot visualise this in your head.

I do not know what this method of deconstruction is called, but I am sure those toffs with an overpriced education will have a word for it.

Conversion to Computer Algorithm

As you can see, once you have the deconstruction steps in alphabetical order, as I've shown above, all that remains is to convert each step into an equivalent line of program code in whatever language that blows your hair back.

I am using JavaScript with a math library consisting of two files called biginteger.js and schemeNumber.js to handle the large integers. This code will work only on Firefox. If you do not have Firefox, then you can find it on Google.

This cool hieroglyphic on either side of the y indicates the floor function. The floor function is typically used in mathematics and computer science and means that the number represented by y maps to the largest integer number. This means the largest integer or greatest integer part of y.

For example:

If y = 3.14159, then floor(y) = 3

If y = 3.6789, then floor(y) = 3

In JavaScript programming language, you would use a very simple line of code that looks like the following to represent this:

 1: a = SchemeNumber.fn.floor(y);

Mod functions are actually very easy, but often not explained properly. It just does not translate well into language. In modulo arithmetic we are concerned with the remainder figure. Mr Tupper uses a mathematical syntax here that I am not familiar with but I understand what he means here. He means that 17 divides integer a, and whatever the remainder is will be the result stored in b. It is a standard mod operation. I am embarrassed to say that I only know one way of writing it, z = x mod y, which I learned from an old library book. However, there are many ways of expressing mod arithmetic. Nevertheless, whatever blows your hair back is fine.

In JavaScript and similar coding languages such as C, the percentage sign represents the mod operation. This function does the same thing and it means 17 divides the value stored in a, and the remainder is stored in variable b.

 1: b = BigInteger.remainder(a, 17);

This is the floor operation again, as described earlier. Incidentally notice that both x and y are fed through the floor function because we are interested in only their integer values. It is obvious but I thought I should mention it. Since x and y are both positive integer values to begin with, this will not actually have any effect!

 1: c = SchemeNumber.fn.floor(x);

This part is just a simple linear equation made out of c and b calculated earlier. I am adding brackets just to be extra clear to all the different types of browsers. Luckily, c and b are small numbers that JavaScript can handle, hence, I did not use functions from the big integer library for addition and multiplication.

 1: d = (17 * c) + b;

At this point, you should be able to see clearly that the formula is binary in nature, and therefore much easier than it looks.

 1: e = BigInteger.pow(2,d);

 1: f = BigInteger.divide(y, 17);

 1: g = SchemeNumber.fn.floor(f);

This is just a simple division where h = g /e.

 1: h = BigInteger.divide(g, e);

 1: i = BigInteger.remainder(h, 2);

 1: j = SchemeNumber.fn.floor(i);

Finally, you have a value in variable j that you will need to compare with the inequality formula.

This is actually what the formula boils down to in the end. All you have to do is compare the value stored in j to see if it is greater than 0.5. In computer language, an if-else structure in C is probably the best to use.

The inequality

 1: Variable pixel;

 2:  

 3: if (j>0.5)

 4:  {

 5:  pixel=0;

 6:  }

 7:  else

 8:  {

 9:  pixel=1;

 10: }

Here is a simplified if-else structure. If the value stored in variable i is greater than 0.5, then the result of Tupper’s formula satisfies the boundary condition and therefore the pixel is black. In computer parlance, black pixels are when the raster is off and therefore we use logic 0 to represent them.

If the value stored in variable i is less than 0.5, then the pixel is white, and therefore represented by logic 1. You can implement that however you like in whatever your compiler and hardware happens to be obviously.

Peter’s Decoding Block

As you can see, the main part of the decoding block for Tupper’s self-referential formula looks like this. Now that I have broken the formula into logical steps, you can see what is happening. At this point, the code is almost ready for plotting purposes. Just make sure that your programming environment can handle large integers because the value in y will contain Tupper’s Constant k, which is 543 digits long!

 1: a = SchemeNumber.fn.floor(y);

 2: b = BigInteger.remainder(a, 17);

 3: c = SchemeNumber.fn.floor(x);

 4: d = (17*c)+(b*1);

 5: e = BigInteger.pow(2,d);

 6: f = BigInteger.divide(y, 17);

 7: g = SchemeNumber.fn.floor(f);

 8: h = BigInteger.divide(g, e);

 9: i = BigInteger.remainder(h, 2);

 10: j = SchemeNumber.fn.floor(i);

 11:  

 12: Var pixel;

 13:  

 14: if (j>0.5)

 15:  {

 16:  pixel=0;

 17:  }

 18:  else

 19:  pixel=1;

 20: }

Here is a pseudo program showing the main decoding block. The full working program is in the following section of this multi-page article.

All you have to do now is to sweep the values of x, and y within a pixel grid. The values of x and y have been given by Mr Tupper as a range, together with a large constant. You can see this exact code implementation on the Plot Tupper’s Self-Referential Formula page.

If you are a professor reading this, please kindly leave feedback by email. Pass / Fail Mark. :-) Maybe I can add it to my CV, below the woodwork school report... :-)

This Article Continues...