News for hackers. Stuff that matters.
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

There are no comments on this comment yet.