News for hackers. Stuff that matters.

A comment on Kolmogorov Complexity – A Primer (2012). Parent comment

Re:Kolmogorov Complexity – A Primer (2012) by mafribe on Sunday October 02, 2016 @10:00AM (#12622351)
How 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.

[ Parent | on HN ]
Re:Kolmogorov Complexity – A Primer (2012) by Ono-Sendai on Sunday October 02, 2016 @10:25AM (#12622452)
That'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 :)
[ Parent | on HN ]
Re:Kolmogorov Complexity – A Primer (2012) by mafribe on Monday October 03, 2016 @02:46AM (#12625787)
What 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.
[ Parent | on HN ]