Successione di Thue-Morse

Da Wikipedia, l'enciclopedia libera.

La successione di Thue–Morse, chiamata anche successione di Prouhet–Thue–Morse, è una sequenza di cifre binarie che trova applicazioni in vari settori della matematica. La successione inizia con:

0110100110010110100101100110100110010110011010010110100110010110...[1]

Agli 0 e agli 1 si può sostituire qualunque altra coppia di simboli, senza che la struttura logica della successione ne risenta[2].

Definizione[modifica | modifica wikitesto]

Gli elementi della successione di Thue-Morse disposti in quadrati concentrici, dall'interno verso l'esterno. Qui i trattini corti rappresentano gli 0, e i lunghi gli 1. Si notino le differenze strutturali (evidenti negli angoli) tra i livelli pari e dispari.

Esistono diversi modi equivalenti di definire la successione di Thue-Morse.

Definizione diretta[modifica | modifica wikitesto]

L'n-esimo numero della successione di Thue-Morse è 0 se l'espressione di n in base 2 contiene un numero pari di 1, ed è uno se ne contiene una quantità dispari. Per esempio, l'espressione binaria del numero 5 è 101, che contiene 2 cifre 1: quindi il quinto simbolo della successione di Thue-Morse è uno 0. Il matematico John Conway ha definito numeri odiosi[3] i numeri interi n tali che tn=1 e numeri malvagi[4] quelli per i quali tn=0 (si tratta di un gioco di parole, nella lingua inglese, tra odious e evil, che significano "odioso" e "malvagio", e odd ed even, che significano "dispari" e "pari").

Come sequenza ricorsiva[modifica | modifica wikitesto]

La successione di Thue-Morse è la sequenza che soddisfa la proprietà che, se tn è l'n-esimo elemento della successione di Thue-Morse, allora

t0=0;
t2n=tn, e
t2n+1=1-tn

per qualunque numero naturale n.

Come L-sistema[modifica | modifica wikitesto]

La successione di Thue-Morse è l'output del seguente sistema di Lindenmayer:

  variabili  0  1
  costanti  nessuna
  inizio     0
  regole     (0 → 01), (1 → 10)

Questo significa che può essere ottenuta iniziando da uno 0 e operando la sostituzione tutti gli 0 con 01 e tutti gli 1 con 10, e ripetendola all'infinito. Si noti che questo procedimento lascia invariati i valori iniziali della stringa, mentre ogni iterazione raddoppia il numero di cifre.

Definizione per negazione bit per bit[modifica | modifica wikitesto]

La successione di Thue-Morse, se considerata come sequenza di bit, può essere definita ricorsivamente mediante la negazione, aggiungendo ad ogni passaggio alla sequenza il suo esatto opposto. Quando si posseggono i primi 2n elementi della stringa, si può così conoscerne i successivi 2n, che consistono nel bit opposto alla prima metà. Ad esempio, sapendo che il primo bit è uno 0, dato che la sua negazione è 1 il bit successivo sarà 1; e dato che la negazione di 01 è 10 i successivi due bit saranno 10; e così via. I primi passaggi sono i seguenti:

Costruzione della sequenza di Thue-Morse col metodo della negazione bit per bit
  • T0 = 0.
  • T1 = 01.
  • T2 = 0110.
  • T3 = 01101001.
  • T4 = 0110100110010110.
  • T5 = 01101001100101101001011001101001.
  • T6 = 0110100110010110100101100110100110010110011010010110100110010110.

Come prodotto infinito[modifica | modifica wikitesto]

La successione di Thue-Morse può essere definita come la successione di 0 e 1 che soddisfa la seguente relazione:

 \prod_{i=0}^{\infty} (1 - x^{2^{i}}) = \sum_{n=0}^{\infty} (-1)^{t_n} x^{n} \mbox{,} \! ,

sempre considerando tn come l'n-esimo elemento della successione.

Proprietà matematiche[modifica | modifica wikitesto]

Cinque matrici binarie quadrate che se lette linea per linea esprimono i primi elementi della successione di Thue-Morse. Ciascuna è ottenuta accostando in un quadrato quattro delle matrici precedenti, di cui due[5] ribaltate.

Essendo la successione di Thue-Morse costruibile per negazioni e aggiunte successive, tramite il metodo della negazione dei blocchi di bit, essa contiene molti quadrati: ovvero, sottostringhe ripetute nella forma xx, dove x è una sequenza di bit. Non ci sono invece cubi, cioè stringhe nella forma xxx[6]. Non vi sono nemmeno quadrati sovrapposti, cioè stringhe 0x0x0 oppue 1x1x1.[7]
Per tutti gli n>1, il pezzo della successione di Thue-Morse dall'inizio a t2n è palindroma. Inoltre, contando gli 1 tra due 0 consecutivi in T2n (cioè fino a t2n) e chiamando qn come la stringa ottenuta concatenando tali valori (ad esempio q1 = 2 e q2 = 2102012), qn è sempre una stringa palindroma e priva di quadrati[6]. Questo perché Tn non contiene mai quadrati sovrapposti e Tn è sempre palindromo.
La successione di Thue-Morse, pur non essendo una sequenza periodica, è una sequenza ricorrente: ciò vuol dire che, prendendo una qualunque stringa x al suo interno, esiste sempre una lunghezza Lx (solitamente molto più grande della lunghezza di x) tale che qualunque pezzo della sequanza contenga sempre x almeno una volta. L'esponente critico della sequenza è 2.[8]
Definendo un'endofunzione f(S) sull'insieme delle sequenze binarie, che operi su una sequenza sostituendo tutti gli 0 con 01 e tutti gli 1 con 10, la successione di Thue-Morse rimarrà invariata dall'applicazione di f: ovvero, f(T)=T, e T è dunque un punto fisso di f. L'unico altro punto fisso è quello che si ottiene negando la successione di Thue-Morse stessa, ossia sostituento tutti gli 0 con 1 e viceversa; si tratta quindi sostanzialmente dell'unico punto fisso della funzione f.

Funzione generatrice[modifica | modifica wikitesto]

Definendo F(x) come la funzione generatrice della successione di Thue-Morse nel campo finito GF(2)

F(x)=0+1x+1x^2+0x^3+1x^4+...

si può dimostrare che F soddisfa l'equazione quadratica

(1+x)F^2+F \equiv \frac{x}{1+x^2}  (\mod{2})

Questa equazione ha due soluzioni: la successione di Thue-Morse e la sua complementare, che si ottiene sostituendo gli 0 con gli 1 e gli 1 con gli 0.

Legami con √2 e π[modifica | modifica wikitesto]

Sono state provate le seguenti relazioni:

\prod_{n=0}^{\infty} {\left( \frac{2n+1}{2n+2} \right)}^{(-1)^{t_n}}=\frac{\sqrt{2}}{2}[9][10]
\prod_{n=0}^{\infty} {\left( \frac{2n+1}{2n+2} \right)}^{2t_n}=\frac{2 \sqrt{2}}{\pi}[7]
\prod_{n=0}^{\infty} {\left( \frac{2n+1}{2n+2} \right)}^{2(1 - t_n)}=\frac{\sqrt{2}}{\pi}[7]

Applicazioni[modifica | modifica wikitesto]

Nel problema di Prouhet–Tarry–Escott[modifica | modifica wikitesto]

Il problema di Prouhet–Tarry–Escott chiede di trovare, dati due numeri interi a>0 un intero p≥0, una partizione dell'insieme dei numeri naturali da 0 ad a-1 in due sottoinsiemi disgiunti tali che ognuna delle somme delle potenze fino alla p-esima dei rispettivi elementi sia la stessa, ovvero

\sum_{x \in S_0} x^r = \sum_{x \in S_1} x^r per ogni esponente intero r da 1 a p

Il problema ha sempre almeno una soluzione se a è un multiplo di 2p+1, che si ottiene mettendo nel sottoinsieme S0 i numeri n per cui tn = 0 -cioè i numeri malvagi- e nel sottoinsieme S1 i numeri n per cui tn = 1 -i numeri odiosi-, o viceversa.

Dato un qualunque insieme S di a elementi disponibili in una progressione aritmetica, dal teorema binomiale segue inoltre che se a è un multiplo di 2p+1 esiste sempre almeno una partizione dell'insieme delle p-esime potenze degli elementi di S in due sottoinsiemi le cui somme degli elementi siano uguali.

La successione come grafico di Turtle[modifica | modifica wikitesto]

La curva di Koch, un frattale ottenibile dalla successione di Thue-Morse

Un grafico di Turtle è una curva ottenuta in base a una sequenza e a uno schema di istruzioni prefissato. La successione di Thue-Morse codifica la curva di Koch, usando come input e le seguenti istruzioni:

  • Se t(n) = 0, vai avanti di una unità di lunghezza;
  • Se t(n) = 1, ruota in senso antiorario di 60°.

Ciò illustra la natura autosomigliante della successione[11].

Nella distribuzione delle risorse[modifica | modifica wikitesto]

La successione di Thue-Morse fornisce una soluzione ai problemi di distribuzione di risorse tra due contendenti. Ad esempio, se A e B vogliono spartirsi un gruppo di elementi, volendo trovare un modo per evitare che uno dei due abbia la possibilità di scegliere elementi di qualità maggiore occorre che ad A spetti la 1°, 4°, 6°, 7°, ecc. scelta (uno più i numeri ordinali malvagi) e a B la 2°, 3°, 5°, 8°, ecc. scelta (uno più i numeri odiosi). Questa proprietà può anche essere applicata, per esempio, per suddividere il contenuto di una caffettiera in un dato numero di tazze di caffè con uguale concentrazione di soluti, e quindi con uguale sapore[12][13]. Questo è stato provato dal matematico Robert Richman che, pur senza nominare esplicitamente la successione, ha descritto le relazioni delle funzioni gradino descritte da Tn nell'intervallo [0,1] con la funzione di Walsh e la funzione di Rademacher. Richman ha mostrato che la loro n-esima derivata può essere espressa in termini di Tn, e che quindi la funzione a gradino descritta da Tn è ortogonale ai polinomi di grado n-1[12].

Nella teoria dei giochi combinatori[modifica | modifica wikitesto]

Storia[modifica | modifica wikitesto]

La successione di Thue-Morse è stata originariamente studiata dal matematico Eugène Prouhet nel 1851, che la applicò alla teoria dei numeri senza però definirla esplicitamente[14]. Il primo a farlo fu, nel 1906, Axel Thue, che usò la sequenza per fondare la combinatoria delle parole[15][16]. Tuttavia, la successione fu portata all'attenzione della comunità internazionale solo nel 1921, grazie al lavoro di Marston Morse che la applicò alla geometria differenziale[17].
La successione di Thue-Morse è stata riscoperta indipendentemente diverse volte, anche da matematici non professionisti. Per esempio, il gran maestro di scacchi e docente di matematica Max Euwe ha scoperto nel 1929 un modo di usare la successione per aggirare una regola degli scacchi che considera la partita finita in patta in caso di ripetizioni continuate di sequenze di mosse, e poter prolungare infinitamente il gioco[18], sfruttando la sua proprietà di essere priva di sottostringhe ripetute tre volte consecutive.

Collegamenti esterni[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

  1. ^ (EN) Sequenza A010060 in On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
  2. ^ Per esempio, la sequenza A001285 dell'OEIS consiste nella stessa successione coi simboli (1,2) invece di (0,1).
  3. ^ (EN) Sequenza A000069 in On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
  4. ^ (EN) Sequenza A001969 in On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
  5. ^ Quella in alto a destra e quella in basso a sinistra.
  6. ^ a b (EN) Morse, M.; Hedlund, G. A., Unending Chess, Symbolic Dynamics, and a Problem in Semigroups in Duke Mathematical Journal, vol. 11, 1944, pp. 1-7.
  7. ^ a b c (EN) Jean-Paul Allouche, Jeffrey Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge, Cambridge University Press, 21 luglio 2003, pp. 152-153, ISBN 0-521-82332-3.
  8. ^ Dalia Krieger, On critical exponents in fixed points of non-erasing morphisms in Oscar H. Ibarra, Zhe Dang (a cura di), Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26-29, 2006, Lecture Notes in Computer Science, vol. 4036, Springer-Verlag, 2006, pp. 280-291, ISBN 3-540-35428-X.
  9. ^ (EN) Woods, D. R., Problem Proposal E2692 in American Mathematical Monthly, vol. 85, 1978, p. 48.
  10. ^ Robbins, D., Solution to Problem E2692 in American Mathematical Monthly, vol. 86, 1979, pp. 394-295.
  11. ^ (EN) Jun Ma, Judy Holdoner, When Thue-Morse meets Koch
  12. ^ a b (EN) (EN) Robert M. Richman, Recursive Binary Sequences of Differences in Complex Systems, vol. 13, 2001, pp. 381–392.
  13. ^ Marc Abrahams, How to pour the perfect cup of coffee in The Guardian, 12 luglio 2010. URL consultato l'11 settembre 2012.
  14. ^ (FR) Prouhet, E., Mémoir sur quelques relations entre les puissances des nombres. in C. R. Adad. Sci. Paris Sér. 1, vol. 33, 1851, p. 225.
  15. ^ (DE) Thue, Axel, Über unendliche Zeichenreihen in Norske vid. Selsk. Skr. Mat. Nat. Kl., vol. 7, 1906, pp. 1-22.
  16. ^ (DE) Axel Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. in Norske vid. Selsk. Skr. Mat. Nat. Kl., vol. 1, 1912, pp. 1-67.
  17. ^ (EN) Morse, Marston, Recurrent Geodesics on a Surface of Negative Curvature in Transactions of the American Mathematical Society, vol. 22, 1921, pp. 84-100.
  18. ^ (NL) Euwe, Max, Mengentheoretische Betrachtungen über das Schachspiel in Proc. Konin. Akad. Wetenschappen (Amsterdam), 1929.
Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica