L-system de Thue-Morse

Como nosso próximo exemplo de L-system, nós apresentamos o sistema de Thue-Morse:

A seqüência de gerações começa como segue:

Table 4: Gerações de Thue-Morse

O número de organismos claramente dobra a cada geração, então:  . A primeira questão que nós devemos fazer é qual é o processo global que emerge, se é que existe.

Para responder esta questão, nós observamos que a geração  aparece no início de  . Se nós olharmos o que segue, nós eventualmente concluímos que ele repete  , exceto que cada a foi substituído por um b e cada b foi substituído por um a. Para cada palavra w em  , nós definimos R(w) como sendo a imagem espelho da palavra onde nós trocamos a por b e b por a. Então o processo global é

Já que   é o começo de  , este L-system produz no limite uma seqüência infinita   de a's e b's que começa:

Esta seqüência tem muitas propriedades importantes e é conhecida como a seqüência de Thue-Morse. Axel Thue apareceu com ela em 1912  no seu estudo de linguagens formais. Marston Morse redescubriu a mesma seqüência em 1917  no estudo das dinâmicas das superfícies. Nós podemos produzir uma fórmula muito interessante para os termos desta seqüência se trocarmos a por 1 e b por -1. No caso, a aplicação da repetição de R é o mesmo que multiplicação por -1. Escreva a seqüência como

onde cada   é  +1 ou  -1. A n-ésima geração é

Então a geração  n+1 consiste deste string   seguido por

Isto estabelece a fórmula

para todo  . Parar isto funcionar para qualquer  dado, sugere que nós precisamos expressar m como uma soma de potências de 2, isto é, nós precisamos encontrar a expansão binária de m:

com  . Por exemplo,

Em dígitos binários, nós escreveríamos  .  O número de potências de 2 ocorrendo é igual ao número de 1's na expansão binária. Então aplicando nossa fórmula nós temos

já que  . Em geral,

onde t é o número de 1's na expansão binária de m. Um outro exemplo:

Thue provou um teorema muito interessante sobre a seqüência Thue-Morse.

TEOREMA: (Thue-Morse é livre de cubo) Não há substring da seqüência Thue-Morse da forma www em nenhum string finito w de a's e b's.

Isto significa que não há substring aaa ou ababab ou babbabbab, etc. De fato, Morse provou um teorema um pouco mais forte mostrando que não há string da forma EEe onde E é um dado string e e é o primeiro símbolo em E. Esta prova primeiro apareceu em um "paper" que mostrou que sobre um certo conjunto de regras para finalizar o jogo de xadrez era possível ter um jogo infinito. Por outro lado, a razão original que Morse introduziu nesta seqüência é que, sem ser periódica, ela ainda tem um alto grau de redundância.

TEOREMA: (Morse; Thue-Morse é recorrente) Seja n um inteiro positivo. Existe um outro inteiro positivo N (maior que n normalmente) tal que, dado algum substring w de comprimento n na seqüência Thue-Morse, nós podemos garantir que todo substring W  de comprimento N contêm um cópia do string w.

Isto significa que todo string finito que ocorre na seqüência Thue-Morse ocorre várias vezes infinitamente. Uma estimação explícita de N pode der provado: de k é o menor inteiro tal que  , então nós podemos garantir  que qualquer substring de comprimento   na seqüência Thue-Morse contém o string  dado w de comprimento n.