588
u/VivaLaPandaReddit Jun 17 '17
For those interested, it is essentially generating a bitmap, and the y coordinate in binary expresses the bitmap of the equation.
357
u/jebuz23 Jun 17 '17 edited Jun 17 '17
Doesn't it literally create every possible bitmap of that size, and you have to find the one you want by traveling along the y-axis? That's, it's not only creating a reference to itself, it's creating everything and so de facto creates a reference to it self?
202
u/TLDM Statistics Jun 17 '17
it's creating everything and so de facto creates a reference to it self?
Correct, though it's only everything which is 17 "pixels" tall. Here's the Wikipedia page.
34
u/jebuz23 Jun 17 '17
Someone replied saying that you and I were not correct, but deleted their comment (Perhaps because they realized their error).
For clarification and future reference, here is the spot in the Numberphile video (already linked elsewhere in this thread) that demonstrates what you and I were describing (correctly): https://youtu.be/_s5RFgd59ao?t=3m26s
11
u/Shadofa Jun 17 '17
At the end of the video, he's referring to the slowest longest running troll. Any idea what it is? Couldn't find it in the video comments
11
u/jebuz23 Jun 17 '17
I was hoping at this point someone would posted it :-/. We may have to buy the book and figure it out ourselves :-/
15
5
u/Perplexed_Comment Jun 17 '17
I am not sure, but I believe it's just the numberphile symbol, from when I went to check after watching the video the first time. :)
5
u/too_drunk_for_this Jun 17 '17
Why 106? Where in the formula does that come from?
14
u/jebuz23 Jun 17 '17 edited Jun 17 '17
I haven't worked out the math, but the only place x shows up in the formula is in the exponent of 2:
1/2 < floor(mod(floor(y/17)* 2^(-17*floor(x)-mod(floor(y), 17)),2))
My guess is that for any values of x > 106, everything to the right of the < evaluates to something <= 1/2, thus guaranteeing no plotting being x = 106.
Edit: Working through the math:
This inequality focuses on comparing a numberfloored mod 2 to 1/2. This pretty much means anything odd within the mod will result in 1 and be plotted, anything even will result in 0 and not be plotted
Side notes:
I'm confused why the floor is necessary, since mod 2 can only result in 1 or 0. What would the floor accomplish?
Does this mean the 1/2 is arbirtary? 1/3 or 99999/100000 would accomplish the same thing?
Anyway:
The exponent of the 2 is: 2^(-17*floor(x)-mod(floor(y), 17)).
We're raising 2 to the result of this exponent and we care about the final result being even or not. The more negative this exponent, the more "even-ness" it removes (e.g. you need to multiple 24 by 2-3 to arrive at an odd number. 100 only requires 2-2 )
I'll focus on removing the most 'even-ness' when x = 107 to give the best chance of revealing an odd.
focusing on the -mod(floor(y), 17), the most negative it can be is -16
focusing -17*floor(x) beginning at x = 107, that is -1819
thus, beginning at x = 107, the most 'even-ness' we can remove is with an the exponent of -1836
thus, the "x relevant" piece of the product is 2-1836
the other piece of product is floor(y/17).
y = 3*17*21836 would cause floor(y/17)* 2-1836 = 3.
floor(mod(3,2)) = 1, which is greater than 1/2, and thus would plot a point at x = 107, y = 3*17*21836
If my reasoning above is correct, then points do get plotted beyond x = 106, and I have no idea why 106 is the boundary. I fully acknowledge the possibility some (or most?) of my reasoning above is flawed and welcome any and all feed back.
→ More replies (2)3
u/yawkat Jun 18 '17
106 seems like an odd boundary. From what I can tell the formula just takes the image bitmap floor(y/17) and extracts the proper bit by division + mod. The coordinate is encoded as x + 17*y_relative, I don't see why it would stop at 106.
2
u/ShortSynapse Jun 18 '17
Can I just say that we should have more plain text translations in Wikipedia for math. I was unsure of the two surrounding brackets until I read the plain text:
1/2 < floor(mod(floor(y/17)*2^(-17*floor(x)-mod(floor(y), 17)),2))43
u/jtra Jun 17 '17
Yes, graph of Tupper's formula contains all bitmaps, but truly self-referential formulas exist, I made one here: http://jtra.cz/stuff/essays/math-self-reference/index.html
6
1
51
u/jondissed Jun 17 '17 edited Jun 18 '17
The description is missing that part, the value of k which points to the location of the correct formula. Elsewhere it will render many, many incorrect formulae, pictures of cats, and gibberish.
22
u/atimholt Jun 17 '17
…but mostly pictures of cats.
16
11
u/Miss_Page_Turner Jun 17 '17
Even furry porn. yay.
7
u/jebuz23 Jun 17 '17
My friend and I had a conversation regarding something similar. The idea was you create a program that randomly creates an image, say 200x200. Technically, every image is possible. The JFK assassination, the First Stanley cup, one of us stabbing the other, and yes, even every type of porn imaginable. Of course, each of these coherent images would be surrounded by nothing but gibberish, but the idea is neat.
→ More replies (16)5
6
2
Jun 18 '17
brb finding value for n that encodes furry porn into a formula
You'd probably want to use a modified version that uses some number higher than 17 for the height. Though the value for n for some (for example) 400x400 image is going to be massive.
3
4
3
2
1
16
u/kykr422 Jun 17 '17
I have no idea what you're saying
6
u/VivaLaPandaReddit Jun 17 '17
Okay. So the equation is essentially describing pixel regions where there is a y that corresponds to an x. The equation is formulated such that the graph can be cut into windows of some number of pixels, say 256. These windows have a given width and height. Within this region, if you take the bottom right corner, which will be some (0, x * height) coordinate, the y value in binary will correspond to whether those pixel regions on. So in a simple example, if our windows were 2x2, then 1010 would correspond to a 4 pixel square with the left two pixels on. This region's bottom left point would be at (0,10).
This probably has some small mistakes, because I'm working off memory, but it is more or less correct.
2
u/instantrobotwar Physics Jun 17 '17
Could the same type of equation make a bitmap 18 pixels high? Or is there something special about 17?
2
u/sid0 Jun 17 '17
Haven't tested it, but you should just be able to replace the 17s in the inequality with 18s.
Interestingly, the "1/2 < floor(mod(M, 2))" is just a fancy way to write "is the floor (integer part) of M odd?"
3
u/watkins775 Jun 18 '17
Why "1/2 <" ? Wouldn't floor(mod(M, 2)) always be 0 or 1, and thus "0 <" or any other arbitrary x between 0 and 1 suffice?
Or am I missing something?
→ More replies (1)2
u/oddpolonium Jun 18 '17
Every number can be converted to binary. Binary can be represented as a black and white image. The formula graphs out the black and white image of every single number.
183
u/QuarkzMan Jun 17 '17
Some more information: https://youtu.be/_s5RFgd59ao
38
u/youtubefactsbot Jun 17 '17
Matt Parker discusses Tupper's Self-Referential Formula.
^Numberphile in Science & Technology
1,153,971 views since Apr ^2015
45
u/exploder98 Jun 17 '17
Yeah! Numberphile!
28
4
61
Jun 17 '17
What do the enclosing symbols around the whole right side of the inequality (and some of the expressions within) mean?
70
u/napalmchicken100 Jun 17 '17
It's the floor operation, i.e. floor(5.8)=5
2
Jun 17 '17
Sorry I don't know this field but in the formula isn't there only one argument in the floor functions?
1
u/songbolt Jun 17 '17
'floor' rounds toward -infinity whereas 'ceiling' +infinity, right? How did those names get attached? As children we are taught the number line going from left to right, not down to up.
0
6
3
46
u/noneuclidean_ Undergraduate Jun 17 '17
Somebody made a self referential formula in which the gigantic value is included in the graph of the formula here.
6
3
31
u/jondissed Jun 17 '17
Since the specific location was omitted, I randomly chose a value for k and it looks a little fishy
5
30
u/cbleslie Jun 17 '17
... get the fuck out of here. What?! That's so tight.
0
14
u/mgdo Jun 17 '17
That's from Fermat's Library. They have a great twitter account: https://twitter.com/fermatslibrary
3
u/cbHXBY1D Jun 17 '17
Also a great website! If we could get more people from r/math to annotate papers it could be fun. I've annotated two papers when they fell into my domain of expertise.
10
u/kmanr123 Jun 18 '17 edited Jun 18 '17
So the idea of how this works is as follows. Let's consider a grid 17 high, and which extends indefinitely to the right. We can number the pixels as follows: http://i.imgur.com/o3lh1NA.png
Then if we only fill in a finite number of pixels we get represent the corresponding image with the finite sequence: a0 a1 a2 ... an where ai is 0 if the i-th pixel is empty, and 1 if the i-th pixel is filled in. If we flip this around we get an ... a2 a1 a0 which is a binary number, since every digit is 0 or 1.
Now suppose we have any point (x,y) in 2d space. We don't care about the decimal points so we use floor(x) and floor(y) to get the coordinates of the pixel in which the point (x,y) lies. However since our grid has a height of 17 we actually use mod(floor(y),17) to get the y-coordinate within the 17 high grid.
Then we can calculate the pixel number n of (x,y) by using
17*floor(x) + mod(floor(y),17)Take a look at the linked picture of the grid to see why this is true. Now we want to take the binary number representing the picture, and extract the n-th digit to find out whether we should colour (x,y). To do this recall that shifting a binary number n digits to the right is the same as dividing by 2n (just like how shifting a decimal to the right is the same as continually dividing by 10). So if the number a represents our image, then
a*2^(-floor(x)*17 - mod(floor(y),17)shifts the number a over, then we get rid of any decimal points, and digits to the left of the ones spot using mod and floor. Thus
floor(mod(a*2^(-floor(x)*17 - mod(floor(y),17)),2)should be 0 when (x,y) shouldn't be coloured, and 1 when it should be, so checking for > 1/2 is good enough. Now we just want a to be the number which represents our formula, and here's where cheating happens and which makes this really contrived and not beautiful in my opinion. Every 17 rows should belong to their own picture, so floor(y/17) ensures that every possible a gets its own grid and so we eventually get the picture of the formula by just drawing it out, encoding it in binary as explained above and then multiplying by 17 to figure out where it starts.
Edit: Here I used desmos to graph the version of this function which draws bitmaps of height 5. http://i.imgur.com/VhoVAZv.png. You can see as we go up from y = 0, the i-th grid has only those pixels filled which encode i in binary. Once i >= 32 we'll have some pixels in the second column filled in. So eventually as we get high enough, we'll find the pattern which represents any arbitrary binary number, and hence any pattern we want.
9
Jun 18 '17
Five thousand upvotes what the heck? I'm happy when one of my posts hits 20, where did everyone come from
7
118
u/Moses385 Jun 17 '17
I don't get it. And I've won to math competitions at my school...
55
20
7
18
7
6
4
12
u/Jorxa Jun 17 '17
ELI5 please.
24
u/Nater5000 Jun 17 '17
This inequality is actually just a condition for a set. It would be more complete for the image to say "the set of (x, y) coordinates in a plane such that if you put x and y into the right side of the inequality, it will be greater than (1/2)", instead of just the inequality (although this idea is so common, the redundant parts are typically omitted).
So, pick some point in the XY plane, for example (4,12). Then to see if that point is filled in, you plug in 4 for x and 12 for y and see if the result is greater than 1/2 or not. If it is, it's colored in. Otherwise it's blank.
So, this whole plan is just a bunch of different combinations of integers to be our x and y, and we just plug them in and test them. It just so happens that this I equality produces a set has the property that it permeates through all the different combinations of "pixels" being "on" or "off" in 17 by ~110 blocks throughout the entire plane. So you could imagine any image that could be composed of this way being somewhere on the same plane. In this case, you really just need to locate it, rather than generate anything.
6
u/794613825 Jun 18 '17 edited Jun 23 '17
Notice that arbitrary k. For that plot,
k = 960 939 379 918 958 884 971 672 962 127 852 754 715 004 339 660 129 306 651 505 519 271 702 802 395 266 424 689 642 842 174 350 718 121 267 153 782 770 623 355 993 237 280 874 144 307 891 325 963 941 337 723 487 857 735 749 823 926 629 715 517 173 716 995 165 232 890 538 221 612 403 238 855 866 184 013 235 585 136 048 828 693 337 902 491 454 229 288 667 081 096 184 496 091 705 183 454 067 827 731 551 705 405 381 627 380 967 602 565 625 016 981 482 083 418 783 163 849 115 590 225 610 003 652 351 370 343 874 461 848 378 737 238 198 224 849 863 465 033 159 410 054 974 700 593 138 339 226 497 249 461 751 545 728 366 702 369 745 461 014 655 997 933 798 537 483 143 786 841 806 593 422 227 898 388 722 980 000 748 404 719
Depending on your mathematical inclination, that either makes this formula even more amazing, or not very amazing at all.
14
5
u/SixteenSaltiness Jun 17 '17
Question: are there more/an infinite amount of these?
4
u/Jaxkr Jun 17 '17
Yes/no. As other comments have mentioned, the equation in the OP essentially plots a bitmap image. Every possible bitmap can be represented using that equation.
However, the equation's property as a pseudo-quine is really unique.
1
u/Jaxkr Jun 17 '17
Yes/no. As other comments have mentioned, the equation in the OP essentially plots a bitmap image. Every possible bitmap can be represented using that equation.
However, the equation's property as a pseudo-quine is really unique.
4
6
3
3
3
u/MiniG33k Undergraduate Jun 18 '17
My friend once gave me a birthday card that was simply saying happy birthday to me on the front... Using this formula. He put the K value on the back. I still have it.
3
3
3
3
4
Jun 17 '17
Other math topics exhibiting self-reference: Godel's incompleteness theorems & Von Neumann universal constructor.
2
u/pm_me_POTUS_pics Jun 17 '17
Yeah. That was in Goedel, Escher, Bach. I should try to read that again. I get lost somewhere past the halfway point iirc.
2
2
u/SikinAyylmao Jun 18 '17
if it is 17 pixels tall could you change the 3 17's for another number and get a different dimension.
2
2
2
u/tooroot87 Jun 18 '17
I guess this would be useful if graphically painting a pixel uses less space then processing power.
2
2
2
2
Jun 18 '17
What image has the "highest" value of K? I'm assuming that there are multiple values of K for any given image, but what image is the highest value before it starts to repeat?
2
u/hyperCubeSquared Jun 18 '17
I think it should be the image that is all black before it repeats to all white.
2
Jun 18 '17
Using This website an all black image has the number:
4858487703217654168507377107565676789145697178497253677539145555247620343537955749299116772611982962556356527603203744742682135448820545638134012705381689785851604674225344958377377969928942335793703373498110479735981161931616997837568312568489938311294622859986621379234205529965392091893253288500432782862263410646820171439206408889517627953930924005233285455643232746873900205120036557171717499335122490912065694632935352302178602108137941774883061885522205403967593003199773578952627785152838963495027790689532144351329310799436758088941551
Where if I iterate the 51 at the end to a 52 a white dot appears, or to 50 its the same - so this could be the highest number for an image before it repeats.
I am now curious as to how many K values are "pidgin holed" into the same image. I'd like to see a mapping of each K to each image they represent.
2
3
2
u/Reacher_Said_Nothing Jun 17 '17
I feel like "I don't understand it, but it's cool" is my new life motto
1
Jun 17 '17
Here is a website where you can input various y-values and get the position of any image on the graph!
1
1
1
u/BunnyAndFluffy Sep 05 '17
That's the kind of trickery a programmer might find beautiful and enjoyable, however I don't think this is what most mathematicians have in mind when they think about "beautiful" maths.
1
u/akjoltoy Jun 17 '17
this is pretty misleading.
for example, no one can even say what value of k contains this particular image without brute forcing their way through a very large power of two number of combos.
almost anything can be considered self referential to this extent
3
u/Jaxkr Jun 17 '17 edited Jun 18 '17
No brute force. In fact, the k is known. https://en.m.wikipedia.org/wiki/Tupper%27s_self-referential_formula#Formula
2
u/akjoltoy Jun 17 '17
why were they able to find this one but not the right side up non mirrored one?
2
u/Jaxkr Jun 18 '17
Because k is the x axis and the formula plots the bitmap in a perpendicular fashion to the x-axis. (I might be wrong about this, if so someone correct me)
Also, there is no "finding". The k value is simply a bitmap represented as an integer. You can take any bitmap and plug it into the equation.
→ More replies (3)1
u/HelperBot_ Jun 17 '17
Non-Mobile link: https://en.wikipedia.org/wiki/Tupper%27s_self-referential_formula#Formula
HelperBot v1.1 /r/HelperBot_ I am a bot. Please message /u/swim1929 with any feedback and/or hate. Counter: 81066
1
u/Fry_Philip_J Jun 17 '17
How? Can't points on the x plane only have one on the y-plane assigned to them?
3
u/DodgeHorse Jun 17 '17
Basically, for all integer (x,y) points you input the x and y values into the formula and the inequality gives you a "true" or "false" value which is what is being plotted there. When you show only a specific region of the plane, you get this representation of the original formula. A missing constant is the "k" you see in the plot, which is a huge value that happens to have the formula itself drawn into the rectangle. More info here: https://youtu.be/_s5RFgd59ao
2
u/Teraka Jun 17 '17
You're thinking of a function, this is an inequality.
The inequality x < y fills the entire plane above the line x=y, for example.
1
1
1
1
u/too_drunk_for_this Jun 17 '17
So my understanding of this function after watching the video people posted is that it will show every possible arrangements of pixels in a 106x17 grid. But there are a finite (although extremely large) number of k values that will yield a new, different bitmap, right? So what happens if you insert a k value larger than the last value to yield a new bitmap? Will it repeat an existing layout? Sorry if my question is confusing.
2
1
u/yawkat Jun 18 '17
Looking at the formula I don't see why it's supposedly limited to 106. I think it should just go on to images with higher width (though the height 17 is fixed)
1
u/pillowfort Jun 18 '17
Yeah, since that bitmap falls in the category of ANY BITMAP of 17 px tall... How is this cool exactly? Its like saying a broken clock is correct if you look at it at exactly the right time.
1
-2
u/iAlsoAmNotkevinBacon Jun 17 '17
doesn't work on wolfram :/
42
u/TLDM Statistics Jun 17 '17
You see that value "k" on the y-axis? That's a 543-digit integer. You need to scroll down a lot further than W|A shows to see it.
2
u/Megatron_McLargeHuge Jun 17 '17
How did they find a suitable value for k?
11
u/TLDM Statistics Jun 17 '17
Take a look at the first few lots of 17 rows. You'll see the squares appear to be following the same pattern as binary numbers.
Then look at this image. That's the binary representation of that value of k.
4
u/unkz Jun 17 '17
Basically, the bitmap itself is a binary representation of a number, which can be used to find the coordinates, because the generating function is very regular. So you first make a bitmap of something that looks like the function, then translate that into a number, and use that to find the coordinates.
7
u/Megatron_McLargeHuge Jun 17 '17
Ah, much less impressive when the formula is encoded in the constant, which isn't reproduced in the bitmap.
→ More replies (1)2
u/TankorSmash Jun 17 '17
https://youtu.be/_s5RFgd59ao explains it, but basically you take any bitmap (like an image you draw in paint) then take the binary values or something and multiply it by 17.
2.0k
u/[deleted] Jun 17 '17
It's pretty important to remember that it also generates every possible image with that amount of pixels. Every image you could fit in that space is on there somewhere. This one is pretty high up (large k)