2 ms·
Introduction to Algorithmic Information Theory
- JoeAltmaier 17y agoQuote "2. A truly random string is not significantly compressible; its description length is within a constant offset of its length. Formally we say K(x) = Theta(|x|), which means "K(x) grows as fast as the length of x". But any finite random sequence can be found at some point in a pseudo-random generated sequence of sufficient length; thus can always be described by the generator function and the seed.