Kolmogorov complexity is not computable #

complexity grows unboundedly (exists_incompressible) yet, were it computable, one could search for the least string whose complexity reaches a given bound k. That search is a partial recursive description of an incompressible string using only the natLen k bits of k, so the invariance theorem bounds its complexity by natLen k + O(1). Since natLen is the binary length and grows logarithmically, the two facts collide: the searched string has complexity at least k but at most natLen k + O(1) < k for large k (Berry's paradox).

Main statements #

• complexity_not_computable — complexity is not a computable function.