Slashdot Mirror
Share The Pi!
freedumb writes "From this article in Nature: "Two mathematicians have now taken the first step towards proving that pi contains not a single message but every conceivable message, meaningful or not."" Actually, it's a discussion concerning whether "that all strings of the same length appear in pi with the same frequency: 87,435 appears as often as 30,752, and 451 as often as 862, a property known as normality."
Soo.. if pi contained every possible message (ie, was truly random), couldn't you in theory find a specific position where pi prints out say, the Max Payne ISO, and distribute that position to friends?
Then, said friends, start calculating pi from that offset (wasn't there a story on slashdot about calculating any N digit of pi without having to calculate the first N-1 digits). Voila, kickass compression.
Of course, the small snags here are:
But once you get over these boring details, pi-based-compression can make for some very neat applications
Oddly, my ICQ number is at position 19724810 counting from the first digit after the decimal point.
What're the odds of *that*?
;-)
Cheers,
Jim in Tokyo
Have no clue about firewalls?
-- My Weblog.
Why concentrate on just pi? If they show it's true for all trancendental numbers, they've got it for pi, e, etc.
Can pi appear in pi anywhere? I guess not, since that would mean that pi repeats. Could e be in pi? I suppose if e was in pi, and pi was in e, then pi would be in pi, which I guessed earlier it couldn't be. But, maybe I'm wrong and there's a loophole since if pi contains itself, there's an infinite recursion going on.
If there were an infinite number of monkeys typing on an infinite number of keyboards would they eventually produce all the works of Shakespeare? Not exactly - they would produce them immediately (as quickly as a monkey can type). That's infinity for you. The lazy 8. It goes on and on...
BigKahuna
That's not quite true. There exist numbers which have a PATTERN, but don't actually repeat.
.101001000100001000001...
For instance,
There's certainly a pattern (1 zero then 2 zeros then 3...) but the number never repeats.
this is the latest : microsoft sues pi for containing the complete source code to windoze.
btw, the code starts at position 4200394298 (in the binary expansion of pi), and continues for well, as long as anyone ccan read the stuff...
Don't Panic
Not necessarily so. If you define a (decimal) number as follows:
- it starts with 1.
after the dot, each digit at a prime number position is 1, and 0 otherwise
The number would be 1.01101010001010001...- The number would have no periodicity (because prime numbers become rarer and rarer), so it woule not be a rational number.
- It never ends.
- But still, by construction, it would not contain a single 8, much less a series of 5,646,498,765 eights.
Thus proving that never ending irrational number does not necessarily contain all strings. Btw, irrational numbers are always never ending, or else they would be a fraction whose denominator would be a large power of ten. Think about it.Say no to software patents.
If you did any math in your youth, you'd know that this is a perfectly valid way to do a proof. It's called "coming up with a counterexample". If somebody claimed that all prime numbers were odd, it would be perfectly valid to point out that 2 is both prime and even. Discarding the proof because "you purposefully picked 2 to show me wrong" is invalid, as this is the whole point of the proof.
Likewise, in this case DNS-and-BIND claimed that all infinitely long irrational numbers have necessary a long sequence of 8's in them. I refuted his claim by showing him a number which had no 8 at all inside. Now, what exactly is your problem with my refutation of that claim?
> But that doesn't tell us anything about wether or not there is a string of 5,646,498,765 8s in pi or any other irrational number in decimal.
You're right on that, but nobody claimed the contrary. Saying "not all irrational numbers have a long string of 8's in them" is not the same thing as "no irrational numbers have a long string of 8's in them".
It's like in real life: "not all pies are cream pies" (or expressed differently "it is a pie, so it has to be a cream pie"): indeed, there are also apple pies...
But that doesn't mean that "no pies are cream pies" (i.e. cream pies don't exist): indeed Bill Gates was hit by one in the face...
Say no to software patents.
42424242 at position 242424.
Oddly enough, according to the pi search page, the same string can be found again at position 1404114, which is also below 100000000. On a normal pi, you'd expect a single occurrance of 42424242 below 100000000, and at a completely random position...
Say no to software patents.
Cannot be, or else it would repeat itself an infinite number of times, cyclically, which would make it a rational number.
Say no to software patents.
It will start a whole new branch of numerology dedicated to finding entire new holy books... the Book of the Damned, I Microsoft, II Microsoft, the letter of BOFH to the Great Unwashed, and, of course, the source code to Office (which will take up the space between 2^8 and 2^40906) ...
Zaphod B
Zaphod B
When duplication is outlawed, only outlaws will have
So if anything, they are proving normality to base 2^n, NOT base 10^n. And it may actually be that their proof is general enough to show normality in all bases - the article is not clear on that point.
Ok, if an average MP3 is 5MB (5,242,880 bytes) then the odds of finding a specific MP3 using a sequence of random numbers is 1/256**5,242,880 (since 8-bit bytes have 256 possibilities). This is about the same as 1/10**12,626,113 (since our base 10 numbering system gives each digit only 10 possibilities)
P(MP3)=1/10**12,626,113 (really close to 0)
Thus the odds of not finding a specific 5Mb MP3 using a sequence of random digits is 1-P(MP3)
~P(MP3)=1-1/10**12,626,113 (much closer to 1)
Since the longest known expansion of Pi is about 500 Billion digits (500,000,000,000) there are 499,987,373,888 consecutive strings of 12,626,113 digits contained in the known expansion. So the question is, what is the probabilty that at least one of these is the specific 5MB MP3 we are looking for.
An easier question is to ask what is the probabilty that we won't find the specific 5MB MP3 in a 500 Billion digit expansion of Pi.
The probability that any specific 12,626,113 digit substring of the 500 Billion digit expansion of Pi is not the 5MB MP3 we are looking for is ~P(MP3). So the probability that every one of the 499,987,373,888 possible 12,626,113 digit expansions is not the 5MB MP3 we are looking for is ~P(MP3)**499,987,373,888.
P(~MP3)=~P(MP3)**499,987,373,888
So now that we know the probability that a specific 5MB MP3 file is not contained in the 500 Billion digit known expansion of Pi, we can calculate the probability that we can find at least one instance of a specific 5MB MP3 as ~P(~MP3)=1-P(~MP3).
~P(~MP3)=1-P(~MP3) =1-~P(MP3)**499,987,373,888 =1-(1-P(MP3))**499,987,373,888 =1-(1-1/10**12,626,113)**499,987,373,888
Hmmm... I think I'll go by a lottery ticket.
Other possible things that we could find -
Then there are the 'dirty' irrational numbers like pi and e that seem to have random digits. The research mentioned has moved a big step closer to proving that the digits of pi don't just seem random, they truly are random (at least in the sense that all possible combinations occur).
The part that'll really blow your mind is that somebody found an equation that tells you any binary digit of pi you want, without having to calculate any of the other binary digits. (See here.) That is why people are excited by the conjectured normality of pi: if normal, it produces all possible strings of bits from a trivial deterministic equation. This mixture of randomness with order is at the heart of many interesting questions in chaos theory, computational theory, and cryptography.
-- ;-)
Kuro5hin.org: where the good times never end.
And that is a pain in the neck for everyone in comp.compression.
There is a frequent fallacy among those who almost understand how compression works, that works like this:
The assumption, of course, is that the number of digits and the offset can be encoded in a form that will be smaller than the original sequence. There is nothing to warrant that assumption. The fact is that the number of possible inputs that a lossless compression method can handle places lower bounds on the average length of its outputs. This means that no lossless compression method can achieve a lower average length for its outputs than would be achieved by simply numbering them all with the non-negative integers.
In fact, 'compressing' a sequence of digits into a (length, offset) pair will do substantially worse, since there are multiple (length, offset) pairs that will correspond to a given digit sequence; for instance, "1" could be encoded as (1,0) or (1,2). This duplication means that (1,2) is essentially wasted, since it could be representing a sequence that currently has a longer representation.
Lossless compression methods need to be used in conjunction with models: some criteria that separates the data we will want to compress from the vast majority of files, about which we do not care. The accuracy of this model affects how many of our inputs we can actually compress, and its precision affects the average compression ratio.
If people are to respect the law, perhaps the law should begin by respecting the people.
A teacher, a physicist and a mathemetician are having drinks together in a Scottish pub when the teacher looks out the window and sees a white sheep. The teacher says, "There are white sheep in Scotland". The physicist looks out the window and declares, "There are sheep in Scotland; we have already detected and confirmed white ones." The mathematician says, "In Scotland there is at least one sheep, at least one side of which is hite."
No, I didn't pull that from Singh (it's there, though). It's an old mathematician's joke but it's true. The most anal Rainman you've ever seen is incredibly chaotic compared to mathematicians (at least when they're working on a proof or theorem).
woof.
"No ma. You don't have to worry about Code Red. Yes, I know CNN told you that you do. Ma, do you run a Web server? No, Netscape is a browser, not a server. Yes, there's a difference. You don't want to know. No, and the Internet didn't die last week, either..." -- my side of a phone call two nights ago.
Trying to imagine why every n digit number shows up the exact same amount of times is hard to imagine at first. But then, once you think about it, on an infinite scale, it would seem to attest to Pi's true randomness.
On a side note, I had a Calc II professor awhile back that wrote on the board:
e^(i*Pi) = -1 (of course, using the real symbols).
Then, he proved it. I have the proof written down in a notebook and I even managed to work through the final parts of the proof (it uses a standard solution for finding e^(i*A*X) without using it. If anyone is really interested in seeing it, I can post it (in rough ascii math =) For those of you with TI-92s that don't believe me, type it in. That magical machine can do more than I give it credit for sometimes.
Anyway, I just thought it was absolutely incredible that you could mix the two most popular transcendental numbers with the imaginary number (square root of -1) and spit out plain old -1.
"The universe seems neither benign nor hostile, merely indifferent." --Carl Sagan
Who they going to sue then - the universe. Or perhaps they are going to require licenses to use PI instead...
If pi has all conceivable messages, pi must contain all of the US military's secrets, DeCSS, kiddie pr0n, violent and explicit sexual films beyond anyone's imagination and much much more. It must therefore be banned. When you get the death penalty for circle possession, don't say I didn't warn you...
A specific string of k bits long will on average occur every 2^k bits of a random bitstream. (For example, it will on average take about 1024 coin tosses to get 10 heads in a row.)[0] The reasoning I have in mind for this relies on the fact that coin tosses are independent events. The digits of pi are certainly not independent random events because we can calculate them. However, because of normality behaves macroscopically much like independent events, k precise bits will occur on average every 2^k bits of pi. I imagine the actual proof is highly nontrivial, but handwavy entropy arguments convince me that this is true.
.320 and they
play 1000 games (made-up numbers).
[0] As an interesting sidenote, many of the "streaks" in sports coincide roughly with the streaks that probability dictates. Baseball hitting streaks aren't necessarily because the hitter is in the zone... they may be because probabalistically, they are due to hit in 30 games in a row if their average is
healyourchurchwebsite.com - WWJB?