Thue-Morsejevo zaporedje

Iz Wikipedije, proste enciklopedije

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}}\; .$

[uredi] 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}:{\Bbb Z}\to{\Bbb 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

[uredi] Nekaj lastnosti

Desetiška vrednost zapisa Thue-Morsejevega zaporedja v dvojiškem sestavu je Thue-Morsejeva konstanta P. Od leta 1977 vemo, da je to število transcendentno.

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 večkratnik 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 lastnost lahko prenesemo na zamisel o samodejnem zaporedju.

[uredi] Zgodovina

Thue-Morsejevo zaporedje je prvi raziskoval P. Prouhet leta 1859, ki ga je uporabil v teoriji števil. Prouhet ni izrečeno opredelil zaporedja. To je storil Axel Thue leta 1906, ki ga je 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.

[uredi] Glej tudi

zajčje zaporedje

[uredi] Zunanje povezave

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

Kategorija: Zaporedja

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Thue-Morsejevo zaporedje

Iz Wikipedije, proste enciklopedije

Vsebina

[uredi] Določitev

[uredi] Nekaj lastnosti

[uredi] Zgodovina

[uredi] Glej tudi

[uredi] Zunanje povezave

Views

Navigacija

občestvo

podpora

Iskanje

V drugih jezikih