Выпускная квалификационная работа на тему «Поведение коллективов автоматов на целочисленной прямой» по направлению 010500 - «Прикладная математика и информатика» (стр. 6 )

и  будут теми же самыми, что и в момент времени . В момент времени - теми же самыми, что и в момент времени . Таким образом в момент времени расстановка и состояния автоматов и  будут теми же самыми, что и в момент времени . Следовательно в момент времени , где , расстановка и состояния автоматов и    будут теми же самыми, что и в момент времени . Этот факт можно записать следующей системой уравнений:

  , 

Из данной системы следует система уравнений:

где  ,  ,

которая означает, что последовательность выходных сигналов коллектива из двух автоматов на целочисленной прямой является периодической с периодом и предпериодом , в том случае, если автоматы и  находятся в зоне обзора друг друга бесконечное число раз. При этом, в данном случае максимальное количество тактов в предпериоде:

при ,

=.

Максимальное количество тактов в периоде:

Теорема доказана.

Теорема 2. Функции вида , где , вычислима коллективами из двух автоматов.

Доказательство.

Пусть дана функция . Построим коллектив , где 

,  который бы вычислял эту функцию. Для того, чтобы коллективу   перейти из их расстановки в   расстановку, достаточно лишь чтобы автомат передвинулся на клеток влево если либо на клеток вправо если , либо остался на месте если . Исходя из того, что  для вычисления данной функции автомату не обязательно «знать» где (слева или справа) находится автомат , то множества состояний автомата будет иметь следующий упрощенный вид: