nLab
Chaitin's incompleteness theorem

Contents

Idea

The Chaitin incompleteness theorem is a kind of incompleteness theorem in the context of complexity theory. It says roughly that within any sufficiently strong formal system SS, there is an upper bound on provable complexity: a natural number LL such that for no given string of data is there is a formal proof in SS that its Kolmogorov complexity exceeds LL.

Note that LL is not an upper bound on complexity; on the contrary, there are only finitely many strings with complexity LL or less, and all of the infinitely many others must have complexity larger than LL. The system SS may even be capable of proving this, but it still cannot prove any particular example.

References

Expositions and surveys include