Kolmogorov Complexity and Compression Distance

Re:Kolmogorov Complexity and Compression Distance by causal on Saturday March 30, 2024 @04:59PM (#39878599)

This seems to assume that KC can be infinite. That must have been proven at some point? Otherwise it may be that there is some upper-bound for L which happens to also be the KC for a KC-computer.

[ Parent | on HN ]

Re:Kolmogorov Complexity and Compression Distance by srcreigh on Saturday March 30, 2024 @06:25PM (#39879276)

yes, it’s a pigeonhole principle argument. A bit tricky to actually enumerate everything. Imagine KC had a limit k. Then there’s a fixed number of strings that can be compressed to k characters. so considering how there’s an infinite number of strings of length greater than k, they can’t all be compressed to be at most k. Therefore KC has no limit

[ Parent | on HN ]

Re:Kolmogorov Complexity and Compression Distance by tromp on Sunday March 31, 2024 @04:14AM (#39882420)

KC(x) is always finite for any finite x. What we can say instead is that KC is unbounded. I.e. there is no finite bound on the value of KC(x).

[ Parent | on HN ]