И оказывается, что как можно видеть, этот автомат в t-й раз окажется в состоянии qg в такт tc2, а за каждый шаг смещается ровно на 1 клетку. Т. е. перейдет в (x+ct) расстановку. Таким образом, видим, что построенный коллектив автоматов действительно вычисляет последовательность функций вида ft(x)=x+ct.

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

(доказательство данного результата содержится в дипломной работе Улугбека Айтбаева)

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

Рассмотрим движение автоматовА1(R, V), А2(R, V). По Теореме 2 оно будет периодичным. Обозначим предпериод их движения как Т_0, а период, как Т.  Рассмотрим состояния q(T_0+1),...,q(T_0+T), это состояния в которых оказывается автомат за период Т. Возможны два варианта:

    Если среди них состояние qgне встречается Если среди них состояние qg встречается ровно один раз
    Если среди них состояние qg встречается несколько раз

Разберем случай, когда у автомата W1 состояние qg не встречается за период. Так как автомат за период не переходит в состояние qgни разу, следовательно, исходя из определения вычислимости автоматом последовательности функций, коллективом автоматов не вычислиманикакая последовательность  функций.

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

НЕ нашли? Не то? Что вы ищете?

Пусть qg=q(T0+i), где i - от 1 до T. Обозначим за s1- перемещение, которое проходит автомат W1 за период T и s2- перемещение, которое проходит автомат W2 за период T.

s=s2-s1

,где s– число показывающее,  насколько вырастает перемещение за период T.

За х0– обозначим расстояние между автоматами в момент T0-последний момент пред периода.

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

В этом случае в состоянии qg автомат будет оказываться ровно 1 раз за период выходной последовательности. В первый раз - в момент T0+i, затем в T0+T+i, ... в t-й раз он окажется в состоянии qg в момент T0+t*T+i. Следовательно, за каждый период расстояние между автоматами будет меняться на s.

Рассмотрим момент T0. Так как мы определили х0как расстояние между двумя автоматами в момент T0, следовательно автоматы из х-расстановки перешли в х0расстановку.

х0=x+c1. c1- изменение расстояния между автоматами за T0- тактов.

Следовательно, в момент T0в состоянии qgвычислима функция вида f(x)=x+c1 по теореме 1. Автоматы  двигаются периодично и за каждый период расстояние меняется на s клеток.  Значит автомат W1из x+c1–расстановки в х+с1+s –расстановку за первый период. Логично, что с каждым периодом расстояние между автоматами будет увеличиваться на s клеток.

Следовательно каждый раз когда автомат будет переходить в состояние qgон будет переходить в х+с1+st-расстановку где t - число показывающее какой раз автомат проходит период Т.  А по определению «вычисления автоматом функции» следует что автомат вычисляет функцию вида  f(x)=x+с1+st. Таким образом видим, что коллективом автоматов вычислима последовательность функцийft(x)=x+с1+st=x+c1+c2t.

Разберем случай, когда у автомат W1 состояние qg встречается несколько раз.

Раз у автомата состояние qg встречается несколько раз - это означает, что в этом состоянии за один период автомат оказывается при разных входных символах, т. е. автоматы видятся за период. Допустим что автомат переходит повторно в состояние qgпри одинаковых входных символах.  Следовательно его предыдущее состояние будет состоянием что и перед предыдущем переходом в состояние qg, а следовательно существует некоторый период, а так как в периоде не может быть пред периода. =>автомат проходит период второй раз.

А раз они видятся за период, то по теореме 2 о периодичности следует, что s=0т. к. если s>0 или s<0, то автоматы будут все дальше удаляться друг от друга и через много периодов они больше никогда не увидятся. А тут они видятся постоянно, каждый период. Последовательность расстояний между ними в моменты qg - это повторение нескольких одинаковых чисел, т. е. расстояния меняются по циклу.

Раз s=0 отсюда следует, автоматы в начале следующего периода переходят в ту же расстановку что и в начале предыдущего периода,  попадая в окрестность, друг друга на разных расстояниях, обозначим эти расстояния как r1,...rk.

Следовательно, автоматы в периоде будут переходить в r1,...rk – расстановки. Так как расстояния между автоматами меняются по циклу следовательно в следующий момент когда автомат перейдет в состояниеqgон переместиться в r1-расстоновку. От сюда следует автомат будет вычислять функции f1(x)=r1, f2(x)=r2,…. fk(x)=rk,…  fk+1(x)=r1,…. Следовательно, данным коллективом будет вычислима бесконечная последовательность функций вида ft(x)=rj(константа), гдеr1,...rk это конечный набор константгде, t=jk+i (i - остаток от деления t на k, а j - целое частное)

9. Перечень используемой литературы

, , "Введение в теорию автоматов", Наука, 1985. "Об автоматной модели преследования", 2007.

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4