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

Филиал Московского государственного университета

имени в г. Ташкенте

Айтбаев Улугбек Батырович

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

на тему «Поведение коллективов автоматов на целочисленной прямой»

по направлению 010500 - «Прикладная математика и информатика»

рассмотрена и рекомендована к защите
Зав. кафедрой «МаТИС» д. ф.-м. н., профессор	Научный руководитель: м. н.с.
_________	______________
«___»____________2012 год	«___»_________2012 год

Ташкент 2012

Содержание

Введение Постановка задачи Основные результаты Список использованной литературы

Введение.

В настоящей работе исследуется поведения на целочисленной прямой коллективов из двух конечных автоматов. Доказывается, что последовательности состояний и выходных символов автоматов при таком движении – периодические.

Далее поведение коллектива из двух автоматов исследуются через  целочисленные функции, которые могут быть определенным образом вычислены такими коллективами. расстановкой коллектива автоматов (где ) называется такая расстановка автоматов, что автомат находится на a клеток правее в случае и на a клеток левее W1 в случае . Говорим, что коллектив автоматов вычисляет целочисленную функцию , если для любого целого х этот коллектив, стартуя из - расстановки остановится в -расстановке.

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

Автор выражает благодарность за научное руководство.

Основные определения и понятия.

Обозначим множества натуральных и целых чисел, как и , соответственно. Положим . Множество клеток, на которые плоскость разбивается целочисленной решеткой, обозначим . Определим подмножество   –  бесконечную в обе сторону ленту, разбитую на клетки:  (рис. 1).

(рис. 1).

Каждой клетке бесконечной в обе стороны ленты сопоставлена координата её нижнего левого угла. Отрезок из клеток, находящихся от клетки на расстоянии, не превосходящем  r, назовем r-окрестностью клетки

Будем считать, что задана нумерация клеток множества - слева направо, т. е. первая клетка отрезка – самая левая, последняя – самая правая.

Под автоматом будем понимать инициальный конечный автомат вида  , где A— входной, B — выходной, Q— внутренний алфавиты автомата W,  ц: Q Ч A → Q и ш: Q Ч A → B — функции переходов и выходов W, соответственно, ∈  Q — его начальное состояние. Алфавит A определяет возможности W “видеть” происходящее вокруг, а алфавит B — его возможности перемещаться. Алфавит Q и функции ц и ш задают внутреннюю логику автомата W.

  Рассмотрим автомат W, перемещающийся по . Выходным алфавитом  W является множество , где параметр V ∈ называется скоростью автомата W. Входной алфавит W зависит от параметра R ∈   (R ≥ V), называемого обзором автомата W и способа взаимодействия W с другими автоматами.

Автомат со скоростью V и обзором R будем обозначать как W (R, V).  Пусть  W (R, V) находится в клетке . Множество называется окрестностью хода W, а множество – зоной обзора W. Рассмотрим коллектив автоматов ,  где R — обзор, а V— скорость каждого из автоматов. Положим – размер зоны обзора каждого из автоматов.

Обозначим внутренний алфавит автомата как . Входным сигналом автомата будет строка вида