Normal Sequences with Non-Maximal Automatic Complexity

This paper examines Automatic Complexity, a complexity notion introduced by Shallit and Wang in 2001. We demonstrate that there exists a normal sequence $T$ such that $I(T)=0$ and $S(T)\le 1\mathrm{/}2$, where $I(T)$ and $S(T)$ are the lower and upper automatic complexity rates of $T$ respectively. We furthermore show that there exists a Champernowne sequence $C$, i.e. a sequence formed by concatenating all strings of length $1$ followed by concatenating all strings of length $2$ and so on, such that $S(C)\le 2\mathrm{/}3$.