|
|
|
|
|
|
by tromp
2309 days ago
|
|
|
In particular, since the number of binary strings of length n exceeds the number of shorter strings, there must be a string of length n that's not described by a shorter program, i.e. that's incompressible. More generally, the fraction of strings of length n that can be compressed by k or more bits is less than 2^{-k}. |
|
|