🧠 Why No Program Can Fully Measure Complexity

Exploring the limits of computability through Kolmogorov complexity and Chaitin’s incompleteness theorem.

Imagine you wanted to write a program that measures how "complex" a piece of text is. Not just stylistically or linguistically, but in a deep mathematical sense — how compressible is the text? How much information does it truly contain?

This question leads us to the idea of Kolmogorov complexity. Formally, the Kolmogorov complexity of a string is the length of the shortest possible program (in a fixed programming language) that produces that string as output and then halts. A string like "aaaaaaaaaa" is very compressible — you can describe it with a short loop. But a string like "d82jJmF1a9z" (if truly random) might not have a shorter description than itself.

Naturally, we might ask:
Can we write a program that computes this complexity for any text?

Here’s where things get fascinating — and frustrating.