I sistemi di Lindenmayer e la successione di Thue-Morse

Aristid Lindenmayer

Per definire una sequenza numerica molto spesso si specificano i primi elementi della sequenza e si fornisce una regola per generare gli infiniti elementi successivi. Per esempio, la celeberrima successione di Fibonacci si costruisce partendo dagli elementi 0 e 1, e rispettando la regola secondo la quale ogni termine successivo è la somma dei due che lo precedono.
Ora, proviamo a costruire una sequenza diversa, formata esclusivamente da zeri e uni. Il suo primo elemento è uno zero. La regola da rispettare è la seguente: ogni elemento genera il suo successore attraverso le sostituzioni 0 → 01 e 1 → 10. Il secondo termine della sequenza è quindi 01. Il terzo è 0110. Il quarto 01101001. E così via.

Il sistema di costruzione della sequenza rientra nella famiglia dei cosiddetti "L-systems", o sistemi di Lindenmayer. Questa famiglia di sistemi, a sua volta, fa parte del più ampio mondo dei "sistemi di riscrittura", nei quali, genericamente, vengono fissate alcune regole di sostituzione che possono essere applicate agli oggetti di un insieme.
Un sistema di riscrittura è un sistema di Lindenmayer se esistono:
1. una famiglia di simboli ammessi;
2. un elemento iniziale formato da una concatenazione di simboli ammess;
3. un insieme di regole di sostituzione per la generazione degli elementi successivi.

Disegni di piante generati mediante sistemi di Lindenmayer

Non deve stupire che questi sistemi prendano il loro nome non da un matematico o da un informatico, ma da un biologo. L'ungherese Aristid Lindenmayer, infatti, vissuto tra il 1925 e il 1989, ideò questo giochino di riscrittura per descrivere formalmente il comportamento delle cellule vegetali e la crescita di alcuni semplici organismi multicellulari, ad esempio particolari tipi di alghe. Successivamente i sistemi di Lindenmayer vennero applicati con successo anche a specie vegetali più complesse. Sono stati impiegati anche per generare frattali, mediante un processo di autosimilarità (un frattale costituito da più copie di se stesso, come il celebre triangolo di Sierpinski).

Torniamo all'esempio iniziale. In questo caso, i simboli ammessi sono 0 e 1, l'elemento iniziale è 0, e le regole di sostituzione sono quelle citate sopra: 0 → 01 e 1 → 10.
Diamo ancora un'occhiata ai primi termini della sequenza: 0, 01, 0110, 01101001, ... Balza all'occhio una prima proprietà: ogni elemento della successione è formato da un numero di cifre doppio rispetto al suo predecessore.
Un'altra caratteristica è la seguente: ogni elemento è costituito dal suo predecessore concatenato con il suo complemento. Detto altrimenti, ogni termine include il precedente come sua prima metà. Per esempio, abbiamo visto che il terzo termine è 0110. Per costruire il suo complemento basta invertire ogni cifra binaria, cioè trasformare gli zeri in uni e viceversa. Otteniamo quindi 1001. Il nostro quarto elemento è 0110 concatenato a 1001, cioè 01101001.

Ecco, abbiamo trovato un modo alternativo per definire in modo costruttivo la nostra sequenza, che viene illustrato nella figura a fianco.

In virtù della seconda proprietà del sistema, potremmo considerare un'altra sequenza: anziché la successione delle stringhe binarie che raddoppiano di lunghezza ad ogni passo, potremmo considerare un'unica stringa, quella di lunghezza infinita alla quale converge la sequenza che abbiamo preso in esame in precedenza: anche questa stringa può essere studiata come una successione, perché è formata da cifre binarie che ne costituiscono gli elementi.
I primi 16 termini della successione sono quindi: 0110100110010110.

Una volta formalizzata la successione in questo modo, saltano fuori alcune proprietà davvero sorprendenti. Ma andiamo in ordine.
Per cominciare, la successione viene chiamata di Thue-Morse, dai nomi dei due matematici che l'hanno studiata: il danese Axel Thue e l'americano Marston Morse.

Vediamo una prima proprietà: l'n-esimo termine della successione è uguale a:

• 0, se il numero n-1 espresso in forma binaria contiene un numero pari di uni;
• 1, se il numero n-1 espresso in forma binaria contiene un numero dispari di uni.

Attenzione: l'elemento che compare per primo nella sequenza è in realtà associato all'indice 0, non all'1. In binario, 0 si scrive ancora 0, che non contiene uni al suo interno. Zero può essere considerato un numero pari, quindi il primo elemento è 0. Vediamo ora, ad esempio, l'elemento associato a n=5: in binario 5 si scrive 101, che contiene due uni. Due è pari, quindi il sesto elemento è 0. Il nono elemento: 8 in binario è 1000, in cui compare un solo uno. Essendo uno dispari, il nono elemento è un 1. E così via.

Quel genio matematico che risponde al nome di John Conway e di cui ho parlato più volte (ad esempio qui), ha avuto un'ideona: ha chiamato "odiosi" i numeri interi n tali per cui l'n-esimo termine della sequenza di Thue-Morse è 1, e "malvagi" quelli per cui l'n-esimo termine è 0. Perché tutto questo odio e questa malvagità"? Soltanto un gioco di parole: in inglese "pari" si dice "even", che suona simile a "evil" ("malvagio"), e "dispari" si dice "odd", che assomiglia a "odious" ("odioso").

Un'altra curiosa proprietà è la seguente: fissato a 0 il termine associato a n=0, il termine associato a 2n (con n naturale qualsiasi) è uguale a quello associato a n, e il termine associato a 2n+1 è uguale al "complemento" del termine associato a n ("complemento" nel senso che 1 è il complemento di 0 e viceversa). Provare per credere.

Non è nemmeno difficile convincersi del fatto che, preso un qualsiasi n naturale, la porzione di successione formata dai primi 2n termini è palindroma, cioè si legge allo stesso modo da sinistra a destra e da destra a sinistra.

Ma il bello deve ancora venire. Intanto beccatevi le proprietà qui a fianco. Che la successione di Thue-Morse sia legata a quantità come la radice quadrata di 2 può sembra abbastanza normale, ma che anche qui venga fuori pi greco, beh, è già molto più stupefacente.
Ricordate il linguaggio Logo, quello che poteva essere usato, tra le altre cose, per guidare una tartaruga su un piano cartesiano?
Ebbene, immaginiamo che i termini successivi della sequenza di Thue-Morse rappresentino ordini impartiti alla tartaruga. Più precisamente, un 1 deve essere interpretato come "vai avanti di una posizione", e uno 0 come "girati in senso antiorario di 60°".
Secondo voi che disegno traccerà la tartaruga seguendo le cifre binarie della nostra sequenza? Proviamo a vedere.

Non si capisce molto, vero? Già, perché servono molti termini della sequenza, cioè molte istruzioni per  il simpatico rettile, perché il risultato cominci a prendere forma. Vediamo cosa succede dopo 2⁸ = 256, 2¹⁰ = 1024, 2¹² = 4096 e 2¹⁴ = 16384 istruzioni.

Vi ricorda qualcosa? Se scegliamo, per la cifra 1, una rotazione antioraria di 120° anziché 60°, si ottiene un disegno ancora più pulito:

Ebbene sì: è il fiocco di neve di Koch, uno dei frattali più famosi. Modificando ancora le regole della tartaruga, ma utilizzando sempre la successione di Thue-Morse, si ottengono risultati interessanti, come questi:

Per questi e altri divertimenti vi rimando al blog Three-Cornered Things di Zachary Abel.

Max Euwe

Una proprietà interessante della successione di Thue-Morse è l'assenza in essa di stringhe della forma XXX, dove X è una qualsiasi sequenza di cifre binarie. Un grande campione di scacchi come Machgielis "Max" Euwe (1901 – 1981), che oltre ad essere stato il quinto campione del mondo di scacchi tra il 1935 e il 1937, fu anche una brillante mente matematica, contestò una delle regole "tedesche" che vigevano nel gioco degli scacchi intorno al 1929: una partita poteva essere dichiarata patta se la stessa sequenza di mosse viene ripetuta per tre volte di seguito.
Sfruttando la successione di Thue-Morse, Euwe dimostrò che la regola non escludeva di per sè partite di lunghezza infinita.
Grazie a questa scoperta, venne accettata universalmente la regola in base alla quale una partita può essere dichiarata patta se una posizione si presenta per tre volte, indipendentemente da quali mosse l'abbiano determinata.

E qui mi fermo. La sequenza di Thue-Morse ha anche affascinanti connessioni con il gioco del Nim, con la risoluzione di problemi di distribuzione di risorse tra due contendenti, con la teoria dei numeri, con la combinatoria delle parole, e con un sacco di altre cose. Buon divertimento.