Turutan Thue–Morse

Daripada Wikipedia, ensiklopedia bebas.
Lompat ke: pandu arah, cari
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[sunting | sunting sumber]

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

Takrifan langsung[sunting | sunting sumber]

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[sunting | sunting sumber]

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[sunting | sunting sumber]

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[sunting | sunting sumber]

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[sunting | sunting sumber]

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 tj merupakan unsur jth jika kita bermula pada j = 0.

Sebahagian ciri[sunting | sunting sumber]

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[sunting | sunting sumber]

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[sunting | sunting sumber]