5 The incompressibility theorem

Shallit and Wang showed that the automatic complexity \(A(x)\) satisfies \(A(x)\ge n/13\) for almost all \(x\in {\{ \mathtt{0},\mathtt{1}\} }^n\). They also stated that Holger Petersen had informed them that the constant 13 can be reduced to 7. Here we show that it can be reduced to \(2+\epsilon \) for any \(\epsilon {\gt}0\). The result also applies to nondeterministic automatic complexity \(A_N(x)\). In that setting the result is tight inasmuch as \(A_N(x)\le n/2+1\) for all \(x\).