4 ms·
http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity For example, consider the following two strings of length
by Maro 17y ago
http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity
For example, consider the following two strings of length 64, each containing only lowercase letters, numbers, and spaces:
abababababababababababababababababababababababababababababababab
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf
The first string has a short English language description, namely "ab 32 times", which consists of 11 characters. The second one has no obvious simple description (using the same character set) other than writing down the string itself, which has 64 characters.
- tel 17y agoMore specifically, Kolmogorov randomness which is closely linked to compressibility. A sufficiently long string which has a generating program longer than itself is random. Since "4..." is highly compressible --- its unpredictable error is zero --- it is unlikely to be governed by a random process. The longer the series is, the less likely.
- klipt 17y agoThe funny thing is that pi's decimal digits have very nice "random" properties (e.g. asymptotically uniform distribution), but it's extremely compressible. Which partly explains why it turns up more often than most other transcendentals: http://en.wikipedia.org/wiki/Algorithmic_probability http://en.wikipedia.org/wiki/Algorithmic_probability