Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Introduction to Algorithmic Information Theory (vwh.net)
1 point by edw519 on Oct 22, 2009 | hide | past | favorite | 1 comment


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




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: