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

По Табл.2 можно видеть, что за тактов передвинулся на клеток вправо, следовательно, коллектив перешел из - расстановки в -расстановку при

.

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

  А множеством состояний автомата будет множество:

Так как функции  переходов и выходов автомата будут иметь вид:   , , (где – любой  входной символ из ) и таким образом, автомат всегда будет находиться в состоянии покоя (вне зависимости от его входного символа), то мы не будем рассматривать функции  переходов и выходов автомата .

Пусть , тогда таблица функций переходов и выходов автомата будет иметь следующий вид:

. . .	. . .	. . .	. . .
. . .	. . .	. . .	. . .

табл.3

Из табл.3 видно, что Автомат находится в состоянии в момент времени . Начиная с этого момента, автомат начинает двигаться в сторону автомата по шагу за такт. Если , то автомат движется по шагу за такт - вправо, если же , то автомат   начиная в момент сдвигается на шаг влево и далее двигается по шагу за такт, до тех пор, пока не достигнет состояния . Также если , то - .

Случаи [ [ [рассматриваются аналогично.

Общая концепция такова, что за тактов автомат   передвигается на клеток, в сторону автомата что бы встать с ним в одну клетку, а затем в зависимости от того , или , соответственно передвигается на клеток влево, вправо, либо «остаётся на месте». Теорема доказана.

Список литературы

[1] , , "Введение в теорию

автоматов", Наука, 1985.

[2] "Об автоматной модели преследования", 2007.