Secvența Morse-Thue

Secvența Morse-Thue este o secvență infinită de zerouri și unu ( biți ), propusă pentru prima dată în 1906 de matematicianul norvegian Axel Thue ca exemplu de șir de caractere aperiodic recursiv computabil.[ specificați ] . Există două variante ale secvenței, obținute una de la cealaltă prin inversare de biți:

10010110011010010110100110010110 … ( secvența OEIS A010059 ) - opțional 01101001100101101001011001101001… (secvența A010060 în OEIS ) - principal

Secvența Morse-Thue este cel mai simplu exemplu de fractal și este folosită în algoritmii de compresie a imaginilor fractale .

Definiții

O secvență poate fi definită în mai multe moduri echivalente diferite:

Efectuarea transformarii ; , luând pentru prima iterație : $0\rightarrow 01$ $1\rightarrow 10$ $unu$

unu zece 1 0 0 1 1 0 0 1 0 1 1 0

Începem de la 1. La fiecare pas, adunăm inversul acestui număr la număr. Inversarea se obține prin înlocuirea tuturor zerourilor cu unu și a celor cu zerouri. De exemplu, inversul numărului 1001 va fi numărul 0110. (Într-un alt mod, inversarea numărului poate fi descrisă astfel: acesta este un număr care completează ceea ce a fost deja scris la un număr format doar din unii; de exemplu, 1001+0110=1111 în sistemul numeric binar)

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

Să scriem numerele 0,1,2,3... într-un rând în sistemul binar și să numărăm numărul de cifre 1 din fiecare număr. (Obținem secvența A000120 în OEIS .) Apoi luăm restul acestui număr atunci când împărțim la 2.

în notație zecimală	în binar	Număr de unități	numarul de unitati mod 2
0	0	0	0
unu	01	unu	unu
2	zece	unu	unu
3	unsprezece	2	0
patru	100	unu	unu
5	101	2	0
6	110	2	0
7	111	3	unu

Istorie

Secvența a fost descoperită în 1851 de Prouhet ( fr. E. Prouhet ), care și-a găsit aplicarea în teoria numerelor, dar nu a descris proprietățile excepționale ale secvenței. Și abia în 1906, Axel Thue , în timp ce studia combinatoria, a redescoperit-o.

Publicarea lucrării lui Thue în Germania a trecut fără urmă, iar Marson Morse a redescoperit secvența în 1921, aplicând-o în geometria diferențială.

Secvența a fost descoperită independent de multe ori: de exemplu, marele maestru Max Euwe și-a descoperit aplicația în șah, arătând cum să joace la nesfârșit fără a încălca regulile unei remițe.

Proprietăți

Simetrii

Ca orice fractal , secvența Morse-Thue are un număr de simetrii. Deci secvența rămâne aceeași:

Când eliminați toate elementele în locuri egale:

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...

Când înlocuiți două părți din care puteți face un întreg, cu alte două personaje. Aceasta înseamnă că secvența nu poate fi arhivată folosind algoritmul Huffman , deoarece secvența care este „arhivă” va coincide cu secvența Morse-Thue în sine:

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

Alte proprietăți

Secvența nu conține niciodată trei părți consecutive identice (este imposibil de întâlnit „ AAA” , unde „ A” - secvențe de zerouri și unu);
Transformata Fourier discretă a secvenței are aceleași maxime la frecvențele ⅓ și ⅔;
Un număr a cărui reprezentare binară este succesiunea Morse-Thue se numește număr Prue-Thue-Morse:

\tau =\sum _{{i=0}}^{{\infty }}{\frac {t_{i}}{2^{{i+1}}}}=0,412454033640\ldots

(secvența A014571 în OEIS ),

unde sunt elementele secvenței Morse-Thue. Acest număr este transcendental (demonstrat de K. Mahler în 1929 ). $t_{i}$

Variații și generalizări

Generalizare la alfabet arbitrar

Având în vedere un alfabet arbitrar de n caractere , se pot compune exact n permutări ciclice diferite ale acestui alfabet. Apoi, înlocuind fiecare „litera” a alfabetului cu permutarea corespunzătoare, se poate obține o secvență Morse-Thue. Deci, de exemplu, trei permutări ciclice pot fi făcute din trei caractere „1”, „2”, „3”: „123”, „231”, „312”:

1\rightarrow 123

2\rightarrow 231

3\rightarrow 312

unu 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...

Generalizare multidimensională

Secvența multidimensională Morse-Thue este definită într-un mod similar. De exemplu, o secvență bidimensională (matrice) este limita unei secvențe, fiecare membru al cărei următor este obținut din cel precedent folosind transformarea

1\rightarrow {\begin{matrice}1&0\\0&1\end{matrice}}

;

0\rightarrow {\begin{matrice}0&1\\1&0\end{matrice}}

10010110\cdots

01101001\cdots

01101001\cdots

10010110\cdots

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

De asemenea, secvența bidimensională Morse-Thue poate fi reprezentată ca un set de unidimensionale.

Link -uri

Weisstein, Eric W. Morse -Thue Sequence la Wolfram MathWorld .