Note: I come from a mathematics background.
The Thue-Morse sequence $ t_n$ is a binary sequence that takes the value $ 0$ at the positive integer $ n$ if the number of $ 1$ s in its binary expansion is even, $ 1$ otherwise.
A definition that is closer to computer science states that $ t_n$ is the binary sequence obtained by starting with $ 0$ and successively appending the boolean complement of the sequence obtained so far.
Thus, $ t_n$ begins $ 0,1,1,0,1,0,0,1,\ldots$
This sequence is of much interest in mathematics, but so far I have not come across any applications in computer science. This surprises me, for the two following reasons:
- The Thue-Morse sequence is automatic, i.e., the sequence is fully characterized by a finite automaton,
- It is a binary sequence.
What theoretic or practical applications of the Thue-Morse sequence are there in computer science?