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 1 10 1001 10010110 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 nth tn, tulis nombor n dalam perduaan. Sekiranya number satu dalam tambahan binari ini adalah ganjil dengan itu tn = 1, adalah genap dengan itu tn = 0. Bagi sebab ini John H. Conway et al. menggelar nombor n memuaskan tn = 1 nombor odious dan nombor bagi mana tn = 0 nombor evil.

 Kaitan ulangan 
Turutan Thue–Morse merupakan turutan  memuaskan  dan

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
 T0 = 0.
 T1 = 01.
 T2 = 0110.
 T3 = 01101001.
 T4 = 0110100110010110.
 T5 = 01101001100101101001011001101001.
 T6 = 0110100110010110100101100110100110010110011010010110100110010110.
 Dan seterusnya.

 Penghasilan infiniti 
Turutan ini juga boleh ditetapkan melalui:

di mana tj merupakan unsur jth 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.

Kategori:Jujukan integer
kategori:Titik tetap