Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v2(1-4)/dumov.pdf Дата изменения: Thu Sep 25 23:37:49 2008 Дата индексирования: Mon Oct 1 23:15:42 2012 Кодировка: Windows-1251

Пример простой универсальной линейной однородной структуры
А.С. Думов
Рассматриваются линейные однородные структуры, обладающие свойством универсальности, т.е. способные в определенном смысле моделировать любые линейные однородные структуры. Приводится конструктивное доказательство существования универсальной линейной однородной структуры с восемью состояниями ячейки.

1 Понятия и результат
Назовем линейной однородной структурой (ЛОС) [1], [2], четверку S = (Z, En , V , f ), где Z - множество одномерных векторов с целыми координатами, En = {0, 1, ..., n - 1} - отрезок расширенного натурального ряда, V = {0 , ..., h-1 } - конечный упорядоченный набор элементов Z, f - функция h переменных, f : (En )h En . Элементы множества Z называются ячейками ЛОС S . Элементы множества En называются состояниями ячеек. Набор V , называемый шаблоном соседства, определяет для каждой ячейки ЛОС S набор V () = ( + 0 , ..., + h-1 ), называемый окрестностью ячейки . Функция f называется локальной функцией переходов ЛОС S . Состоянием ЛОС S называем произвольную функцию g , определенную на множестве Z и принимающую значения из En . Если Z и g - состояние ЛОС S , то значение g () называем состоянием ячейки , определяемым состоянием g линейной однородной структуры S . На множестве всех состояний ЛОС S определим основную функцию переходов F линейной однородной структуры S , полагая F (g1 ) = g2 , если g1 , g2 и выполняется тождество g2 () = f (g1 ( + 0 ), ..., g1 ( + h-1 )). Назовем поведением ЛОС S последовательность ее состояний g0 , g1 , ..., для которых выполняется равенство gi+1 = F (gi ), i = 0, 1, ....


Состояние g0 интерпретируется как некоторое изначально задаваемое состояние. Состояние gi иногда интерпретируется как состояние ЛОС в момент времени i. Моделирование поведения одной ЛОС посредством поведения другой ЛОС определим следующим образом. Пусть S = (Z, En , V , f ), S = (Z, En , V , f ), l N. Обозначим через P множество всех таких ячеек ЛОС S , что ћ l < ћ l + l. Семейство множеств (блоков) P , Z, образует покрытие множества ячеек ЛОС S . Назовем состоянием блока P совокупность g (P ) состояний ячеек этого блока. Пусть взаимно однозначное отображение множества En состояний ячейки ЛОС S на подмножество M множества состояний блока ЛОС S . Сопоставим каждому состоянию g ЛОС S такое состояние g ЛОС S , что для каждой ячейки ЛОС S состояние g (P ) блока P равно (g ( )). Таким образом, состояние блока P ЛОС S изображает состояние ячейки ЛОС S . Обозначим это как g = (g ). Пусть G - подмножество множества всех состояний ЛОС S . Если существует такое N N, что для любого такого поведения g0 , g1 , ... ЛОС S , что g0 G , поведение g0 = (g0 ), g1 , ... ЛОС S удовлетворяет соотношению gN ћi = (gi ), i N, то говорим, что множество состояний G ЛОС S представимо в ЛОС S [с замедлением N ]. Если G = , то говорим, что ЛОС S представима в ЛОС S [с замедлением N ]. Если произвольная ЛОС S представима в некоторой ЛОС S , то назовем ЛОС S универсальной. Теорема. Существует универсальная линейная однородная структура с n = 8 состояниями ячейки и шаблоном соседства V = ((-1), (0), (1)).

2 Доказательство
Рассмотрим линейную однородную структуру S , множество состояний ячейки которой есть {0, , , , , , , } и шаблон соседства V = ((-1), (0), (1)). Состояния из множества {, , , , }, которые будут осуществлять движение влево и вправо, передаваясь от ячейки к ячейке, назовем сигналами. Определим локальную функцию переходов f этой ЛОС S в соответствии со следующими правилами, предполагая, что в случае возможности применения более чем одного правила, следует применять первое из возможных. Звездочки означают, что соответствующие переменные могут принимать произвольное значение. 1. f ( , , ) = ; 2. f (, , ) = ; 3. f (, , ) = ; 4. f ( , , ) = ; 5. f ( , , ) = ; 6. f ( , , ) = ; 7. f ( , , ) = ; 8. f (, , ) = ; 9. f (, , ) = ; 10. f (, , ) = ; 11. f ( , , ) = 0; 12. f (, , ) = ; 13. f (, , ) = ; 14. f (, , ) =; 15. 260


f (, , ) = ; 16. f ( , , ) = ; 17. f (, , ) =; 18. f (, , ) = ; 19. f (, , ) =; 20. f ( , , ) = ; 21. f (, , ) = ; 22. f (, , ) = ; 23. f ( , , ) = ; 24. f ( , , ) = ; 25. f (, , ) = ; 26. f (, , ) = ; 27. f (, , ) = 0; 28. f ( , , ) = ; 29. f (, , ) = ; 30. f ( , , ) = 0; 31. f (, , ) = 0; 32. f (, , ) = ; 33. f (, , ) = 0; 34. f ( , , ) =; 35. f (, , ) = ; 36. f (, , ) = ; 37. f (, , ) = 0. Обозначим через класс всех ЛОС S с n 2 состояниями ячейки, шаблоном соседства ((-1), (1)), локальные функции переходов f которых удовлетворяют следующим правилам: f (0, 0) = 0, f (x, y ) = 0 если x = 0 и y = 0, f (x, y ) = f (y , x). Будем говорить, что состояние g удовлетворяет условию четности, если g () = 0 = (i), i-нечетно. Лемма 1. Множество G состояний ЛОС S , удовлетворяющих условию четности, представимо в ЛОС S . Доказательство. Пусть ЛОС S имеет n состояний ячейки. Поставим в соответствие состоянию g ЛОС S состояние g ЛОС S следующим образом. Пусть , N. Обозначим через i совокупность таких ячеек = (i), что ( + ) ћ i i < ( + ) ћ i + , i Z. Множество ячеек, ограниченное слева ячейками из i и справа ячейками из i +1 , будем обозначать через i . Назовем такие множества ячеек соответственно блоками и -блоками. Положим равным 2n -2 и будем пока считать, что , и что - четно. Состоянию g ( ) произвольной ячейки = (i ) ЛОС S сопоставим совокупность состояний ячеек i - и i -блоков ЛОС S . Если состояние g ( ) = 0, то g () = 0 для всех ячеек i ЛОС S , если же g ( ) = x = 0, то g () = для ячейки = (( + ) ћ i + - 2x-1 ) (т.е. для ячейки номер 2x-1 , если считать от правого края блока i ), и g () = 0 для остальных ячеек i -блока. Состояния ячеек i -блока не зависит от состояния ячейки ЛОС S , а определяются локальной функцией переходов f моделируемой ЛОС S . Пусть = {, v , k1 , ..., km , + - w} - упорядоченное по возрастанию множество чисел, v , ki , i {1, ..., m}, w - четны, m N. Пусть g (( )) =, g ((v )) = , g ((ki )) =, i {1, ..., m}, g (w) =, и пусть g () = 0 для остальных ячеек блока 0 . Состояния ячеек остальных -блоков могут быть получены переносом 0 блока на ( + ) ћ i, i Z. Далее мы дадим описание функционирования ЛОС S , из которого станет ясно, как именно следует выбирать числа v , m, k1 , ..., km , w для представления множества G состояний данной структуры S . При этом мы ограничимся изложением основной идеи, оставляя в стороне некоторые технические детали. Пусть состояние g0 ЛОС S сопоставлено состоянию g0 ЛОС S указанным образом, причем для состояния g0 выполнено условие g0 ( ) = 0 = (i ), i - нечетно.
261


Согласно правилу 17, сигнал из g0 (( )) будет двигаться влево, и достигнет в момент времени t1 такой ячейки 1 , что gt1 (1 + (-1)) = , после чего gt1 +2 (1 + (-1)) станет равным согласно правилам 17, 20, 22, и затем появившийся сигнал согласно правилу 16 будет перемещаться вправо. Аналогично, сигнал из ячейки 2 ћ ( + - w) будет двигаться вправо и достигнет в момент времени t2 такой ячейки 2 3 , что gt2 (2 + (1)) = . К этому моменту времени состояние ячейки 2 + (2) есть (согласно правилу 23), затем gt2 +1 (2 + (1)) = по правилу 14 и сигнал из ячейки 2 + (2) начнет движение влево. В результате в момент времени t3 состояние ячейки 3 = ( ) станет равным , а в момент времени t4 состояние ячейки 4 = 2 ћ ( + ) - (1) станет равным . Согласно соответствию, введенному между состояниями ячеек ЛОС S и состояниями ячеек ЛОС S , t1 = 2x + 1, t2 = w + 3 + 2 - 2y , где x, y - состояния ячеек 1 = (1) и 2 = (3) ЛОС S . Можно подобрать w и v так, что для любых x и y встреча соответствующих сигналов и произойдет в ячейке 5 , = {(i)|2 + + v + 2 < i 4 + + v + 2}, и так, что в течение временного диапазона [t5 , t6 ], в котором может произойти эта встреча сигналов, в указанном множестве не будет никаких других сигналов. Тогда состояние этой ячейки 5 по правилу 10 станет равным , и этот сигнал останется неподвижен, согласно правилу 35, до появления сигнала в левой соседней ячейке. Заметим, что для различных с точностью до перестановки пар x и y соответствующий сигнал будет возникать в различных ячейках. Пусть в момент времени t7 > t6 сигнал , находившийся в момент времени t = 0 в ячейке (-w), окажется в ячейке (2 + + v - 1), чего можно добиться, подбирая и числа из . Затем он дойдет до ячейки 5 - (1), и сигнал переместится на одну ячейку влево согласно правилу 26. Если 5 - (1) = (2 + + v + 1), то, согласно правилам 18, 28, 29, 32, 34 в ячейках (2 + + v + 1), (2 + + v ), (2 + + v - 1) возникнет несколько сигналов, которые начнут перемещаться влево со скоростью 1 ячейка за 1 такт времени. Вследствие столкновения этой совокупности сигналов с сигналом (в момент времени t = 0 находившемся в ячейке (- + km )), согласно правилу 1, некоторая ячейка 6 перейдет в состояние . Число km , таким образом, следует выбирать так, чтобы эта ячейка 6 была равна ( + - 2f (x,y)-1 ), где f (x, y ) -локальная функция переходов ЛОС S , x = g ((0)), y = g ((3)). Если же 5 - (1) = (2 + + v + 1), то сигнал передвинется влево на одну ячейку при встрече с сигналом из {ki }-последовательности. Каждой паре (x, y ), x = g ((0)), y = g ((3)), соответствует (с точностью до перестановки) свой сигнал , находящийся в момент времени t = 0 в ячейке (- + kl ), после встречи с которым сигнал переродится в совокупность сигналов, начинающую 262


движение влево до столкновения с сигналом , находящемся в момент времени t = 0 в ячейке (- + kl-1 ). Варьируя разность kl - kl-1 , можно обеспечить всевозможные значения функции f на наборе (x, y ). Решая эту задачу для различных x, y , получаем моделирование различных функций. Замедление при таком представлении множества G состояний ЛОС S посредством ЛОС S составит 2 ћ ( + ). Лемма доказана. Пусть - класс всех ЛОС S с n 2 состояниями ячейки и шаблоном соседства V = ((-1), (0), (1)). Лемма 2. Произвольная ЛОС S представима некоторой ЛОС S , причем так, что для любого состояния g ЛОС S соответствующее ему состояние g ЛОС S удовлетворяет условию четности. Доказательство. Пусть моделируемая структура S имеет n состояний ячейки и локальную функцию переходов f (x, y , z ). Пусть состояние каждой ячейки моделирующей ЛОС S - либо 0, либо x вектор (A, t), где A {ћ, , , x, - , , x, y , - y , y }, x, y x- x, x,- {0, ..., n - 1}, t {0, ..., 5}. Локальную функцию переходов f (x, y ) ЛОС S , симметричную относительно своих аргументов, определим согласно следующим правилам. (Через x, y будем обозначать элементы множества {0, ..., n - 1}.) 1. f (0, 0) = 0. 2.1. f ((x, 0), (, 0)) = (- , 1), 2.2. f ((x, 0), ( x , 1), 2.3. f ((, 0), (, 0)) = (ћ, 1). 3.1. f ((- , 1), (ћ, 1)) = - , 0)) = ( x x - - - - (, 2), 3.2. f ((, 1), (ћ, 1)) = (, 2), 3.3. f ((, 1), (, 1)) = (ћ, 2). x x x x - - 4.1. f ((- , 2), (, 2)) = (x, y , 3), 4.2. f ((, 2), (ћ, 2)) = (, 3), 4.3. x y x , 2), (ћ, 2)) = (, 3). 5.1. f ((x, y , 3), (, 3)) = (y , 4), 5.2. - f (( x x,- f ((x, y , 3), (, 3)) = (- y , 4), 5.3. f ((, 3), (, 3)) = (ћ, 4). 6.1. x, - y , 4), (ћ, 4)) = (- y , 5), 6.2. f ((y , 4), (ћ, 4)) = (y , 5), 6.3. f ((x, x, x,- x,- f ((- y , 4), (y , 4) = (ћ, 5). 7.1. f ((- y , 5), (z , 5)) = (f (x, y , z ), 0), 7.2. x, x,- x, y ,- f ((- y , 5), (ћ, 5)) = (, 0), 7.3. f ((y , 5, (ћ, 5)) = (, 0). x, x,- Состояние g ЛОС S поставим в соответствие состоянию g ЛОС S следующим образом. Если g () = x, то g (6 ћ ) = (x, 0). Если = (i ), i - нечетно, то g ( ) = 0. Если = (2) + 6 ћ k , k Z, то g ( ) = (, 0). Если = (-2) + 6 ћ k , k Z, то g ( ) = (, 0). Следующая таблица иллюстрирует последовательность состояний ЛОС S с такой функцией переходов. Вторые компоненты векторовсостояний опущены. (Они равны нулю для всех ячеек в ненулевом состоянии в первой строке, единице - во второй, ..., пяти - в шестой строке и снова нулю - в седьмой.)

263




0 - x

x 0 ћ

0 - x 0

0 - x 0 y - x,-

0 ћ 0 x, y 0 ћ

0 - y 0 -y - x, 0

0 - y 0 0 -y - x, 0

y 0 ћ 0 ћ 0 f (x, y , z )

0 - y 0 0 z y- ,- 0

0 - y 0 z y- ,- 0

0 ћ 0 y, z 0 ћ

0 - z 0 -z - y,

0 - z 0

z 0 ћ

0 - z



Ячейка , находящаяся в момент времени t = 0 в состоянии (y , 0), оказывается в момент времени t = 6 в состоянии (f (x, y , z ), 6), (x, 0), (z , 0) - состояния в момент времени t = 0 ячеек, отстоящих от ячейки влево и вправо на 6 ячеек. Т.о. ЛОС S моделируется ЛОС S с задержкой 6. Лемма доказана. Из существования в классе универсальной ЛОС [2] и из лемм 1 и 2 вытекает универсальность структуры S .

Список литература
[1] В. Б. Кудрявцев, С.В. Алешин, А.С. Подколзин. Введение в теорию автоматов. - М.; Наука, 1985. [2] В.Б. Кудрявцев, А.С. Подколзин, А.А. Болотов. Основы теории однородных структур. - М.; Наука, 1990.

264