5 The incompressibility theorem
Shallit and Wang showed that the automatic complexity satisfies for almost all . 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 for any . The result also applies to nondeterministic automatic complexity . In that setting the result is tight inasmuch as for all .