304
правки
Изменения
→Свойства и эквивалентные определения
Как видно из определения, символ на <tex>i</tex>-ой позиции не зависит от номера строки. Так как длина строк возрастает, каждая строка является собственным префиксом следующей, поэтому можно рассматривать получение следующей строки как приписывание к текущей некоторого суффикса.
{{Теорема
|statement=
Пусть <tex>\varphi(S)</tex> — строка, получающаяся из <tex>S \in \{0, 1\}^*</tex> заменой всех вхождений <tex>a</tex> на <tex>b</tex> и всех вхождений <tex>b</tex> на <tex>a</tex>. Для строк Туэ-Морса верно следующее соотношение: <tex>T_{n + 1} = T_n \varphi(T_n)</tex>
|proof=
Заметим, что соответсвующие индексы символов при приписывании суффикса к строке <tex>T_n</tex> получаются добавлением к индексам <tex>i = 0, 1, \dots, 2^n - 1</tex> числа <tex>2^n</tex>. Количество единиц в двоичной записи числа <tex>i + 2^n</tex> ровно на один больше, чем в двоичной записи числа <tex>i</tex>. Поэтому приписываемый суффикс есть ни что иное, как исходная строка с инвертированными символами.
}}
Данная теорема позволяет определять последовательность строк Туэ-Морса следующим образом: <tex>T_0 = a</tex>, <tex>T_{n + 1} = T_n \varphi(T_n)</tex>.
Часто рассматривают предельный случай — бесконечную строку Туэ-Морса. Бесконечную строку также можно задать с помощью правил ассоциативного исчисления, клеточного автомата, рекурсивных соотношений и так далее.
