Thue-Morsejevo zaporedje

Thue-Morsejevo zaporedje (Morse-Thuejevo zaporedje ali Prouhet-Thue-Morsejevo zaporedje) je v matematiki dvojiško zaporedje, katerega začetni členi se v določenem vzorcu izmenjujejo (OEIS A010060).

Prvih 64 členov Thue-Morsejevega zaporedja je:

{0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,

1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,...}

Zaporedje je primer preprostega fraktala. Želvja grafika vodi do Kochove snežinke. Včasih zaporedje namesto dvojiških števk zapišejo z 1, 2 ali v obratnem vrstnem redu 1,0; levo, desno; zgoraj, spodaj. V tem smislu lahko o Thue-Morsejevem zaporedju govorimo kot o zaporedju danega urejenega para:

X_{\sigma }\in \left\{0,1\right\}^{\mathbb {N} }\!\,.

Določitev

Prikaz prvih členov Thue-Morsejevega zaporedja

V zgornji obliki lahko Thue-Morsejevo zaporedje kot zaporedje bitov določimo rekurzivno z enočleno operacijo bitne negacije b^* (npr. bitni dopolnitveni operator (bitni komplement) ~ v C-ju), ki spremeni vse bite operanda:

b^{\star }:{\mathbb {Z} }\to {\mathbb {Z} }\quad b^{\star }:(0,1)\mapsto (1,0)\!\,.

Prvi člen je po dogovoru tako 0. Določimo prvih 2ⁿ členov in ustvarimo niz s. Naslednjih 2ⁿ členov tvori bitno negacijo s. Tako smo določili 2ⁿ⁺¹ členov in z rekurzijo določimo naslednje.

Poglejmo si prvih nekaj korakov podrobneje:

začnemo z 0,
bitna negacija 0 je 1,
prva dva člena sta tako 01,
bitna negacija 01 je 10,
imamo prve 4 člene 0110,
bitna negacija 0110 je 1001,
s tem nastane prvih 8 členov 01101001,
in nadaljujemo enako.

Zaporedje lahko določimo kot

\prod _{i=0}^{\infty }(1-x^{2^{i}})=\sum _{j=0}^{\infty }(-1)^{t_{j}}x^{j}{\mbox{,}}\!\,

kjer je t_j j-ti člen, če začnemo označevati indekse z j = 0.

Dvorazsežna predstavitev Thue-Morsejevega zaporedja. S črno so označene enice, z belo pa nule

Nekaj značilnosti

Desetiška vrednost zapisa Thue-Morsejevega zaporedja v dvojiškem sestavu je Prouhet-Thue-Morsejeva konstanta P. Da je to število transcendentno, je leta 1929 dokazal Kurt Mahler.

Ker je vsak odsek v Thue-Morsejevem zaporedju določen z bitno negacijo začetnega člena in ker se pri vsakem koraku to ponovi, je zaporedje zapolnjeno s kvadrati - z zaporednimi ponavljajočimi se nizi. To pomeni, da je navedenih več XX, kjer je X poljuben niz. Ne obstajajo pa kocke - pojavitve XXX. Ne obstajajo tudi prekrivajoči kvadrati oblike 0X0X0 ali 1X1X1.

Zgornjo navedbo, da je Thue-Morsejevo zaporedje »zapolnjeno s kvadrati« lahko izrazimo še natančneje: zaporedje je rekurenčno, kar pomeni da za dan končen niz X v zaporedja, obstaja odsek dolžine n_X (velikokrat precej daljši od X), v katerem se X pojavi v vsakem odseku dolžine n. Najlažji način za tvorbo rekurentnega zaporedja je tvorba periodičnega zaporedja, kjer se zaporedje po danem številu korakov m ponovi v celoti. Tako lahko n_X nastavimo na mnogokratnik m, ki je večji kot dvojna dolžina X. Vendar je Thue-Morsejevo zaporedje rekurentno, ni pa periodično, oziroma slučajno periodično - periodično po začetnem neperiodičnem odseku.

Iz množice dvojiških zaporedij samih vase lahko določimo funkcijo f z zamenjavo vsake 0 iz zaporedja z 01 in vsake 1 z 10. Potem, če je T Thue-Morsejevo zaporedje, je tudi f(T) spet T, oziroma T je negibna točka f. V bistvu je T edina negibna točka f - edina druga negibna točka je bitna negacija T, ki je preprosto Thue-Morsejevo zaporedje na (1,0) namesto na (0,1). To značilnost lahko prenesemo na zamisel o samodejnem zaporedju.

Zgodovina

Thue-Morsejevo zaporedje je prvi raziskoval Eugène Prouhet leta 1851 in ga uporabil v teoriji števil. Prouhet ni izrečeno opredelil zaporedja. To je storil Axel Thue leta 1906 in ga uporabil pri kombinatoričnem študiju besed. Thue je objavljal v norveščini in so njegovo delo v začetku spregledali. Z delom Marstona Morseja na področju diferencialne geometrije iz leta 1921 so postali pozorni na zgodnejše Thuejevo delo. Zaporedje so večkrat neodvisno odkrili. Med odkritelji niso bili vedno raziskovalci v matematiki ampak tudi drugi. Šahovski velemojster in učitelj matematike Max Euwe, (svetovni šahovski prvak 1935) ga je leta 1929 odkril pri uporabi v šahu.

Glej tudi

Zunanje povezave

https://web.archive.org/web/20000914051126/http://www.math.uwaterloo.ca/~shallit/Papers/ubiq.ps -- veliko uporab in nekaj zgodovine (angleško)
http://mathworld.wolfram.com/Thue-MorseSequence.html -- MathWorld, nekaj drugih uporab (angleško)
http://www.research.att.com/projects/OEIS?Anum=A010059 -- zaporedje v Sloaneovi ekciklopediji celoštevilčnih zaporedij na (1,0) (angleško)
http://www.research.att.com/projects/OEIS?Anum=A001285 -- zaporedje na (1,2) (angleško)