Morse-Thue sekvens
Morse-Thue sekvensen er en uendelig sekvens af nuller og enere ( bits ), først foreslået i 1906 af den norske matematiker Axel Thue som et eksempel på en aperiodisk rekursivt beregnelig tegnstreng[ angiv ] . Der er to varianter af sekvensen, opnået fra hinanden ved bit-inversion:
10010110011010010110100110010110 … ( OEIS Sequence A010059 ) - valgfri 01101001100101101001011001101001… (sekvens A010060 i OEIS ) - hovedMorse-Thue-sekvensen er det enkleste eksempel på en fraktal og bruges i fraktale billedkomprimeringsalgoritmer .
Definitioner
En sekvens kan defineres på mange forskellige ækvivalente måder:
- Udførelse af transformationen ; , tager for den første iteration :
- Vi starter fra 1. På hvert trin tilføjer vi det omvendte af dette tal til tallet. Inversionen opnås ved at erstatte alle nuller med enere og enere med nuller. For eksempel vil det omvendte af tallet 1001 være tallet 0110. (På en anden måde kan inversionen af tallet beskrives som følger: dette er et tal, der supplerer det, der allerede er skrevet til et tal, der kun består af enere; f.eks. 1001+0110=1111 i det binære talsystem)
- Lad os skrive tallene 0,1,2,3... på række i det binære system, og tælle antallet af cifre 1 i hvert tal. (Vi får sekvensen A000120 i OEIS .) Så tager vi resten af dette tal, når vi dividerer med 2.
| i decimalnotation | i binær | antal enheder | antal enheder mod 2 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| en | 01 | en | en |
| 2 | ti | en | en |
| 3 | elleve | 2 | 0 |
| fire | 100 | en | en |
| 5 | 101 | 2 | 0 |
| 6 | 110 | 2 | 0 |
| 7 | 111 | 3 | en |
Historie
Sekvensen blev opdaget i 1851 af Prouhet ( fr. E. Prouhet ), som fandt dens anvendelse i talteori, men ikke beskrev sekvensens exceptionelle egenskaber. Og først i 1906 genopdagede Axel Thue det, mens han studerede kombinatorik.
Udgivelsen af Thues arbejde i Tyskland gik sporløst, og Marson Morse genopdagede sekvensen i 1921 og anvendte den i differentialgeometri.
Sekvensen er blevet opdaget uafhængigt mange gange: for eksempel opdagede stormester Max Euwe dens anvendelse i skak, og viste, hvordan man spiller uendeligt uden at bryde reglerne for remis.
Egenskaber
Symmetrier
Som enhver fraktal har Morse-Thue-sekvensen en række symmetrier. Så rækkefølgen forbliver den samme:
- Når du fjerner alle elementer på lige steder:
- Når du udskifter to dele, hvorfra du kan lave en helhed, med to andre tegn. Dette betyder, at sekvensen ikke kan arkiveres ved hjælp af Huffman-algoritmen , da sekvensen, der er "arkivet", vil falde sammen med selve Morse-Thue-sekvensen:
Andre egenskaber
- Sekvensen indeholder aldrig tre identiske på hinanden følgende dele (det er umuligt at opfylde " AAA" , hvor " A" - sekvenser af nuller og enere);
- Den diskrete Fourier-transformation af sekvensen har de samme maksima ved frekvenserne ⅓ og ⅔;
- Et tal, hvis binære repræsentation er Morse-Thue-sekvensen, kaldes Prue-Thue-Morse-tallet:
hvor er elementerne i Morse-Thue-sekvensen. Dette tal er transcendentalt (bevist af K. Mahler i 1929 ).
Variationer og generaliseringer
Generalisering til vilkårligt alfabet
Givet et vilkårligt alfabet på n tegn , kan man komponere nøjagtigt n forskellige cykliske permutationer af dette alfabet. Derefter kan man ved at erstatte hvert "bogstav" i alfabetet med den tilsvarende permutation opnå en Morse-Thue-sekvens. Så for eksempel kan tre cykliske permutationer laves fra tre tegn "1", "2", "3": "123", "231", "312":
en 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...
Multidimensionel generalisering
Den multidimensionelle Morse-Thue-sekvens er defineret på lignende måde. For eksempel er en todimensionel sekvens (matrix) grænsen for en sekvens, hvis næste medlem er opnået fra den forrige ved hjælp af transformationen
;
Den todimensionelle Morse-Thue-sekvens kan også repræsenteres som et sæt endimensionelle.
Links
- Weisstein, Eric W. Morse -Thue Sequence hos Wolfram MathWorld .