Turutan Thue–Morse

Dalam matematik dan kegunaannya, **turutan Thue–Morse**, atau **turutan Prouhet–Thue–Morse**, merupakan jujukan perduaan tertentu yang awalannya berselang (dalam bentuk tertentu).

Turutan Thue–Morse bermula:

0&thinsp;1&thinsp;10&thinsp;1001&thinsp;10010110&thinsp;1001011001101001....

Sebarang simbol pasangan teratur lain boleh digunakan selain 0 dan 1; struktur logik bagi turutan Thue–Morse tidak bergantung kepada simbol yang digunakan.

## Takrifan
Terdapat beberapa cara yang sama bagi mentakrifkan turutan Thue–Morse.

### Takrifan langsung
Bagi mengira unsur *n*th *t**n*, tulis nombor *n* dalam perduaan. Sekiranya number satu dalam tambahan binari ini adalah ganjil dengan itu *t**n*&nbsp;=&nbsp;1, adalah genap dengan itu *t**n*&nbsp;=&nbsp;0. Bagi sebab ini John H. Conway et al. menggelar nombor *n* memuaskan *t**n*&nbsp;=&nbsp;1 nombor ***od''ious''' dan nombor bagi mana ''t''<sub>''n''</sub>&nbsp;=&nbsp;0 nombor ***ev*il*'.

### Kaitan ulangan
Turutan Thue–Morse merupakan turutan t_n memuaskan t_0 = 0 dan

:t_{2n} = t_n
:t_{2n+1} = 1-t_n

bagi semua integer poitif *n*.

### Sistem-L
Turutan Thue–Morse merupakan output bagi sistem Lindenmayer berikut:
   **variable**  0  1
   **konstant**  tiada
   **mula**      0
   **peraturan**      (0 → 01), (1 → 10)

### Pencirian menggunakan penyingkiran bit
Turutan Thue–Morse dalam bentuk diberi di atas, sebagai turutan bit, boleh ditakrifkan melengkung menggunakan operasi penyingkiran bit ("bitwise negation").
Dengan itu, unsur pertama adalah 0.

Dengan itu sebaik sahaja 2 unsur *n* pertama telah ditetapkan, membentuk jujuran *s*, kemudian 2 unsur *n* berikutnya mesti membentuk penyingkir bitwise bagi *s*.
Dengan itu kita telah mengtakrifkan 2 unsur *n* +1 pertama, dan kita rekurse ("recurse").

Memperincikan beberapa langkan awal:
* Kita bermula dengan 0.
* Penyingkir bitwise bagi 0 adalah 1.
* Menggabungkan keduanya, 2 unsur pertama adalah 01.
* Penyingkir bitwise bagi 01 adalah 10.
* Menggabungkan keduanya, 4 unsur pertama adalah 0110.
* Penyingkir bitwise bagi 0110 adalah 1001.
* Menggabungkan keduanya, 8 unsur pertama adalah 01101001.
* Dan seterusnya.

Dengan itu
* *T*0 = 0.
* *T*1 = 01.
* *T*2 = 0110.
* *T*3 = 01101001.
* *T*4 = 0110100110010110.
* *T*5 = 01101001100101101001011001101001.
* *T*6 = 0110100110010110100101100110100110010110011010010110100110010110.
* Dan seterusnya.

### Penghasilan infiniti
Turutan ini juga boleh ditetapkan melalui:
:  \prod_{i=0}^{} (1 - x^{2^{i}}) = \sum_{j=0}^{\infty} (-1)^{t_j} x^{j} \mbox{,} \! 
di mana *t**j* merupakan unsur *j*th jika kita bermula pada *j* = 0.

## Sebahagian ciri

Kerana setiap blok baru dalam urutan Thue-Morse ditakrifkan dengan membentuk penafian bitwise permulaan, dan ini diulangi pada awal blok seterusnya, turutan Thue-Morse dipenuhi dengan kuasa dua: tali berturut-turut yang berulang. Iaitu, terdapat banyak contoh XX, di mana X adalah beberapa tali. Walau bagaimanapun, tiada kiub: contoh XXX. Terdapat juga tiada kuasa dua bertindih:.. Contoh 0X0X0 atau 1X1X1 [3] [4] yg menafsirkan adalah kritikal 2 [5]

Perhatikan bahawa T2n adalah palindrome untuk mana-mana n> 1. Seterusnya, membenarkan qn menjadi satu perkataan mendapatkan daripada T2n dengan mengira orang-orang yang antara sifar berturutan. Sebagai contoh, q1 = 2 dan q2 = 2102012 dan sebagainya. Tn perkataan tidak mengandungi bertindih segiempatsama kepentingan, perkataan qn adalah palindrome persegi perkataan bebas.
## Sejarah
Rentetan Thue-Morse mula dikaji oleh Eugène Prouhet pada tahun 1851, yang menerapkan kepada teori nombor. Walau bagaimanapun, Prouhet tidak menyebut urutan yang jelas; ini ditinggalkan kepada Axel Thue pada tahun 1906, yang menggunakannya untuk mendapati kajian Kombinatorik kata-kata. Urutan ini hanya dibawa ke perhatian di seluruh dunia dengan kerja Marston Morse pada tahun 1921, apabila beliau memohon kepada geometri kebezaan. Urutan ini telah ditemui secara bebas banyak kali, tidak selalu oleh ahli matematik penyelidikan profesional; sebagai contoh, Max Euwe, seorang guru Grandmaster catur dan matematik, mengetahuinya pada tahun 1929 dalam satu permohonan pada catur: dengan menggunakan harta kiub bebas (lihat di atas), beliau menunjukkan bagaimana untuk memintas peraturan yang bertujuan untuk mencegah permainan terhingga berlarutan dengan mengisytiharkan pengulangan bergerak seri.

## Pautan luar
*The Ubiquitous Prouhet-Thue-Morse Sequence. Allouche, J.-P.; Shallit, J. O.  Many applications and some history
*MathWorld: Thue-Morse Sequence.  Some other applications
*Thue–Morse Sequence 
*Thue–Morse Sequence over (1,2) 
*Odious numbers 
*Evil numbers 
*When Thue-Morse meets Koch A paper showing an astonishing similarity between the Thue–Morse Sequence and the Koch snowflake
*Reducing the influence of DC offset drift in analog IPs using the Thue-Morse Sequence A technical application of the Thue–Morse Sequence
*MusiNum - The Music in the Numbers Freeware to generate self similar music based on the Thue–Morse Sequence and related number sequences.