# nLab Chaitin's incompleteness theorem

Contents

### Context

#### Constructivism, Realizability, Computability

intuitionistic mathematics

# 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 $S$, there is an upper bound on provable complexity: a natural number $L$ such that for no given string of data is there is a formal proof in $S$ that its Kolmogorov complexity exceeds $L$.

Note that $L$ is not an upper bound on complexity; on the contrary, there are only finitely many strings with complexity $L$ or less, and all of the infinitely many others must have complexity larger than $L$. The system $S$ 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.