Я собирался рассказывать о том, что узнал на конференции на прошлой неделе — но понял, что мне в качестве иллюстрации нужен рассказ, который интересн сам по себе. Итак:

Последовательность Морса-Туэ.

Давайте строить последовательность конечных слов w_n из 0 и 1 так:
*) w_0= 0
*) а каждое следующее получается приписыванием к предыдущему его «негатива» N(w_n): слова, получаемого из w_n заменой 0 на 1 и 1 на 0.
Тогда
w_0=0
w_1=01
w_2=0110
w_3=01101001
w_4=0110100110010110
и так далее.
Тогда, раз каждое следующее слово продолжает предыдущее, они все являются началами некоторого бесконечного слова w:

w = 01101001100101101001011001101001…

Определение. Это бесконечное слово w (бесконечная последовательность 0 и 1) называется последовательностью Морса-Туэ.

Эту последовательность можно определять и по-другому, с помощью замен. А именно: пусть T это отображение на множестве конечных слов, заменяющее каждый символ 0 на 01, а каждый 1 на 10. Например,
T(001)=010110.
Так вот — тогда нашу последовательность конечных слов можно получить, просто раз за разом применяя T:
T(w_n)=w_{n+1}.
И это ну совсем несложно увидеть по индукции. Действительно,
если
T(w_{n-1})=w_n,
то (поскольку T коммутирует со « взятием негатива » N(.) — заменой 0 на 1 и обратно)
T(N(w_{n-1})) = N(T(w_{n-1}))=N(w_n),
и потому
T(w_n) = T(w_{n-1} N(w_{n-1})) = w_n N(w_n) = w_{n+1}.
Вот и всё.

Соответственно, вся бесконечная последовательность Морса-Туэ w это то, что получается, если "применить замену T к w_0=0 бесконечное число раз".

(Собственно, подстановочные слова я в этом канале уже упоминал, вспоминая слово Фибоначчи, получающееся чередой замен A->AB, B->A, и разные красивые вещи, которые по соседству получаются; ну а тут правила чуть-чуть другие.)