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

при ,

=.

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

Рассмотрим случай в), когда автоматы и  находятся в зоне обзора друг друга бесконечное число раз.

В данном доказательстве расстановку , будем использовать как входной сигнал, но лишь тогда, когда автоматы и  будут находиться в зоне обзора друг друга, таким образом, будет выполняться следующее неравенство для множества расстановок

.

Так как автоматы и  находятся в зоне обзора друг друга бесконечное число раз, то для любого временного момента , найдётся такой временной момент , где , что расстояние между автоматами и  будет не больше чем .

Автоматы и  могут  находиться на расстоянии не большем не более чем в   состояниях – каждый, соответственно и  не более чем в разных расстановках.

Таким образом, существует не более чем вариантов расстановок при разных состояниях каждого из автоматов. Так как каждое из множеств имеет конечное число элементов, то и множество вариантов расстановок при разных состояниях каждого из автоматов, также будет иметь конечное число элементов.

Исходя из того, что вариантов расстановок при разных состояниях каждого из автоматов и    – конечное число, а  автоматы и  находятся в зоне обзора друг друга бесконечное число раз, следует, что при , не позднее чем через тактов, а при , не позднее чем через

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

 

А из определений функции перехода и функции входного сигнала конечного автомата известно, что зная входной сигнал и состояние автомата в любой момент времени , можно однозначно определить выходной сигнал в момент времени и состояние автомата в момент времени :

Из сказанного выше следует, что в момент времени расстановка и состояния автоматов