I'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.
Not sure if we're on the same page here, but this does not conform to what we know about information theory.
First, as someone else mentioned we'd have to have a maximum book length or else your library contains an infinite number of books, which is simply absurd because there would, for instance, be a book that contained all of the finite books inside it, in alphabetical order.
Second, using your compression technique, we'd still need to have some numbering on the volumes, and to describe a book, we'd have to do so by a list of numbers describing which volumes comprise it and in what order.
Third, this makes clear what is happening in your reductio ad absurdum argument -- we can reduce the volumes down to one dash, one dot; but then each book needs to contain a listing in order of which "volume" is in which order. So we're just writing the boks in binary again.
You 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...
Information theory already has the answer: the original library, of all 1 million bit strings, contains zero (or very close to zero) information. Paradoxically enough, it contains far less information than one of those 1 million bit strings selected at random.
A library is not just a collection of all possible patterns, is perhaps the real lesson here.
>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.
We have to stop there. I cannot simply replace my iTunes library with two text files containing a '0' and a '1'.
Assuming 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.
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."
I 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?
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.
"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.
Ever 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.
This 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.
"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."
In 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.
Does 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.
Only 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.
The 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.
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 π.
> 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.
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, but an interesting thought-exercise.
> 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.
If 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"
Yes, 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.
As 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.
This 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.
[+] [-] IsaacL|13 years ago|reply
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.ht...
[+] [-] bo1024|13 years ago|reply
First, as someone else mentioned we'd have to have a maximum book length or else your library contains an infinite number of books, which is simply absurd because there would, for instance, be a book that contained all of the finite books inside it, in alphabetical order.
Second, using your compression technique, we'd still need to have some numbering on the volumes, and to describe a book, we'd have to do so by a list of numbers describing which volumes comprise it and in what order.
Third, this makes clear what is happening in your reductio ad absurdum argument -- we can reduce the volumes down to one dash, one dot; but then each book needs to contain a listing in order of which "volume" is in which order. So we're just writing the boks in binary again.
[+] [-] ma2rten|13 years ago|reply
[+] [-] mherdeg|13 years ago|reply
Fun fact about Quine -- he didn't actually write the first known self-printing program! http://en.wikipedia.org/wiki/Quine_(computing)
[+] [-] jasomill|13 years ago|reply
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...
[+] [-] lmm|13 years ago|reply
A library is not just a collection of all possible patterns, is perhaps the real lesson here.
[+] [-] isleyaardvark|13 years ago|reply
We have to stop there. I cannot simply replace my iTunes library with two text files containing a '0' and a '1'.
[+] [-] lutusp|13 years ago|reply
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
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|13 years ago|reply
[+] [-] cdavid|13 years ago|reply
[+] [-] rorrr|13 years ago|reply
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.
[+] [-] ramses0|13 years ago|reply
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.
[+] [-] newhouseb|13 years ago|reply
[+] [-] caf|13 years ago|reply
[+] [-] jbri|13 years ago|reply
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|13 years ago|reply
[+] [-] damian2000|13 years ago|reply
"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|13 years ago|reply
[+] [-] lifeformed|13 years ago|reply
[+] [-] teraflop|13 years ago|reply
[+] [-] randomdata|13 years ago|reply
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.
[+] [-] Evbn|13 years ago|reply
[+] [-] cammil|13 years ago|reply
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.
[+] [-] digeridoo|13 years ago|reply
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|13 years ago|reply
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.
[+] [-] SeanDav|13 years ago|reply
http://milesmathis.com/monkey.html
http://en.wikipedia.org/wiki/Infinite_monkey_theorem
[+] [-] walle_|13 years ago|reply
Test at https://github.com/walle/pi2ascii
The algorithm can be greatly improved though.
[+] [-] BasDirks|13 years ago|reply
[+] [-] lutusp|13 years ago|reply
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. :)
[+] [-] sksksk|13 years ago|reply
[+] [-] lutusp|13 years ago|reply
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.
[+] [-] tzs|13 years ago|reply
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.
[+] [-] andreasvc|13 years ago|reply
[+] [-] phylofx|13 years ago|reply
[+] [-] ColinWright|13 years ago|reply
[+] [-] ritratt|13 years ago|reply
[+] [-] generalobs|13 years ago|reply
[deleted]
[+] [-] Evbn|13 years ago|reply
It is relevant to hackernews as a illustration of the effectiveness of seemingly pointless pictures of text as memes, obnoxious though they be.