When two strings have the same Kolmogorov Complexity, one of them might take significantly longer to "decompress". Shouldn't we then say that this string has higher information content?
It feels to me like Kolmogorov Complexity (while very elegant) might just be a crude approximation to a measure that also takes into account the time it takes to print the string.
That seems unlikely because actually computing kolmogorov complexity is impossible, even approximating it is super hard. But you can run random numbers through compression software, and if they compress, something is very wrong.
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 :)
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.
21 comments
[ 3.0 ms ] story [ 54.3 ms ] threadIt feels to me like Kolmogorov Complexity (while very elegant) might just be a crude approximation to a measure that also takes into account the time it takes to print the string.
http://people.idsia.ch/~juergen/speedprior.html
.... But seriously, can we not all just learn higher math?
It was a sleep deprived and childish reply.
1. N. K. Vereschagin, V. Uspensky, Alexander Shen : Kolmogorov Complexity (English draft in preparation: http://www.lirmm.fr/~ashen/kolmbook-eng.pdf)
2. Downey, Hirschfeldt: Algorithmic Randomness and Complexity (http://www.springer.com/gp/book/9780387955674)
3. Andre Nies: Computability and Randomness (https://global.oup.com/academic/product/computability-and-ra...)
in addition to the now classic book by Li and Vitanyi that others have mentioned.
This does not affect the results that people use KC for, like the incompressibility of most strings.
It was very interesting to find out how efficient it was in authorship attribution, even having 100 possible authors.