9 ms·
Mathematics: Came across the following gag. Is it true?
- lutusp 14y agoAssuming that π is normal and infinite (that's redundant but for clarity), then yes, it's true -- it contains every finite-sized number, every textual sequence, every secret, every book ever written. Scientific secrets we may never discover. Cures to nonexistent diseases. Everything! But this is as meaningless as it is true, because the problem is not that those secrets are present, the problem lies in locating them. I had this conversation years ago on Usenet -- the same question, the same answer. My correspondent seemed to think it was remarkable that all those riches lay within π. He didn't seem to realize that the same could be said of any normal, infinite sequence of digits, of which there may be an infinite number (not proven, but it's possible that e, √2, indeed the square root of any non-perfect-square number, all fall into this category). If the grains of sand on a beach could be decoded as binary bits (or as digits in any base) by some accepted convention, and making the same assumptions about normality and infinity, then a beach also contains every secret, every book that has ever been written or will ever be written. But it's the same problem - those secrets cannot be located, distinguished from sequences we might label meaningless, simply because they're answers we're not interested in. http://en.wikipedia.org/wiki/Normal_number http://en.wikipedia.org/wiki/Normal_number A quote: "While a general proof can be given that almost all numbers are normal (in the sense that the set of exceptions has Lebesgue measure zero), this proof is not constructive and only very few specific numbers have been shown to be normal. For example, it is widely believed that the numbers √2, π, and e are normal, but a proof remains elusive."
- gabemart 14y agoI don't have a strong mathematics background, but would I be right in thinking that the probability of a normal, infinite number containing a given arbitrary string of digits is "almost sure" rather than "sure"? Or can it actually be proven mathematically that it contains such a string?
- notatoad 14y agoIt's not proven, it's the definition. If there is a subsequence that isn't contained in a non-repeating infintely long sequence, then it isn't a non-repeating infinitely long sequence.
- ColinWright 14y agoYou're conflating two things. The technical definition of "normal" is that it contains every finite string as a substring. That will imply that it's infinite and non-repeating. However, you can have a string that is infinit and non-repeating but not normal. Pi is infinite and non-repeating, but it is not known to be normal.
- deleted 14y ago[deleted]
- xyzzyz 14y agoThis is not true. For instance, sequence 00 does not occur in sequence 010110111011110111110111111... which can hardly be described as "repeating" (or periodic) sequence. The point here is normality. Fix alphabet A having b letters. We say that a sequence S of elements of A is normal if, for every word w, we have lim n->inf C(S, w, n)/n = b^(-k) where C(S, w, n) is the number of occurrences of w in first n letters of S, and k is length of w. More intuitively, S is normal if every word occurs in S with the same asymptotic frequency. So, if a sequence does not contain some word as a substring, it cannot be normal by above definition.
- lutusp 14y ago> ... but would I be right in thinking that the probability of a normal, infinite number containing a given arbitrary string of digits is "almost sure" rather than "sure"? No. Given the assumptions (a normal number, therefore infinite in extent), the probability that a given finite sequence appears somewhere in it is 1.0. > Or can it actually be proven mathematically that it contains such a string? Here's one way to think about it. Let's say that you flip a perfectly fair, random coin, heads counts as 1 and tails 0, and each flip adds a bit to a sequence. Let's further say that some finite bit sequence is chosen as a finite-subsequence target, let's say the text of "War and Peace" by Leo Tolstoy (a famously big book, 1,225 pages). We can agree that, as the normal bit sequence increases in length, the probability of encountering "War and Peace" within the sequence increases as a strict function of the number of bits in the sequence. Now the clincher -- what is true for a finite sequence (that the probability of encountering a given subsequence increases but never becomes certain) is not true for an infinite sequence. For an infinite sequence, the probability for the appearance of a given subsequence becomes certain, i.e 1.0. The only requirement is that the subsequence be finite.
- cdavid 14y agoIt is proven that there is an infinite number of normal numbers, as quoted in the wiki article you're mentioning (p({a real; a is normal}) = 1).
- lutusp 14y agoYes, because among other things it's clearly implied by "While a general proof can be given that almost all numbers are normal ... " If true, then the set is infinite.
- rorrr 14y ago> But this is as meaningless as it is true Well, it's a little more complicated than that. You see, it means that there's the complete description of our universe in there, position of every atom, at every nanosecond. Somewhere in pi there's you living your life. Also, every possible you.
- lutusp 14y agoStill meaningless, because of the insoluble problem of access. Within Pi there's a cure for cancer, written entirely in iambic pentameter, but that fact has no practical meaning because we can't find it.
- Evbn 14y agoEmphases on insoluble, as to find an item of interest, on average, would take longer than the history of the Universe till now, longer than human civilization or any encoding scheme is likely to be in use....
- damian2000 14y agoSounds similar to the http://en.wikipedia.org/wiki/Infinite_monkey_theorem http://en.wikipedia.org/wiki/Infinite_monkey_theorem ... "a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text, such as the complete works of William Shakespeare."
- Fice 14y agoIn the ideal world of mathematics there is no distinction between creating and discovering. Everything that is possible exists. That makes the infinite monkey theorem or statements like "the answers to all the great questions of the universe can be found in the digits of π" meaningless. For instance, every future masterpiece of literature already exist in mathematical sense, yet it will still take a genius to discover it in the infinite sequence of all possible texts.
- xk_id 14y agoDo you have any bibliography for this topic? I would be very grateful, I'm extremely interested in this.
- lifeformed 14y agoDoes this mean writing out a normal number is illegal? They encode state secrets, child pornography, pizza recipes, and entire computer simulations of universes where owning pizza recipes is considered high treason.
- teraflop 14y agoOnly to the same extent that counting is illegal, because if you count high enough you'll eventually generate a numeric representation of every possible datum.
- Evbn 14y agoYes. Recall the DeCSS controversery in USA, and the Wicket-Cricket wars in fiction's HHGTTG
- randomdata 14y agoThe law is about intent. Writing out a number isn't illegal, but writing out a number with the purpose of carrying out something that is illegal is. To be fair, it is a concept that I still struggle with. My programmer mind is always stuck in "it is either true or it isn't" mode. Things that are only true sometimes do not make sense to me.
- phylofx 14y agoWell, obviously, everything exists in the infinite - somewhere. A completely trivial realization, however.
- ColinWright 14y agoThis is not true - you can have infinite things without them containing evertthing. So no, this is not obvious. Indeed, pi may not be normal, so there may be things not contained in it.
- BasDirks 14y agoYou could pose the question the other way around: is the infinite hidden within the finite? This philosophical question is probably outside the realm of mathematics, but an interesting thought-exercise.
- lutusp 14y ago> You could pose the question the other way around: is the infinite hidden within the finite? This philosophical question is probably outside the realm of mathematics ... There's a reason it's outside the domain of mathematics -- it contradicts the definition of infinite. By definition, an infinite set cannot be a subset of a finite one. > ... but an interesting thought-exercise. Briefly, but easily answered. :)
- BasDirks 14y agoI came to think of it after reading part of one of the answers in OP link: "So yes, it has the story of your life -- but it also has many false stories, many subtly wrong statements, and lots of gibberish." The "gibberish" is bound to contain many truths. This kind of encoding is very different from the mathematical idea of subsets. I am probably bending concepts beyond breaking point here, and you are correct.
- Evbn 14y agoBut look at at the plain meaning of the word: "infinite" is "in finite". More seriously, if you aren't careful in your interpretations, you observe that the real interval [0,1] has finite measure but infinite cardinality. And the rational interval has 0 measure but infinite cardinality, so you do find infinite in the finite.
- IsaacL 14y agoI'm guessing people here are familiar with Borges' "Library of Babel". (If not, it's a short story about a library that contains every possible book). I read an interesting thought experiment about the concept: 1. There's lots of different languages around, but all languages (even Chinese) use a finite alphabet of symbols. So for simplicity we can just convert all languages in the Library into binary. 2. On first appearance, the library would contain books of an infinite number of lengths. But it would surely be more practical to split such books into volumes. 3. You'd have a maximum volume length of say, 1 million bits. Books shorter than that can just be padded with 0s. But you can now double up volumes: volume #6345 of book #1840849 might be an exact duplicate of volume #93974 of book #11132445. Which means the library can now be finite in size: it only needs to contain all one-million-bit strings, a mere 2^1000000 volumes. 4. Why stop there, though? It's clear we could just use smaller volumes and get a smaller library. In fact, the library only needs two pages - one '0' and one '1'. Depending on the order you read them, you can get any book you want out of it. Information theory is weird. Edit: here's the original: http://jubal.westnet.com/hyperdiscordia/universal_library.html http://jubal.westnet.com/hyperdiscordia/universal_library.ht...
- jasomill 14y agoYou don't even have to assume the alphabet is finite, merely countable, and you still have exactly one book for each finite string of bits. In other words, the set of every finite sequence of integers (or natural numbers, rationals, finite strings of Chinese characters, etc.) is no larger than the proper subset of "every sequence of length one". A library with uncountably many distinct volumes is a fun thought experiment, though, as is a text written in a language that uses an uncountable alphabet, wherein a single letter potentially contains an infinite amount of information...
- tripzilch 14y ago> a text written in a language that uses an uncountable alphabet, wherein a single letter potentially contains an infinite amount of information... Isn't that called "drawing" instead of "writing", though? So, comic books? :)
- 14y ago
- newhouseb 14y agoEver since I was a kid in elementary school I've loved the idea/thought experiment of owning a hard disk full of every possible n-by-n binary image. By definition, on this hard disk you would have a sketch of every person you've ever met, every person you've ever loved, every place you've ever been, every alien in the solar system. On one hand, it's endearing you could depict so many things in such a finite medium, but at the same time it's astounding how much storage space you would need for even the smallest reasonable numbers of N. Sometimes when I'm bored waiting for a bus, I love to think about what it would be like to pour through all these images and somehow know which ones would be meaningful in my future that I don't yet know.
- caf 14y agoSadly, there isn't enough energy in the entire Universe to cycle even a 16x16 black and white grid through all of its possible states.
- randomdata 14y agoUnless you happen to own a quantum computer.
- cammil 14y agoInfinite and non-repeating does not imply it contains every number. For proof of this, consider an infinite non-repeating number, without the number 9. Pi is infinite and non-repeating. I have not yet seen proof that pi contains every finite number.
- jbri 14y agoThis reminds me of the "pi encoding" - if pi is, in fact normal, you can encode any file as a tuple (`start`, `length`) encoding a substring of the expansion of pi. It's often phrased as a compression paradox of a sort - surprisingly many people overlook the fact that `start` will tend to take a lot of bits to encode.
- TazeTSchnitzel 14y agoIt's also quite slow...
- digeridoo 14y agoa. proove it b. pi as a decimal number is an approximation that is only as long as you calculate it to be. Moreover, decimals do not contain non-numeric information. That's just your own interpretation. Imagine a number system where pi is 1. Clearly no names in 1. Now imagine a number system where pi is expressed as π, like... the number system that we use. Clearly no names in π.
- lutusp 14y ago> pi as a decimal number is an approximation that is only as long as you calculate it to be. But Pi is not equal to our approximations of Pi. That's backwards. Pi owes nothing to our lame efforts to approximate it. When someone asserts that Pi may be an infinite sequence, the truth of the proposition doesn't depend on someone computing an infinite sequence of Pi's digits. > Moreover, decimals do not contain non-numeric information. Are you aware that your typing is promptly translated into numbers for transmission through the Internet? That A = 65 (in the old ASCII encoding), B = 66, etc.? So yes, decimals do contain non-numeric information if we choose to interpret them that way. And we do.
- sp332 14y agoYou're looking for strings in the decimal expansion of pi. Pi is not a decimal number! Every decimal representation of pi is an approximation. Pi is not an infinite sequence, it is a single value a bit higher than 3.14, it is only the decimal (or other bases, besides 10) expansion that has an infinite number of digits.
- lutusp 14y ago> Pi is not a decimal number! Of course it is -- although choice of base is quire arbitrary. Pi is as much a decimal number as it is a binary number. > Every decimal representation of pi is an approximation. Our inability to represent Pi doesn't constrain Pi, it only constrains us. The fact that we cannot fully represent Pi has no effect on Pi or its identity. And Pi has the same identity in any base -- the ratio of a circle's circumference to its diameter. > Pi is not an infinite sequence Pi is an infinite sequence. http://en.wikipedia.org/wiki/Pi#Infinite_series http://en.wikipedia.org/wiki/Pi#Infinite_series Quote: "The calculation of π was revolutionized by the development of infinite series techniques in the 16th and 17th centuries. An infinite series is the sum of the terms of an infinite sequence.[49] Infinite series allowed mathematicians to compute π with much greater precision than Archimedes and others who used geometrical techniques."
- sksksk 14y agoIf computing ever got powerful enough to compute pi to an nth amount of digits nearly instantaneously, would it be possible to compress everything by just saying "get the digits between x and y"
- lutusp 14y agoYes, but not in a way that would be useful. For a sufficiently complex message, the index into Pi that matches it might well be longer than the original message. So, yes, but no gain -- the result would be larger than the original. This would be true for a huge set of Pi digits and some imagined fast way to gain access to the right index -- the index into the set would likely be larger than the message it indexes.
- andreasvc 14y agoYou can do it but it wouldn't compress most things because the x and y will be larger than the input.
- tzs 14y agoAs the other replies have noted, you would generally not actually save anything. Let's put some numbers behind that. Consider all possible strings of n bits. There are 2^n of these. If each is represented by an index into pi, we have 2^n indexes. The best possible case is that the indexes all point within the first 2^n bits of pi, which allows them to be represented by integers from 0 to 2^n-1. Representing such an integer takes n bits. Result: representing an n bit string by its index into pi takes in general at least n bits to represent the index. There is no compression to be had here.
- walle_ 14y agoI did a quick test for this, would add a comment to the stackexchange thread, but it's closed now. Test at https://github.com/walle/pi2ascii https://github.com/walle/pi2ascii The algorithm can be greatly improved though.
- ramses0 14y agohttp://yro.slashdot.org/story/01/03/17/1639250/illegal-prime-number-unzips-to-decss http://yro.slashdot.org/story/01/03/17/1639250/illegal-prime... This is from WAAAY back in the day. "A person named Phil Carmody has found a very interesting prime number. When converted to hexadecimal, the result is a gzip that contains a DeCSS implementation. I've posted a short bit of Java here that takes the prime as a command line parameter and dumps the result to standard out if you want to test it." ...I actually ran it once upon a time, although I didn't check if the links were current. While slightly different context (prime #'s vs. PI) the concept is the same. If you dig deep enough into prime numbers and it contains the "illegal" topic du-jour expressed as a zip file... well, I won't put it past PI containing almost everything else as well.
- ritratt 14y agoIt represents a fractal.
- SeanDav 14y agoThis is similar to the Infinite Monkeys theorem and is more nuanced than many people think. http://milesmathis.com/monkey.html http://milesmathis.com/monkey.html http://en.wikipedia.org/wiki/Infinite_monkey_theorem http://en.wikipedia.org/wiki/Infinite_monkey_theorem
- Evbn 14y agoIt isn't a gag. It is a (conjectured, tested, not proven) mathematical fact explained on the SE page. It is relevant to hackernews as a illustration of the effectiveness of seemingly pointless pictures of text as memes, obnoxious though they be.
- generalobs 14y agoThe conclusion does not follow from the premise. The fact that "pi is an infinite, non-repeating decimal" (while easily provable true) does not imply that every number combination exists somewhere in pi. For example, if you removed all the 7's from pi, producing a new number, (i.e. 3.1415926535899323... instead of pi, which is 3.14159265358979323...) the new number would still be an "infinite, non-repeating decimal." But if your encoding calls for a seven in the date, time, or manner of your death , the new "infinite, non-repeating decimal" no longer contains it anywhere.