Milk chocolate? Dark chocolate? The most devoted chocoholics surely face a daily dilemma over which bar to choose. If we restrict ourselves to these two choices, repetition is very hard to avoid. What exactly do we mean? Let L stand for milk chocolate and N for dark chocolate. Our fickle chocoholic, unwilling to taste the same kind twice in a row, cannot begin with LL or NN. So let's start with LN. Dark chocolate cannot come next (that would give LNN, repeating N). Let us therefore continue with milk chocolate: LNL. At this point, our chocolate lover is doomed to repetition: LNLL (L is repeated) or LNLN (and the pattern LN is repeated). We say that squares are unavoidable.
Fair enough—but what about cubes? Can we write a sequence of Ls and Ns in which no pattern appears three times in a row, as in the word "blablabla"? The answer is yes! And constructing this sequence recursively is easier than it looks.
From chocolate to binary
------------------------
The first mathematician to encounter this famous sequence was Eugène Prouhet (1817–1867), in 1851, while working on a problem in arithmetic. The sequence is so rich that it was subsequently rediscovered in entirely different fields, notably by Axel Thue (1863–1922) in 1912, in connection with problems in combinatorics on words, and then by Marston Morse (1892–1977), the father of Morse theory, in a differential geometry problem in 1921! Hence the name "(Prouhet–)Thue–Morse word (or sequence)", or, more simply, "Morse word".
Let us set our chocolatey concerns aside for a moment and, more conventionally, denote milk chocolate by 0 and dark chocolate by 1. Here, the digits 0 and 1 must be regarded simply as characters, not as numbers. We start with the word m0 = 0 and apply the following simple transformation to each character: the morphism defined by
(0) = 01 and (1) = 10.
