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 ]
There are no comments on this comment yet.