Automaticity. IV: Sequences, sets, and diversity (Q679096)

The author continues his work on the ``automaticity'' of sequences; this is a measure of how far from being generated by a finite automaton a sequence is. The first paper on the subject is a joint work with \textit{Y. Breitbart} (note that this is reference [27] that appeared in J. Comput. Syst. Sci. 53, 10-25 (1996; Zbl 0859.68059)]; the second paper is a joint work with \textit{C. Pomerance} and \textit{J. M. Robson} (note that this paper appeared, this is reference [20], Theor. Comput. Sci. 180, 181-201 (1997)). The third paper is a joint work with \textit{I. Glaister} and has not appeared yet (reference [10]). In the nice paper under review the author proves many results having a strong analytic number theory flavor. For example he proves that the \(k\)-automaticity of the characteristic sequence of the prime integers is \(\Omega (m^{1/43})\). This gives a quantitative version of the Minsky-Papert theorem [\textit{M. Minsky} and \textit{S. Papert}, Unrecognizable sets of numbers, J. Assoc. Comput. Mach. 13, 281-286 (1966; Zbl 0166.00601)]. This gives an example of a sequence having a large \(k\)-automaticity for all \(k \geq 2\). The author also gives sequences having a low \(k\)-automaticity for all \(k\geq 2\), as well as sequences having low or high \(k\)-automaticities according to the values of \(k\). He also studies the \(k\)-automaticity of fixed points of homomorphisms. Finally the author introduces and studies the notion of ``diversity'', which is a strong non-automaticity.