Morse-Thue-sekvens

Morse-Thue-sekvensen är en oändlig sekvens av nollor och ettor ( bitar ), först föreslog 1906 av den norske matematikern Axel Thue som ett exempel på en aperiodisk rekursivt beräkningsbar teckensträng[ specificera ] . Det finns två varianter av sekvensen, erhållna från varandra genom bitinversion:

10010110011010010110100110010110 … ( OEIS Sequence A010059 ) - valfritt 01101001100101101001011001101001… (sekvens A010060 i OEIS ) - huvud

Morse-Thue-sekvensen är det enklaste exemplet på en fraktal och används i fraktala bildkomprimeringsalgoritmer .

Definitioner

En sekvens kan definieras på många olika ekvivalenta sätt:

Utföra transformationen ; , med den första iterationen : $0\högerpil 01$ $1\högerpil 10$ $ett$

ett tio 1 0 0 1 1 0 0 1 0 1 1 0

Vi börjar från 1. Vid varje steg lägger vi till inversen av detta tal till talet. Inversionen erhålls genom att ersätta alla nollor med ettor och ettor med nollor. Till exempel kommer inversen av talet 1001 att vara talet 0110. (På ett annat sätt kan inverteringen av talet beskrivas på följande sätt: detta är ett tal som kompletterar det som redan har skrivits till ett tal som endast består av ettor; till exempel 1001+0110=1111 i det binära talsystemet)

Steg 1: 1 Steg 2: 10 Steg 3: 1001 Steg 4: 10010110 Steg 5: 1001011001101001 ...

Låt oss skriva siffrorna 0,1,2,3... i rad i det binära systemet, och räkna antalet siffror 1 i varje tal. (Vi får sekvensen A000120 i OEIS .) Sedan tar vi resten av detta tal när vi dividerar med 2.

i decimalnotation	i binärt	antal enheter	antal enheter mod 2
0	0	0	0
ett	01	ett	ett
2	tio	ett	ett
3	elva	2	0
fyra	100	ett	ett
5	101	2	0
6	110	2	0
7	111	3	ett

Historik

Sekvensen upptäcktes 1851 av Prouhet ( fr. E. Prouhet ), som fann dess tillämpning i talteorin, men inte beskrev sekvensens exceptionella egenskaper. Och först 1906 återupptäckte Axel Thue den, när han studerade kombinatorik.

Publiceringen av Thues verk i Tyskland gick spårlöst, och Marson Morse återupptäckte sekvensen 1921, och tillämpade den i differentialgeometri.

Sekvensen har upptäckts oberoende många gånger: till exempel upptäckte stormästaren Max Euwe dess tillämpning i schack, och visade hur man spelar oändligt utan att bryta mot reglerna för oavgjort.

Egenskaper

Symmetrier

Som vilken fraktal som helst har Morse-Thue-sekvensen ett antal symmetrier. Så sekvensen förblir densamma:

När du tar bort alla element på jämna ställen:

10 01 01 10 01 10 10 01 01 10 10 01 10 01 01 10... 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1...

När du ersätter två delar som du kan göra en helhet av, med två andra karaktärer. Detta innebär att sekvensen inte kan arkiveras med Huffman-algoritmen , eftersom sekvensen som är "arkivet" kommer att sammanfalla med Morse-Thue-sekvensen själv:

1001 0110 0110 1001 0110 1001 1001 0110... 1 0 0 1 0 1 1 0...

Andra egenskaper

Sekvensen innehåller aldrig tre identiska på varandra följande delar (det är omöjligt att möta " AAA" , där " A" - sekvenser av nollor och ettor);
Den diskreta Fouriertransformen av sekvensen har samma maxima vid frekvenserna ⅓ och ⅔;
Ett tal vars binära representation är Morse-Thue-sekvensen kallas Prue-Thue-Morse-talet:

\tau =\summa _{{i=0}}^{{\infty }}{\frac {t_{i}}{2^{{i+1}}}}=0.412454033640\ldots

(sekvens A014571 i OEIS ),

var finns elementen i Morse-Thue-sekvensen. Detta nummer är transcendentalt (bevisat av K. Mahler 1929 ). $t_{i}$

Variationer och generaliseringar

Generalisering till godtyckligt alfabet

Givet ett godtyckligt alfabet på n tecken , kan man komponera exakt n olika cykliska permutationer av detta alfabet. Sedan, genom att ersätta varje "bokstav" i alfabetet med motsvarande permutation, kan man få en Morse-Thue-sekvens. Så till exempel kan tre cykliska permutationer göras av tre tecken "1", "2", "3": "123", "231", "312":

1\högerpil 123

2\högerpil 231

3\högerpil 312

ett 1 2 3 1 2 3 2 3 1 3 1 2 1 2 3 2 3 1 3 1 2 2 3 1 3 1 2 1 2 3 3 1 2 1 2 3 2 3 1...

Multidimensionell generalisering

Den flerdimensionella Morse-Thue-sekvensen definieras på liknande sätt. Till exempel är en tvådimensionell sekvens (matris) gränsen för en sekvens, vars nästa medlem erhålls från den föregående med hjälp av transformationen

1\högerpil {\begin{matrix}1&0\\0&1\end{matrix}}

;

0\högerpil {\begin{matrix}0&1\\1&0\end{matrix}}

10010110\cdots

01101001\cdots

01101001\cdots

10010110\cdots

\vdots \quad \vdots \quad \vdots \quad \ddots

Den tvådimensionella Morse-Thue-sekvensen kan också representeras som en uppsättning endimensionella.

Länkar

Weisstein, Eric W. Morse -Thue Sequence på Wolfram MathWorld .