Mathematics: Came across the following gag. Is it true?

http://math.stackexchange.com/questions/216343/came-across-the-following-gag-is-it-true

by bjourne • 14 years ago

68 80 14 years ago

math.stackexchange.com

lutusp14• 14 years ago

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.

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."

gabemart2• 14 years ago

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?

notatoad• 14 years ago

It'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.

lutusp14• 14 years 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.

cdavid2• 14 years ago

It 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).

lutusp14• 14 years ago

Yes, 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• 14 years 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.

lutusp14• 14 years ago

Still 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.

damian2000• 14 years ago

Sounds similar to the 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• 14 years ago

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.

xk_id• 14 years ago

Do you have any bibliography for this topic? I would be very grateful, I'm extremely interested in this.

lifeformed• 14 years ago

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.

teraflop• 14 years ago

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.

Evbn6• 14 years ago

Yes. Recall the DeCSS controversery in USA, and the Wicket-Cricket wars in fiction's HHGTTG

randomdata2• 14 years ago

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.

phylofx• 14 years ago

Well, obviously, everything exists in the infinite - somewhere. A completely trivial realization, however.

ColinWright2• 14 years ago

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.

BasDirks2• 14 years 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, but an interesting thought-exercise.

lutusp14• 14 years 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. :)

BasDirks2• 14 years ago

I 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.

Evbn6• 14 years ago

But 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• 14 years ago

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.

Information theory is weird.

Edit: here's the original: http://jubal.westnet.com/hyperdiscordia/universal_library.ht...

ma2rten• 14 years ago

You are not accounting for meta information, such as which volumes go together in which order to form which book.

Robin_Message• 14 years ago

The point of a library containing every possible book is you don't need any meta information – if it has every possible book, it doesn't matter what order you put the volumes, or pages, or words together.

And that's why the library containing every possible book contains no information (think, for every correct maths textbook, there is one with every fact negated, one with every number replaced with the Unicode symbol for a cake, and very many that are wrong in all manner of nastily subtle ways.)

jasomill2• 14 years ago

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...

tripzilch2• 14 years 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? :)

mherdeg• 14 years ago

Borges's library doesn't actually contain every possible book, just every possible book of a certain length (it's finite but very large).

Fun fact about Quine -- he didn't actually write the first known self-printing program! http://en.wikipedia.org/wiki/Quine_(computing)

rsaarelm• 14 years ago

You can find every possible book longer than the default length split into several volumes.

bo10243• 14 years ago

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.

carstimon• 14 years ago

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.

Careful, that doesn't follow. The library could contain all finite books, but no infinite book.

tripzilch2• 14 years ago

> 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.

Yes, for a normal library this would be the case. But this library contains every possible book.

So the index list you're asking for, describing which volumes comprise what book in what order, is the complete list of all possible orderings of volumes up to the maximum book length.

You don't really need that list, because you know exactly what it looks like.

But then, you don't really need the volumes either, because you know what they look like too (being all combinations of N bits).

So yeah, you'd just need a 0 and a 1.

I already got a copy of that library, and the cool thing is that it doubles as a light switch.

isleyaardvark• 14 years ago

>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'.

surement• 14 years ago

If your itunes library contained every possible audio file, then yes, you could.

lmm• 14 years ago

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.

newhouseb• 14 years ago

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.

caf• 14 years ago

Sadly, there isn't enough energy in the entire Universe to cycle even a 16x16 black and white grid through all of its possible states.

randomdata2• 14 years ago

Unless you happen to own a quantum computer.

cammil• 14 years ago

Infinite 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• 14 years ago

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.

TazeTSchnitzel• 14 years ago

It's also quite slow...

digeridoo• 14 years ago

a. 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 π.

lutusp14• 14 years 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.

sp3324• 14 years ago

You'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.

sksksk• 14 years ago

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"

lutusp14• 14 years ago

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.

andreasvc• 14 years ago

You can do it but it wouldn't compress most things because the x and y will be larger than the input.

tzs2• 14 years ago

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.

walle_• 14 years ago

I 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

The algorithm can be greatly improved though.

ramses0• 14 years ago

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• 14 years ago

It represents a fractal.

SeanDav• 14 years ago

This is similar to the Infinite Monkeys theorem and is more nuanced than many people think.

http://milesmathis.com/monkey.html

http://en.wikipedia.org/wiki/Infinite_monkey_theorem

Evbn6• 14 years ago

It 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.

Mathematics: Came across the following gag. Is it true?

Related Stories