Timeline for How much can you compress information?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 5 at 19:45 | comment | added | Kaia | (Maybe a more convincing argument: If it were possible to compress arbitrary strings using Pi, you could do it recursively to achieve arbitrary compression: find the index-into-pi itself in pi, and the index of that, and so on. so it's ruled out by the pidgeonhole principle) | |
| Mar 5 at 18:09 | comment | added | Kaia | @Pica I believe the logic is the same for any length of string. There are 2^n bitstrings of length N, so in expectation you'd find the index of that bitstring at 2^n bits into pi, so the index takes N bits to express too. | |
| Mar 5 at 14:01 | comment | added | Pica | @Kaia - that is a a pretty rare edgecase though? Nobody compresses small stringlets.. | |
| Mar 5 at 10:15 | comment | added | U. Windl |
Without going into the details: Is there a proof that any string of digits can be found in Pi? Maybe try to replace the first 3 with 4 and then find the result in Pi...
|
|
| Mar 4 at 20:17 | comment | added | Kaia | "Pi compression" usually requires at least as many bits to store the index into pi. For instance, atractor.pt/cgi-bin/PI/pib27Search_vn.cgi finds "ROMEO" at position 71116480, which is 26 bits, while naievely encoding "ROMEO" in base-26 and converting to base-2 is 24 bits. (You can do a lot better with eg huffman coding) | |
| Mar 4 at 9:01 | history | edited | Pica | CC BY-SA 4.0 |
added 106 characters in body
|
| Mar 4 at 8:51 | history | answered | Pica | CC BY-SA 4.0 |