2automatic

2automatic, or 2-automatic sequences, are a class of sequences over a finite alphabet that are generated by finite automata reading the base-2 representations of the nonnegative integers. In practical terms, there exists a deterministic finite automaton with output (a DFAO) that, when fed the binary expansion of n (usually from most significant to least significant digit), outputs the nth term of the sequence. This framework places 2automatic sequences within the broader family of k-automatic sequences, with k = 2.

A standard example is the Thue–Morse sequence, where a_n is the parity of the number of 1s in the binary expansion of n. Another well-known 2automatic sequence is the regular paperfolding sequence. These sequences can be described succinctly by a small automaton and share several formal properties that arise from the finite-state nature of the generating device.

2automatic sequences have applications in combinatorics on words, number theory, and theoretical computer science. They are useful for constructing sequences with controlled complexity and for studying automaticity as a bridge between automata theory and symbolic dynamics. The class is closed under certain operations, such as uniform morphisms and projections, and provides a decidable framework for questions about regularity and growth.

Historically, the concept was developed within the theory of automatic sequences, with prominent foundational work by Allouche and Shallit. A key theoretical result is Cobham’s theorem, which states that a sequence cannot be simultaneously automatic in two multiplicatively independent bases (except for ultimately periodic sequences).

In summary, 2automatic sequences are finite-state generated sequences indexed by natural numbers via binary representations, exemplified by Thue–Morse and the paperfolding sequence, and connected to rich areas of mathematical logic and combinatorics.