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.

Sejarah

The Thue–Morse sequence was first studied by Eugène Prouhet in 1851, who applied it to number theory. However, Prouhet did not mention the sequence explicitly; this was left to Axel Thue in 1906, who used it to found the study of combinatorics on words. The sequence was only brought to worldwide attention with the work of Marston Morse in 1921, when he applied it to differential geometry. The sequence has been discovered independently many times, not always by professional research mathematicians; for example, Max Euwe, a chess grandmaster and mathematics teacher, discovered it in 1929 in an application to chess: by using its cube-free property (see above), he showed how to circumvent a rule aimed at preventing infinitely protracted games by declaring repetition of moves a draw.

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 Templat:OEIS
• Thue–Morse Sequence over (1,2) Templat:OEIS
• Odious numbers Templat:OEIS
• Evil numbers Templat: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.