Приложение: "Линейные автоматы".


Давайте изобретем одномерный аналог игры "Жизнь". Зафиксируем "кодовое
слово" - некое семизначное число, каждая цифра которого равна 0, 1 или 2.
Пусть A_0 - его последняя цифра, A_1 - предпоследняя и т.д.


Теперь представим себе бесконечную горизонтальную полоску, разделенную
на клеточки.  В каждый момент времени клеточка может находиться в одном
из трех состояний (0,1,2). Состояние клеточки в момент  t+1  определяется
по ее состоянию и состоянию двух соседних с ней в момент t следующим
образом.

Числа, стоящие в данной клеточке и двух соседних, складываются.
хсли получилось число S, то в момент времени  t+1  состояние данное
клеточки будет равняться  A_S.

Всего кодовых слов 3^7, соответственно существует 3^7 вариантов игры,
иными словами, существует 3^7 линейных автоматов.

Пусть, например, кодовое слово равно 0102100. Давайте двойку изображать
знаком  ^ , единицу знаком - , а ноль пробелом. Пусть состояние
всей полоски в момент времени 0 такое:  -----^ ^
Тогда события будут развиваться следующим образом:

0           -----^ ^
1           -^^^ ^ --
2           ^-   -^--
3          -^^   ^  -
4          ^- - ---
5         -^^- --^-
6         ^--^--  ^
7        -^    - ---
8        ^^-    --^-
9       - -^    -  ^
10       -^^-     ---
11       ^--^     -^-
12      -^  ^-    ^ ^
13      ^^--^^   -- --
14     - -  - -  -----
15      -    -   -^^^-
16               ^- -^
17              -^^-^^-
18              ^-----^
19             -^ ^^^ ^-
20             ^^     ^^
21            -  -   -  -
22


Неформальная общая задача: найти кодовое слово, дающее самый интересный
линейный автомат. (Это и будет искомый аналог игры "Жизнь".)

Минимальное требования к "интересному" автомату:

(*) Существует планер, то есть финитная (состояние почти каждой клеточки 0)
конфигурация, переходящая через  несколько поколений в исходную, но с
ненулевым сдвигом.

Вот один из простейших примеров планера для автомата 0002100:
0     ^^- ---
1    -  ^--^-
2      -^   ^
3      ^^- ---

Примеры конкретных задач:
1) Найти все автоматы, удовлетворяющие требованию (*).
(Замечание: вряд ли это будет сделано полностью. Однако можно довольно
быстро показать, что люой интересный автомат имеет вид ...2100 или ....020)
2) Найти все автоматы, для которых существует планер с периодом 2.
(Здесь ответ известен, такой автомат всего один.)
3) Для автомата 0002100 описать явно все планеры периода 3.
4) Каково максимальное значение скорости планера?