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. 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 wasn't any other that was 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 holder... :-) - instead of sitting in a stuffy building wasting reams of paper and destroying the rain forest at the same time 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 might 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 - both of them I think - and 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: subtract ((5 minutes, 6 minutes), (2 aspirins, 3 aspirins)) = (5 minutes↓ - 3 aspirins, 6 minutes↓ - 2 aspirins) , 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're floating, within boundary limits of course. I hope that's made it very clear.
Interval arithmetic is a very interesting branch of mathematics. Human beings tend to think in terms of actual quantities; it's not very often that they think in terms of upper and lower bounds of those quantities. But there is a whole 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 will be well defined, 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... :-)
But 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 really frustrated she'll 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's an interval arithmetic formula. An 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 formula does not have to output an exact value but simply meet the condition that the output is greater than 0.5. Therefore there is no equal sign anywhere. From the equation you'll probably be getting an inkling that the output might very well be binary in nature and the 0.5 is just a threshold fixed value between 1 and 0 - That's interval mathematics for you I suppose...
It certainly does appear to be a binary formula and the mod 2 and mod 17 sequence gives that indication straight away. Then 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 - 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 differently, when the output of the formula meets the condition, then x, and y are considered 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 likely to be the solutions. Hence, they are 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, neither does he mention it being a quine, that other Blogger's seem to be mentioning.
It is an excellent paper in which he discusses a new and better way to graph functions, which holds a lot of merit. And 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're not experienced in mathematics, [or experienced as the case may be] you probably won't 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 won't make sense if you did it that way. So 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 are arranged within each other. I didn't 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 each 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 - aka, Russian Dolls - where one doll is inside another doll. Made by a Russian guy called Sergey. - Not the owner of Google! Similarly, the result of the inner function is fed to the outer function and so forth until the outermost function which would be the final comparison of the inequality.
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. I love taking technology apart: Vintage Walkmans, Radios, Electronic Engineering, software, ancient puzzles, and all sorts of things to figure out how they work...
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 where many mathematicians have devoted their lives to. 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're just not getting it then perhaps this animation might help to train the brain a little. If you look at the sequence of steps the way I am animating them, 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's where you need to start from.
Tupper's Jedi Mind Power: At the risk of sounding like Master Yoda, If y is a positive integer number, then why floor? mmm? Obfuscating I think, this padawan is.
mod(⌊y⌋,17): y contains the constant K when the bitmap offset is 0 or y = 0, therefore based on my rough guess (If you are using the casting or division by factors approach and doing this in your head) mod(y,17) will return a zero. Since it divides k completely by 17. 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's the remainder! and when the offset is 2, y = K+ 2 and run that through the mod function then obviously the remainder will be 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! that 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 why floor x? And for the same reason why floor the result of the second mod function. mod by its very nature will return an integer value because it's the remainder. If integer value it is 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 now 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 don't need to do any of this because it's so clear and obvious as explained, but for the neuronally 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. And here are the steps to do that, I am using my substitution method of showing you how this Russian Doll of a formula works.
And 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 inner most function in y and moving to the outer functions, similar to my animation. Each inner function is substituted by a letter of the alphabet in sequence a, b, c... and so forth. This is exactly as shown in my animated graphic which I hope will help to visualise.
The alphabetic sequence is very important as this is the sequence in which you would write the lines of code for your decoding program 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 called b... and so on until you get to the final variable i where a simple comparison operation is performed on the final 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 can't visualise this in your head.
I don't know what this method of deconstruction is called, but I am sure those toffs with an over-priced 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.
These cool hieroglyphic looking guys 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.
a = SchemeNumber.fn.floor(y);
Mod functions are actually very easy, but often not explained properly. It just doesn't 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 the integer a is divided by 17 and whatever the remainder is will be the result stored in b. It's a standard mod operation.
I'm embarrassed to say that I only know one way of writing it z = x mod y which I learnt from an old library book. But there are many ways of expressing mod arithmetic. But hey, what ever blows your hair back. If there's no money in it then I'm not interested how it's written.
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's obvious but I thought I should mention it. Since x and y are both positive integer values to begin with, this won't actually have any effect!
c = SchemeNumber.fn.floor(x);
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.
e = BigInteger.pow(2,d);
f = BigInteger.divide(y, 17);
g = SchemeNumber.fn.floor(f);
This is just a simple division where h = g /e.
h = BigInteger.divide(g, e);
i = BigInteger.remainder(h, 2);
j = SchemeNumber.fn.floor(i);
And finally you will be left with 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.
1: Variable pixel;
3: if (j>0.5)
Here is a simple if-else structure. When the value stored in variable is greater than 0.5 then the result of Tupper's formula satisfies the boundary condition and therefore the pixel is set to black. In computer parlance, black pixels are when the raster is off and therefore we use logic 0 to represent them.
When the value stored in variable i is less than 0.5 then the pixel is set to white, and therefore represented by logic 1. You can implement that however you like in what ever your compiler and hardware happens to be obviously.
Peter's Decoding Block
As you can see the main decoding block of Tupper's self-referential formula looks like this. Now that I have broken the formula into logical steps you can see what's happening. At this point, the code is almost ready to be used 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);
12: Var pixel;
14: if (j>0.5)
Here is a pseudo program showing the main decoding block. The full working program can be seen 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 the exact code implementation 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...
Tupper's Self-Referential Formula Explained
Simplification of Tupper's Formula for Graphing
How to graph Tupper's self-referential formula
Graphing Raster Used for Tupper's Formula
Plot Tupper's Self-Referential Formula
How to Convert Binary (Base 2) to Decimal (Base 10)
Self-Referential Formula Plot 1
Self-Referential Formula Plot 2
Author: Peter J. Vis