O que é Sequência de Thue-Morse? Explique sua construção.
Passo 1
O enunciado pede para definirmos a sequência de Thue–Morse e explicarmos como ela é construída. O conteúdo envolve sequências recursivas em teoria de palavras e a paridade de dígitos em representação binária. Vamos usar tanto uma definição recursiva quanto uma via paridade de bits para mostrar a construção.
Passo 2
Definição recursiva. Começamos com
T_{0} = 0.
Dado o bloco T_{n}, definimos T_{n+1} como
T_{n+1} = T_{n}\,\|\,\overline{T_{n}},
onde “\|” significa concatenação de cadeias e \overline{T_{n}} é o complemento bit a bit de T_{n} (trocamos 0 por 1 e 1 por 0). Assim, os primeiros blocos são:
Sequência infinita. A sequência de Thue–Morse T é o limite
T = \lim_{n\to\infty} T_{n},
isto é, a cadeia infinita
T = 0110100110010110\cdots.
Ela tem propriedades interessantes, como evitar subcadeias do tipo www (“cubos”) e “overlaps”.
Passo 4
Definição via paridade de bits. Outra forma equivalente de definir o n-ésimo termo t_{n} de T é tomar a soma dos dígitos 1 na representação binária de n e computar essa soma módulo 2. Formalmente, se \mathrm{popcount}(n) é o número de 1’s em n, então
t_{n} = \mathrm{popcount}(n)\bmod 2.
Por exemplo, para n=5, escrevemos 5 em binário como 101, a soma dos dígitos 1 é 2, e 2\bmod 2=0, então t_{5}=0. Isso gera exatamente a mesma sequência vista acima.
Resposta
A sequência de Thue–Morse é a sequência infinita binária que se obtém recursivamente por