Kolmogorov complexity is uncomputable
Kolmogorov complexity
Kolmogorov complexity is uncomputable
Kolmogorov complexity measures the shortest program needed to produce an object, reflecting its computational resource requirements. This concept generalizes classical information theory and is named after Andrey Kolmogorov.
The notion of Kolmogorov complexity allows for stating and proving impossibility results similar to Cantor's diagonal argument, Gödel's incompleteness theorem, and Turing's halting problem. Specifically, no program can compute a lower bound for each text's Kolmogorov complexity that returns a value larger than the program's own length.
Example
Consider a simple text "hello". A shorter program might be "print 'hello'", while a longer program could be a detailed explanation of how to print "hello". The Kolmogorov complexity of "hello" is lower for the shorter program.
Remember this
Understanding the uncomputability of Kolmogorov complexity is crucial for grasping the limitations of computational systems and the inherent unpredictability in certain computational tasks.
Text adapted from Wikipedia, licensed under CC BY-SA 4.0.
Related concepts
Halting problem
Alan Turing proved the halting problem is undecidable
Overlapping subproblems
Ever calculated a huge Fibonacci sequence by hand?
Graph (abstract data type)
Time complexity of BFS and DFS: O(V + E)
Computational complexity of matrix multiplication
O(n³) naive matrix multiplication
Shannon's source coding theorem: you can't compress below entropy
Can you squeeze endless text into fewer bits without losing anything?
O(n log n) is the lower bound for comparison-based sorting
Ever wonder why sorting can't be faster than a certain point?
Swipe through 100 ML concepts daily
Open Pocket Polymath