3 ms·
If we're doing Kolmogorov complexity reposts: http://forwardscattering.org/post/7 http://forwardscattering.org/post/7 http://forwardscattering.org/post/14 http:
by Ono-Sendai 10y ago
If we're doing Kolmogorov complexity reposts:
http://forwardscattering.org/post/7 http://forwardscattering.org/post/7
http://forwardscattering.org/post/14 http://forwardscattering.org/post/14
- mafribe 10y agoHow many times do you want people to tell you that everybody knows that Kolmogorov complexity (KC) is only defined up to a constant? This does not affect the results that people use KC for, like the incompressibility of most strings.
- Ono-Sendai 10y agoThat's what my second post linked above addresses. I think it does affect the 'incompressibility of most strings' result. I'm fine with not rehashing the argument though, unless you're keen to do so :)
- mafribe 10y agoWhat you need to do is produce a programming language L such that the existence of incompressibility of strings becomes false, e.g. contradict Theorem 2.2.1 of Li & Vitanyi.