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

назовем – конфигурацией. Каждая – конфигурация однозначно задает клетки зоны обзора, в которых находятся другие автоматы коллектива, а так же состояния этих автоматов.

Расположения в автоматов и их состояния однозначно задают все -конфигурации. Множество всех конфигураций при всевозможных расположениях  и состояниях автоматов является множеством Aj – входных символов автомата .

В данной работе будет рассматриваться поведение коллектива из двух автоматов (W1, W2) в .Для удобства будем считать, что у рассматриваемых коллективов .

Пусть автомат W1 имеет внутренний алфавит вида . Тогда будем говорить, что коллектив (W1, W2) находится в а-расстановке, если:W2 удален от W1 на а клеток вправо в случае, если , и на а клеток влево, в случае, если .

При , W1 находится в состоянии вида (1,q),  а при , W1 находится в состоянии вида (-1,q).

Состоянием покоя автомата A(R, V) назовём то состояние автомата, находясь в котором, при любом входном символе, выходной символ будет .

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

  где  ,  ,

где – предпериод, а – период.

5. Постановка задачи и основные результаты

Будем называть целочисленной функцией одноместную функцию f:Z→Z.

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

Будем говорить что коллектив (в данном случае автоматы ).вычисляет последовательность функций  если:

1) автомат Wn имеет выделенное состояние qg

2) когда коллектив W1,...Wn стартует из х-расстановки, то последовательность расстояний между Wn  и W1 с учетом знака в моменты t1,...tj... есть последовательность f1(x),... fj(x)…, где tj - это момент времени, в который автомат Wnв j-й раз оказался в выделенном состоянии qg.

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

Теорема 1. Существует коллектив из двух автоматов А1(R, V), А2(R, V), который вычисляет последовательность функций вида ft(x)=x+ct,

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

Теорема 3.Коллектив из двух автоматов А1(R, V), А2(R, V) на целочисленной прямой  вычисляет последовательность функций только вида  ft(x)=x+c1+c2t.

6. Изложение решений

Теорема 1. Существует коллектив из двух автоматов А1(R, V), А2(R, V), который вычисляет последовательность функций вида ft(x)=x+c1+c2t, где  c - некоторая задаваемая константа, t - номер функции из задаваемой последовательности функций.

Доказательство. Пусть дана последовательность функций видаf(x)=x+c1+c2t, построим коллектив из двух автоматов вычисляющий последовательность функций данного вида. Множеством состояний автомата будет множество: , где qg-состояние в котором автомат вычисляет функцию, n=c1+c2-1.  А множеством состояний автомата будет множество:

Функции переходов и выходов автомата (где — входной, — выходной, — внутренний алфавиты автомата ) не будут зависеть от входного символа , таким образом, имея вид: .  Автомат W2 неподвижен.