Не будет преувеличением сказать, что эта последовательность нулей и единиц столь же “всепроникающая и вездесуща” [6], как число p . Ещё в 1906 году норвежский математик Аксель Туэ привёл эту последовательность в качестве примера апериодической рекурсивно вычисляемой строки символов, а американский математик Марстон обнаружил ту же последовательность при изучении некоторых нелинейных систем методом символической динамики в 1921 году.
Построение последовательности Морса — Туэ начинается с нуля. На каждом следующем шаге к набору нулей и единиц, уже имеющемуся на предыдущем шаге, справа приписывается его дополнение— набор знаков, в котором каждый нуль заменеён единицей, а каждая единица заменена нулём
1-й шаг 0
2-й шаг 01
3-й шаг 0110
4-й шаг 01101001
5-й шаг 0110100110010110
6-й шаг 01101001100101101001011001101001
В сущности последовательность Морса — Туэ получается из простого правила замены символов
0 ® 01, 1 ® 10.
Последовательность Морса — Туэ обладает свойством самоподобия: содержит фрагменты, которые при надлежащем “растяжении” воспроизводят всю последовательность.
В качестве примера можно рассмотреть 6 шаг построения последовательности. Начав с первого члена, выберем каждый второй член последовательности (они выделены). Нетрудно заметить, что выбранные члены образуют последовательность Морса — Туэ.
0110100110010110.
Выбирая таким же способом члены из “новой” последовательности Морс — Туэ получим снова последовательность Морса — Туэ, что соответствует тому, что происходила выборка каждого четвёртого члена, начиная с первого последовательности. Вообще говоря, выбирая каждый 2n член последовательности, начиная с первого, снова получится последовательность Морса — Туэ.
Последовательность Морса — Туэ можно получить не только из правила “скопировать и приписать дополнение”, но и следующим образом. Рассмотрим все неотрицательные числа.
|
Десятичные числа |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
Двоичные числа |
0 |
1 |
10 |
11 |
100 |
101 |
110 |
111 |
|
Сумма двоичных чисел |
0 |
1 |
1 |
2 |
1 |
2 |
2 |
3 |
|
Цифровой корень по модулю 2 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
Запишем в двоичной системе и заменим каждое двоичное число остатком от деления суммы его двоичных цифр на 2. Цифровые корни по модулю 2 образуют последовательность Морса — Туэ.