Turutan Thue–Morse

Graf ini menunjukkan binaan berulang dan pelengkap kepada 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 n^th t_n, tulis nombor n dalam perduaan. Sekiranya number satu dalam tambahan binari ini adalah ganjil dengan itu t_n = 1, adalah genap dengan itu t_n = 0. Bagi sebab ini John H. Conway et al. menggelar nombor n memuaskan t_n = 1 nombor odious dan nombor bagi mana t_n = 0 nombor evil.

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 ⁿ pertama telah ditetapkan, membentuk jujuran s, kemudian 2 unsur ⁿ 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.
• T₁ = 01.
• T₂ = 0110.
• T₃ = 01101001.
• T₄ = 0110100110010110.
• T₅ = 01101001100101101001011001101001.
• T₆ = 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

Segi empat bersarang dihasilkan oleh turutan iterasi Thue–Morse.

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 (jujukan A010060 dalam OEIS)
• Thue–Morse Sequence over (1,2) (jujukan A001285 dalam OEIS)
• Odious numbers (jujukan A000069 dalam OEIS)
• Evil numbers (jujukan A001969 dalam OEIS)
• 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.