Visualizza wikitesto di Successione di Thue-Morse

[[Image:Morse-Thue sequence.gif|frame|right|Animazione che mostra l'inizio della costruzione della successione di Thue–Morse]]
La '''successione di Thue-Morse''', chiamata anche '''successione di Prouhet-Thue-Morse''', è una sequenza di [[Sistema numerico binario|cifre binarie]] che trova applicazioni in vari settori della [[matematica]].

La [[Successione (matematica)|successione]] inizia con:<ref>{{OEIS|A010060}}</ref>
:0110100110010110100101100110100110010110011010010110100110010110...
Agli 0 e agli 1 si può sostituire qualunque altra [[coppia (matematica)|coppia]] di simboli, senza che la struttura logica della successione ne risenta<ref>Per esempio la [[OEIS:A001285|sequenza A001285 dell'OEIS]] consiste nella stessa successione con i simboli (1,2) invece di (0,1).</ref>.

== Storia ==
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<ref>{{fr}} {{Cita pubblicazione|autore=Prouhet, E.|titolo=Mémoir sur quelques relations entre les puissances des nombres.|rivista=C. R. Adad. Sci. Paris Sér. 1|volume=33|pagine=225|anno=1851}}</ref>. Il primo a farlo fu, nel 1906, [[Axel Thue]], che usò la sequenza per fondare la [[combinatoria delle parole]]<ref>{{de}} {{cita pubblicazione|autore=[[Axel Thue|Thue, Axel]]|titolo=Über unendliche Zeichenreihen|rivista=Norske vid. Selsk. Skr. Mat. Nat. Kl.|volume=7|pagine=1-22|anno=1906|url=http://books.google.it/books/about/%C3%9Cber_unendliche_Zeichenreihen.html?id=-gwpGwAACAAJ&redir_esc=y}}</ref><ref>{{de}} {{cita pubblicazione|autore=[[Axel Thue]]|titolo=Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen.|rivista=Norske vid. Selsk. Skr. Mat. Nat. Kl.|volume=1|pagine=1-67|anno=1912|url=https://www.worldcat.org/title/uber-die-gegenseitige-lage-gleicher-teile-gewisser-zeichenreihen/oclc/9939656}}</ref>. 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]]<ref>{{en}} {{cita pubblicazione|autore=[[Marston Morse|Morse, Marston]]|titolo=Recurrent Geodesics on a Surface of Negative Curvature|rivista=Transactions of the American Mathematical Society|volume=22|pagine=84-100|anno=1921|url=https://www.ams.org/journals/tran/1921-022-01/S0002-9947-1921-1501161-8/S0002-9947-1921-1501161-8.pdf}}</ref>.

La successione di Thue-Morse è stata riscoperta indipendentemente diverse volte, anche da matematici non professionisti. Per esempio il [[Grande maestro internazionale|gran maestro di scacchi]], ex-campione del mondo 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 (a quei tempi la regola richiedeva che le posizioni ripetute della scacchiera fossero consecutive, è stata poi modificata in modo che la triplice ripetizione anche non consecutiva di una posizione facesse terminare con una patta la partita) e prolungare infinitamente il gioco<ref>{{nl}} {{cita pubblicazione|autore=Max Euwe|titolo=Mengentheoretische Betrachtungen über das Schachspiel|rivista=Proc. Konin. Akad. Wetenschappen (Amsterdam)|anno=1929|url=http://books.google.it/books/about/Mengentheoretische_Betrachtungen_%C3%BCber_d.html?id=WHgotwAACAAJ&redir_esc=y}}</ref>, sfruttando la sua proprietà di essere priva di sottostringhe ripetute tre volte consecutive.

== Definizione ==
[[File:Thue-Morse Squares.PNG|thumb|upright=0.6|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 ===
L'<math>n</math>-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 due cifre 1: quindi il quinto simbolo della successione di Thue-Morse è 0. Denotiamo con <math>t_n</math> l'<math>n</math>-esimo numero della successione di Thue-Morse. Il matematico [[John Conway]] ha definito ''numero odioso''<ref>{{OEIS|A000069}}</ref> ogni numero intero <math>n</math> tale che <math>t_n=1</math> e ''numero malvagio''<ref>{{OEIS|A001969}}</ref> ogni numero intero tale che <math>t_n=0</math> (si tratta di un [[Calembour|gioco di parole]], nella [[lingua inglese]], tra ''<u>od</u>ious'' e ''<u>ev</u>il'', che significano "odioso" e "malvagio", e ''<u>od</u>d'' ed ''<u>ev</u>en'', che significano "dispari" e "pari").

=== Come sequenza ricorsiva ===
La successione di Thue-Morse è la sequenza che soddisfa la proprietà che, se <math>t_n</math> è l'<math>n</math>-esimo elemento della successione di Thue-Morse, allora:
:<math>t_0=0;</math>
:<math>t_{2n}=t_n,</math>
:<math>t_{2n+1}=1-t_n,</math>
per qualunque numero intero positivo <math>n.</math>

=== Come L-sistema ===
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 ===
La successione di Thue-Morse, se considerata come sequenza di bit, può essere definita [[algoritmo ricorsivo|ricorsivamente]] mediante la [[Negazione (matematica)|negazione]], aggiungendo a ogni passaggio alla sequenza il suo esatto opposto. Quando si posseggono i primi 2<sup>''n''</sup> elementi della stringa, si può così conoscerne i successivi 2<sup>''n''</sup>, che consistono nel bit opposto alla prima metà. Per 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:
[[Image:Morse-Thue sequence.gif|frame|right|Costruzione della sequenza di Thue-Morse con il metodo della negazione bit per bit]]
* ''T''<sub>0</sub> = 0.
* ''T''<sub>1</sub> = 01.
* ''T''<sub>2</sub> = 0110.
* ''T''<sub>3</sub> = 01101001.
* ''T''<sub>4</sub> = 0110100110010110.
* ''T''<sub>5</sub> = 01101001100101101001011001101001.
* ''T''<sub>6</sub> = 0110100110010110100101100110100110010110011010010110100110010110.

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

:<math>\prod_{i=0}^{\infty} (1 - x^{2^{i}}) = \sum_{n=0}^{\infty} (-1)^{t_n} x^{n},</math>

sempre considerando <math>t_n</math> come l'<math>n</math>-esimo elemento della successione.

== Proprietà matematiche ==
[[File:Parity relation 0011 1100 0011 1100.svg|thumb|upright=1.8|Cinque [[Matrice binaria|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<ref>Quella in alto a destra e quella in basso a sinistra.</ref> 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: ossia [[Sottostringa|sottostringhe]] ripetute nella forma ''xx'', dove ''x'' è una sequenza di bit. Non ci sono invece cubi, cioè stringhe nella forma ''xxx''<ref name="Morse">{{en}} {{cita pubblicazione|autore=Morse, M.; Hedlund, G. A.|titolo=Unending Chess, Symbolic Dynamics, and a Problem in Semigroups|rivista=Duke Mathematical Journal|volume=11|pagine=1-7|anno=1944|url=https://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.dmj/1077472364|urlmorto=sì|urlarchivio=https://web.archive.org/web/20160304054307/http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.dmj%2F1077472364|dataarchivio=4 marzo 2016}}</ref>. Non vi sono nemmeno quadrati sovrapposti, cioè stringhe 0''x''0''x''0 oppure 1''x''1''x''1.<ref name="Allouche">{{en}} {{cita libro|autore=Jean-Paul Allouche, Jeffrey Shallit|titolo=Automatic Sequences: Theory, Applications, Generalizations|pagine=152-153|data=21 luglio 2003|editore=Cambridge University Press|città=Cambridge|url=https://www.amazon.com/exec/obidos/ASIN/0521823323/ref=nosim/weisstein-20|ISBN=0-521-82332-3}}</ref> Per tutti gli <math>n>1</math>, il pezzo della successione di Thue-Morse dall'inizio a <math>t_{2n}</math> è [[numero palindromo|palindroma]]. Inoltre, contando gli 1 tra due 0 consecutivi in <math>t_{2n}</math> (cioè fino a <math>t_{2^n}</math>) e chiamando <math>q_n</math> come la stringa ottenuta concatenando tali valori (per esempio <math>q_1 = 2</math> e <math>q_2 = 2102012</math>), <math>q_n</math> è sempre una stringa palindroma e [[parola priva di quadrati|priva di quadrati]]<ref name="Morse"/>. Questo perché <math>T_n</math> non contiene mai quadrati sovrapposti e <math>T_n</math> è sempre palindromo.

La successione di Thue-Morse, pur non essendo una [[successione periodica]], è una [[sequenza ricorrente]]: ciò vuol dire che, prendendo una qualunque stringa <math>x</math> al suo interno, esiste sempre una lunghezza <math>L_x</math> (solitamente molto più grande della lunghezza di <math>x</math>) tale che qualunque pezzo della successione contenga sempre <math>x</math> almeno una volta. L'[[esponente critico]] della successione è 2.<ref>{{cita libro|autore=Dalia Krieger| titolo=Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26-29, 2006 | volume=4036 |serie=Lecture Notes in Computer Science | curatore=Oscar H. Ibarra, Zhe Dang | editore=Springer-Verlag | anno=2006 | isbn=3-540-35428-X | capitolo=On critical exponents in fixed points of non-erasing morphisms | pagine=280-291 | url=http://www.zentralblatt-math.org/zmath/en/search/?q=an:1227.68074&format=complete}}</ref> Definendo un'[[endofunzione]] <math>f(S)</math> 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 <math>f</math>: ossia <math>f(T)=T</math>, e <math>T</math> è dunque un [[punto fisso]] di <math>f</math>. L'unico altro punto fisso è quello che si ottiene negando la successione di Thue-Morse stessa, ossia sostituendo tutti gli 0 con 1 e viceversa; si tratta quindi sostanzialmente dell'unico punto fisso della funzione <math>f</math>.

=== Funzione generatrice ===
Definendo <math>F(x)</math> come la [[funzione generatrice]] della successione di Thue-Morse nel [[campo finito]] <math>\mathrm{GF}(2)</math>:

:<math>F(x)=0+1x+1x^2+0x^3+1x^4+ \dots</math>

si può dimostrare che <math>F</math> soddisfa l'[[equazione quadratica]]:

:<math>(1+x)F^2+F \equiv \frac{x}{1+x^2} (\mod{2}).</math>

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 π ===
Valgono le seguenti relazioni:<ref>{{en}} {{cita pubblicazione|autore=Woods, D. R.|titolo=Problem Proposal E2692|rivista=American Mathematical Monthly|volume=85|pagine=48|anno=1978}}</ref><ref>{{cita pubblicazione|autore=Robbins, D.|titolo=Solution to Problem E2692|rivista=American Mathematical Monthly|volume=86|pagine=394-295|anno=1979}}</ref>

:<math>\prod_{n=0}^{\infty} {\left( \frac{2n+1}{2n+2} \right)}^{(-1)^{t_n}}=\frac{\sqrt{2}}{2};</math>

:<math>\prod_{n=0}^{\infty} {\left( \frac{2n+1}{2n+2} \right)}^{2t_n}\left( \frac{2n+3}{2n+2} \right)=
\frac{2 \sqrt{2}}{\pi};</math> <ref name="Allouche"/>

:<math>\prod_{n=0}^{\infty} {\left( \frac{2n+1}{2n+2} \right)}^{2(1-t_n)}\left( \frac{2n+3}{2n+2} \right)
=\frac{ \sqrt{2}}{\pi}.</math> <ref name="Allouche"/>

== Applicazioni ==
=== Nel problema di Prouhet–Tarry–Escott ===
Il [[problema di Prouhet-Tarry-Escott]] chiede di trovare, dati due numeri interi <math>a>0</math> e <math>p\ge 0</math>, una [[partizione di un insieme|partizione]] dell'insieme dei [[Numero naturale|numeri naturali]] da 0 ad <math>a-1</math> in due [[Sottoinsieme|sottoinsiemi]] [[Insiemi disgiunti|disgiunti]] tali che ognuna delle somme delle potenze fino alla <math>p</math>-esima dei rispettivi elementi sia la stessa, ovvero:

:<math>\sum_{x \in S_0} x^r = \sum_{x \in S_1} x^r </math>

per ogni esponente intero <math>r</math> da 1 a <math>p</math>. Il problema ha sempre almeno una soluzione se <math>a</math> è un [[multiplo]] di <math>2^{p+1}</math>, che si ottiene mettendo nel sottoinsieme <math>S_0</math> i numeri <math>n</math> per cui <math>t_n =0</math> (cioè i numeri malvagi) e nel sottoinsieme <math>S_1</math> i numeri <math>n</math> per cui <math>t_n =1</math> (i numeri odiosi), o viceversa.

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

=== La successione come grafico di Turtle ===
[[File:Kochsim.gif|thumb|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 <math>t(n)=0</math>, vai avanti di una unità di lunghezza;
* se <math>t(n)=1</math>, ruota in senso antiorario di 60[[Grado d'arco|°]].
Ciò illustra la natura [[autosomiglianza|autosomigliante]] della successione<ref>{{en}} Jun Ma, Judy Holdoner, [http://www2.kenyon.edu/people/holdenerj/StudentResearch/WhenThueMorsemeetsKochJan222005.pdf When Thue-Morse meets Koch]</ref>.

=== Nella distribuzione delle risorse ===
La successione di Thue-Morse fornisce una soluzione ai problemi di distribuzione di risorse tra due contendenti. Per 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 [[Soluto|soluti]], e quindi con uguale sapore<ref name="Richman">{{en}} {{cita pubblicazione|autore=Robert M. Richman|titolo=Recursive Binary Sequences of Differences|rivista=Complex Systems|volume=13|pagine=381–392|anno=2001|lingua=en|url=http://www.complex-systems.com/pdf/13-4-3.pdf}}</ref><ref>{{cita news|cognome=Abrahams|nome=Marc|titolo=How to pour the perfect cup of coffee|url=http://www.guardian.co.uk/education/2010/jul/13/perfect-coffee-improbable-research|pubblicazione=The Guardian|data=12 luglio 2010|accesso=11 settembre 2012}}</ref>.
Questo è stato provato dal matematico [[Robert Richman]] che, pur senza nominare esplicitamente la successione, ha descritto le relazioni delle [[Funzione a gradino|funzioni gradino]] descritte da T<sub>''n''</sub> nell'[[Intervallo (matematica)|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 T<sub>''n''</sub>, e che quindi la funzione a gradino descritta da T<sub>''n''</sub> è [[polinomi ortogonali|ortogonale]] ai [[polinomi]] di [[Grado di un polinomio|grado]] ''n''-1<ref name="Richman"/>.

=== Nella teoria dei giochi combinatori ===
{{...|matematica}}

== Note ==
<references/>

== Bibliografia ==
* {{Cita libro|cognome1= Allouche |nome1= Jean-Paul |cognome2= Shallit |nome2= Jeffrey |wkautore2= Jeffrey Shallit | isbn = 978-0-521-82332-6 |editore= Cambridge University Press |titolo= Automatic Sequences: Theory, Applications, Generalizations |anno= 2003 | zbl=1086.11015 |lingua= en }}
* {{Cita libro|cognome1=Berstel |nome1=Jean |cognome2=Lauve |nome2=Aaron |cognome3=Reutenauer |nome3=Christophe |cognome4=Saliola |nome4=Franco V. |titolo=Combinatorics on words. Christoffel words and repetitions in words |serie=CRM Monograph Series |volume=27 |città=Providence, RI |editore=American Mathematical Society |anno=2009 | isbn=978-0-8218-4480-9 |url=http://www.ams.org/bookpages/crmm-27 | zbl=1161.68043 |lingua=en }}
* {{Cita libro|cognome=Bugeaud |nome=Yann |titolo=Distribution modulo one and Diophantine approximation |url=https://archive.org/details/distributionmodu0000buge |serie=Cambridge Tracts in Mathematics |volume=193 |città=Cambridge |editore=Cambridge University Press |anno=2012 | isbn=978-0-521-11169-0 | zbl=pre06066616 }}
* {{Cita libro|cognome=Lothaire |nome=M. |titolo=Algebraic combinatorics on words |altri=With preface by Jean Berstel and Dominique Perrin |edizione=Reprint of the 2002 hardback |serie=Encyclopedia of Mathematics and Its Applications |volume=90|editore=Cambridge University Press |anno=2011 | isbn=978-0-521-18071-9 | zbl=1221.68183 |lingua=en }}
* {{Cita libro|cognome=Lothaire |nome=M. |titolo=Applied combinatorics on words |url=https://archive.org/details/appliedcombinato0000loth |altri=A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé|serie=Encyclopedia of Mathematics and Its Applications |volume=105 |città=Cambridge |editore=Cambridge University Press |anno=2005 | isbn=0-521-84802-4 | zbl=1133.68067 |lingua=en }}
* {{Cita libro|cognome=Pytheas Fogg |nome=N. |altri=Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. |titolo=Substitutions in dynamics, arithmetics and combinatorics |serie=Lecture Notes in Mathematics |volume=1794 |città=Berlin |editore=Springer-Verlag |anno=2002 | isbn=3-540-44141-7 | zbl=1014.11015 |lingua=en }}
* {{en}} Allouche, J.-P. and Cosnard, M. "The Komornik-Loreti Constant Is Transcendental." ''Amer. Math. Monthly'' '''107''', 448-449, 2000.
* {{en}} Allouche, J.-P. and Shallit, J. "The Ubiquitous Prouhet-Thue-Morse Sequence." In ''Sequences and Their applications'', Proc. SETA'98 (Ed. C. Ding, T. Helleseth, and H. Niederreiter). New York: Springer-Verlag, pp.&nbsp;1–16, 1999.
* {{en}} Allouche, J.-P. and Shallit, J. "Example 5.1.2 (The Thue-Morse Sequence)." ''Automatic Sequences: Theory, Applications, Generalizations''. Cambridge, England: Cambridge University Press, pp.&nbsp;152–153, 2003.

== Voci correlate ==
* [[Costante di Prouhet-Thue-Morse]]
* [[Grafico di Turtle]]
* [[Funzione generatrice]]
* [[Successione di Rudin-Shapiro]]

== Altri progetti ==
{{interprogetto|preposizione=sulla}}

==Collegamenti esterni==
* {{Collegamenti esterni}}
* {{en}} Allouche, J.-P.; Shallit, J. O. [https://www.cs.uwaterloo.ca/~shallit/Papers/ubiq.ps The Ubiquitous Prouhet-Thue-Morse Sequence]
* {{en}} [https://web.archive.org/web/20090912104941/http://www.geocities.com/jan.schat/ThueMorse.PDF Reducing the influence of DC offset drift in analog IPs using the Thue-Morse Sequence].
* {{cita web|http://xmau.wikispaces.com/morse|Esposizione divulgativa della successione di Thue-Morse}}
* {{en}} [http://lcni.uoregon.edu/~dow/Geek_art/Simple_recursive_systems/Tesselations/Thue-Morse_tilings/Thue-Morse_tilings.html Thue-Morse sequence tilings and patterns] {{Webarchive|url=https://web.archive.org/web/20120427191933/http://lcni.uoregon.edu/~dow/Geek_art/Simple_recursive_systems/Tesselations/Thue-Morse_tilings/Thue-Morse_tilings.html |date=27 aprile 2012 }}: immagini generate dalla successione di Thue-Morse
* {{en}} [http://reglos.de/musinum MusiNum - The Music in the Numbers]: Software per generare musica autosomigliante dalla successione di Thue-Morse e da altre sequenze analoghe

{{Teoria dei numeri}}
{{Portale|Matematica}}

[[Categoria:Combinatoria]]
[[Categoria:Punti fissi]]
[[Categoria:Successioni di interi]]