nLab
Chaitin's incompleteness theorem

Contents

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

Last revised on October 28, 2014 at 19:04:01. See the history of this page for a list of all contributions to it.