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:

Določitev uredi

 
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:

 

Prvi člen je po dogovoru tako 0. Določimo prvih 2n členov in ustvarimo niz s. Naslednjih 2n členov tvori bitno negacijo s. Tako smo določili 2n+1 č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

 

kjer je tj 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 uredi

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 nX (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 nX 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 uredi

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 uredi

Zunanje povezave uredi