Системный анализ гетерогенных слабоструктурированных автоматов

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Системный анализ гетерогенных слабоструктурированных автоматов

С.М. Крылов

Самарский государственный технический университет

Рассматриваются определения и свойства гетерогенных автоматов, в которых входными, внутренними и выходными сигналами служат различные (гетерогенные) объекты, в т. ч. молекулы. Преобразования в таких автоматах напоминают химические реакции и потому названы преобразованиями «химического типа».

Ключевые слова: автоматы, гетерогенные свойства, общая формальная технология, химические реакции, «химический триггер», функциональности объектов.

System analysis of heterogeneous weakly-structured automata. Basic definitions and behavior

The paper deals with basic definitions and behavior of heterogeneous weakly-structured automata which use various heterogeneous objects like molecules of different chemical substances as input, internal and output signals. Some kinds of behavior of such automata are very close to the formal representations of chemical reactions, and therefore these automata are called heterogeneous ones with chemical-like transformations.

Keywords: automata, heterogeneous properties, General Formal Technology, chemical reactions, “chemical trigger”, object functionality.

В [1, 2, 3] рассмотрены электронные функциональные блоки (ФБ), которые вследствие различия свойств входных и выходных сигналов названы гетерогенными. Предложен формализм для представления как самих гетерогенных сигналов, так и ФБ для них [2, 3]. Цель настоящей статьи - расширить класс автоматов, названных гетерогенными, на функциональности так называемого «химического типа», что позволило бы рассматривать некоторые химические реакции в более простой логической интерпретации, чем это позволяет ?-исчисление Чёрча [4, 5] или теория «динамической» интерпретации некоторых гипотетических систем непрерывных химических реакций Г. Хакена в виде простейших логических схем, где, к примеру, бистабильный запоминающий элемент с двумя устойчивыми состояниями представляется двумя различными концентрациями реагентов [6].

Рассмотрим абстрактную химическую реакцию между двумя молекулами a и b, итогом которой является новая молекула c (пример взят из [7], с. 192):

a + b ® c. (1)

Как правило, молекулы a и b, так же как и молекула c, имеют различные физико-химические свойства, то есть отвечают условиям гетерогенности [1, 2].

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

a + b ® c («переключение» в состояние 0); (2)

c + d® a + e («переключение» в состояние 1).

По закону сохранения вещества молекула e должна содержать компоненты b и d (e=b*d, где * - символ соединения молекул b и d). Вещество e можно рассматривать как «выходной» сигнал «химического триггера», свидетельствующий о его переключении из состояния 0 (c) в состояние 1 (a), соответственно молекула b - это «входной» сигнал, переключающий «триггер» из состояния 1 (a) в 0 (c), а d - «входной» сигнал, переключающий триггер из 0 (c) в 1 (a). В электронике такой триггер принято называть RS-триггером.

К группам реакций типа (2) могут быть отнесены, например, реакции окисления двух- или трехвалентного железа кислородом и его восстановления водородом. Для двухвалентного железа эти реакции выглядят так:

Fe + O = FeO («переключение» в состояние 0);(3)

FeO + H₂ = Fe + H₂O («переключение» в состояние 1).

Согласно определению конечного автомата в [8, с. 298] им называется система S=<A, Q, V, d, l>, где A, Q, V - конечные множества (алфавиты) соответственно входных сигналов, сигналов состояния автомата и выходных сигналов, а d: QґA®Q и l: QґA®V - функции, определенные на этих множествах. Потребуем, чтобы в качестве элементов множеств A, Q, V использовались гетерогенные объекты, наделенные гетерогенными свойствами и некоторыми специфическими функциональностями, связанными с преобразованием этих свойств согласно определению функциональностей гетерогенных объектов [1, 2]. Введем определение.

Определение 1. Гетерогенным (неоднородным) автоматом называется система S=<A, Q, V, d, l>, где A, Q, V - конечные множества соответственно входных гетерогенных объектов, гетерогенных объектов, конкретные совокупности которых представляют (кодируют) состояния автомата, и выходных гетерогенных объектов, а d: QґA®Q и l: QґA®V - системы преобразований свойств гетерогенных объектов для переключения состояний автомата и состояний его выходных объектов, определенные на указанных множествах (в которых любой гетерогенный объект представлен конечной совокупностью своих конечных свойств и функциональностей).

В данном определении термины «системы преобразований» трактуются максимально широко. В общем случае это могут быть любые алгоритмы, реализуемые для соответствующих пар объектов множеств Q и A. Конкретные примеры систем преобразований свойств гетерогенных объектов рассмотрены ниже.

Как и любой классический автомат, гетерогенный автомат можно задать с помощью набора таблиц преобразований свойств гетерогенных объектов, соответствующих таблицам переходов и выходным сигналам-объектам, или с помощью ориентированного мультиграфа. Следует, однако, обратить внимание на то, как определяется состояние гетерогенного автомата, а именно - как совокупность всех объектов, относящихся ко множеству его состояний, со всеми присущими этим объектам конкретными значениями конкретных свойств. Т. е. число возможных состояний любого конечного гетерогенного автомата всегда конечно, поскольку не может выйти за рамки декартова произведения конечного числа состояний, приписываемых конечному числу объектов, даже если среди свойств объектов есть так называемые эмерджентные свойства и функциональности [2].

Определение 2. Гетерогенный автомат называется слабоструктурированным, если объекты, совокупность которых определяет его состояние, могут находиться в любом месте некоторого условно-ограниченного пространства, размеры которого соизмеримы с размерами взаимодействующих объектов (например реагирующих молекул) и через условную границу которого поступают входные объекты и удаляются выходные.

Понятие слабоструктурированности является одним из ключевых. Во-первых, оно сразу обращает внимание на кардинальное отличие такого рода автоматов от классических, имеющих, как правило, вполне четкие структурные описания. Во-вторых, отсутствие четкой структуры не позволяет говорить о фиксированных временных параметрах переключения таких автоматов. Тем не менее, как будет показано в дальнейшем, это обстоятельство не лишает такого рода автоматы свойства переключать свои состояния под воздействием внешних сигналов-объектов. Примером подобного слабоструктурированного автомата может служить некоторая область физического пространства живой клетки, в которой происходит конечная совокупность химических реакций, связанных с ее метаболизмом. При этом в данную область должны поступать исходные вещества и удаляться продукты реакций.

Другим примером может быть специально выделенный объект, используемый в объектно-ориентированном программировании (ООП), - так называемая «рамка» (frame), «окно» или «панель», в которую можно в любом месте вставлять (помещать) другие объекты. При этом конкретное положение таких объектов может быть неизвестно, а информационные связи между вставляемыми объектами могут иметь различную длину и создаваться различными способами - например, последовательно от объекта к объекту по мере вставки их в рамку. Такую нерегулярную связь между объектами удобно интерпретировать как некоторый «поток», «омывающий» все объекты и «доносящий» любой входной объект до любого объекта, вставленного в рамку. В примере с областью клетки «потоком», омывающим все объекты, относящиеся к автомату, может быть броуновское движение, переносящее «входные» объекты-молекулы к различным молекулам-переработчикам, образующим автомат.

Чтобы входные объекты точно попадали к местам своего назначения внутри автомата даже тогда, когда их конкретный маршрут непредсказуем, как и время достижения цели, удобно снабдить их уникальными именами, а компоненты автомата (объекты-переработчики) научить распознавать эти имена. Естественно, разные объекты должны получать разные имена, а одинаковые - одинаковые. Присваивание различным объектам уникальных имен назовем индивидуализацией.

Введение уникальных имен позволяет снять проблему синхронизации: пока объект-переработчик («оператор») не получит свой входной объект («операнд») с конкретным именем, он не может начать свою операцию и никаких изменений ни в совокупности объектов, представляющих состояние автомата, ни в выходных объектах происходить не должно. В случае же получения оператором своего операнда (которого он «узнает» по его уникальному «имени») соответствующая операция выполняется (с присущей ей естественной временной задержкой). Автоматы с такими свойствами принято называть самосинхронными [9].

Другое важное достоинство подобных автоматов - возможность параллельной работы всех его «внутренних» компонентов. Действительно, как только какой-либо из объектов-переработчиков освободился от своего объекта-«операнда», он может тут же приступить к следующей операции. Однако для сохранения определенной аналогии с классическими автоматами предполагается, что пока гетерогенный автомат не закончил работу с очередным входным объектом, следующий входной объект на «вход» автомата не поступает.

На рис. 1 приведены условная схема и граф переходов гетерогенного слабоструктурированного самосинхронного автомата типа «RS-триггер», работа которого задана уравнениями типа (2). Из него следует, что множество А его входных объектов есть A={<b,g_b>,<d,g_d>}, где g_b и g_d - списки параметров соответственно объектов b и d [1, 2]. Множество состояний содержит тоже два объекта: Q={<a,g_a>, <с,g_c>}, а множество выходных объектов V={<e,g_e>}.

Для задания гетерогенного слабоструктурированного автомата графом переходов формулируются аналогичные [8, с. 296] условия корректности: 1) для любого входного объекта a_j имеется ребро, выходящее из состояния q_i, на котором написано a_j (условие полноты); 2) любой входной объект a_j встречается только на одном ребре, выходящем из состояния q_i (условие непротиворечивости). Представленный на рис. 1 автомат задан не полностью и не отвечает условию 1.

Определение 3. Гетерогенный автомат S называется частичным, если хотя бы одна из его двух систем преобразований - d или ? - не полностью определена (то есть задана не на всех элементах соответствующего декартова произведения).

Нетрудно видеть, что это определение очень близко к [8, с. 304].

Согласно только что введенному определению, автомат, представленный на рис. 1, является примером частичного гетерогенного автомата. Для его доопределения можно использовать классические методы, рассмотренные в [8], включая теорему Пола - Ангера.

Для гетерогенных автоматов можно определить аналог автоматного отображения, зафиксировав в автомате начальное состояние q_i и поставив в соответствие каждой входной последовательности объектов a=a_j1a_j2...a_jk (т. е. «входному слову») выходную последовательность w:

w = l(q_i, a_j1) l(q_i, a_j1, a_j2)... l(q_i, a_j1,... a_jk).

Достижимые состояния и сильно связный гетерогенный автомат определяются аналогично [8, с. 298].

Разумеется, есть и расхождения с классической теорией автоматов, некоторые из которых будут рассмотрены ниже и в последующих статьях (в дальнейшем все термины трактуются в соответствии с работами [1, 2], а символ ю используется как символ окончания доказательств).

В частности, весьма нестандартно выглядит ситуация с изоморфизмом гетерогенных автоматов. Если мы примем, например, классическое определение изоморфизма автоматов применительно к гетерогенным, то изоморфизма на уровне свойств и функциональностей объектов мы можем и не получить. Покажем это на примере с автоматом типа «химический RS-триггер» (рис. 1). Действительно, все объекты, участвующие в его функционировании, могут иметь и разные списки свойств, и разные значения числовых параметров, представляющих свойства в этих списках. Кроме того, в ходе взаимодействия («химической реакции») объектов между собой многие из этих параметров могут (и даже должны) изменяться. Такие свойства в [2] названы функциональными. Говорить об изоморфизме соответствующих процессов изменения различных параметров, представляющих различные свойства, можно, только если мы тщательно специфицируем все многообразие возможных функциональностей и параметров, их представляющих. Рассмотрим один из гипотетических вариантов.

Пусть в схеме рис. 1 среди свойств g_a объекта a имеется некоторое свойство g₁. Далее, пусть значение этого свойства, равное 1, обеспечивает «достаточно удаленное» взаимодействие его со свойством g₂=0 (g₂g_b) объекта b и пусть при этих значениях свойств объекты a и b притягиваются друг к другу. Под действием этого притяжения объекты сближаются. Предположим далее, что в момент соединения (касания) объектов свойство g₂ принимает значение 1 и объекты a и b фиксируются в таком состоянии (т. е. комбинация свойств g₁=1 и g₂=1 вызывает «сцепление» объектов). Будем полагать, что новое состояние синтезированного из a и b объекта c (c=a*b) состоит из двух свойств: g_c=<g₁, g₂>, причем согласно нашему построению g₁=1, g₂=1. Предположим, что такая комбинация свойств объекта c вызывает его взаимодействие со свойством g₃=0 (g₃g_d) объекта d, заключающееся в том, что объекты c и d также начинают притягиваться друг к другу. При контакте объектов c и d свойство g₃=0 объекта d получает значение 1, что способствует сцеплению объектов b и d, которое, в свою очередь, приводит уже к отталкиванию объекта a от объекта e=b*d (т. е. комбинация свойств g₁=1, g₂=1 и g₃=1 вызывает отталкивание объектов a и e). В результате образуется новый объект со свойством g_e=<g₂, g₃>, а объект a возвращается в исходное состояние, готовое к встрече с новым объектом b, как только тот поступит через условную границу автомата.

Таким образом, мы построили некую искусственную систему свойств и функциональностей, которая демонстрирует, как может происходить взаимодействие и изменение значений (состояний) свойств гетерогенных объектов, обеспечивающих их нужное поведение. Подобный прием достаточно широко используется в различных моделях изучения поведения сложных систем, например, в моделях клеточных автоматов фон-Неймана [10] или в моделях молекулярных автоматов [11]. Весьма подходящее название для него - «метод назначенных функциональностей» (МНФ).

Запись рассмотренных выше функциональностей в форме, принятой в [2], дает:

гетерогенный слабоструктурированный автомат

(g₁=1)^a + (g₂=0)^b ® (g₂=1)^c (притяжение и сцепление объектов a и b);

((g₁=1)&(g₂=1))^c + (g₃=0)^d ® (g₃=1)^c (притяжение объектов c и d, (4)

сцепление d c b, отталкивание a и e),

где верхние индексы означают принадлежность содержимого скобок соответствующим объектам, а символы ?_i, как обычно, обозначают i-тые свойства объектов.

Можно видоизменить характер переключения свойств объектов, например:

(g₁=0)^a + (g₂=0)^b ® (g₁=1)^c (притяжение и сцепление объектов a и b);

(g₁=1)^c + (g₃=0)^d ® (g₃=1)^c (притяжение объектов c и d, (5)

сцепление d и b, отталкивание a и e).

Для восстановления исходного состояния объекта a g₁=0 систему (5) необходимо дополнить строчкой (g₁=1)^a + (g₃=1)^b®(g₁=0)^a. Заметим также, что запись g_i=0 не означает отсутствия свойства g_i. Это может быть просто некоторое условное значение параметра, отображающего g_i на числовую ось.

Алгоритм переключения состояний объектов и их взаимодействий для варианта (4) приведен на рис. 2.

Из рисунка видно, что важную функцию в алгоритмах переключения состояний свойств объектов выполняет проверка их физической близости. Именно она фактически синхронизирует последовательность операций «переключения» свойств, обеспечивая самосинхронность автоматов. Контроль сближения можно выполнить с помощью проверки наличия какого-либо свойства одного из двух сближающихся объектов. Например, для (4) при сближении a и b достаточно дождаться появления в ближайшем пространстве различимого значения свойства (g₂=0) или (g₁=1). Проверку при этом можно записать как (g₂=0?) или (g₁=1?). Естественно, что проверку (g₁=1?) лучше выполнять в рамках объекта b, поскольку положительный результат проверки позволит сразу перейти к переключению свойства g₂ этого же объекта: g₂:=1. Чтобы указать, что именно объект b должен производить проверку, модифицируем запись проверки так: b(g_a=x?) (x - ожидаемое значение свойства g_a при сближении b и a).

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Нетрудно предложить и другие варианты переключения функциональностей, в которых участвуют свойства g₁, g₂, и g₃, обеспечивающие последовательность операций типа (4) или (5). Т. о., если мы вовлекаем в рассмотрение функционирования гетерогенного автомата функциональности, обеспечивающие его физическую реализацию, то очевидной становится множественность решений, дающая внешне изоморфное, но по сути различное его поведение, т.е. справедливо следующее утверждение.

Утверждение 1. Изоморфизм на уровне графов гетерогенных автоматов допускает их множественную неизоморфную реализацию на уровне функциональностей участвующих в работе автомата объектов.

Утверждение 1 оставляет возможным описание поведения автоматов на уровне их графов для нелогических функциональностей типа тех, которые использовались в (4), (5). Кроме того, вместе с введением индивидуальных имен объектов и, соответственно, свойства их индивидуальной различимости оно позволяет вводить в условные границы гетерогенного слабоструктурированного самосинхронного автомата с индивидуальными именами объектов столько функций (в том числе, если нужно, логических), сколько может вместить в себя его физическое внутреннее пространство. Для этого нам необходимо доказать, что функциональности (1) и (2) образуют, с точки зрения булевых функций, функционально полную систему. Сделать это можно по-разному. Но сначала сформулируем следующее утверждение.

Утверждение 2. Система функциональностей «химического типа» (1), (2) образует функционально полный базис для реализации любых конечных булевых функций и, соответственно, для реализации алгоритмов любых конечных автоматов.

Развернутое доказательство этого утверждения будет приведено во второй части статьи «Системный анализ гетерогенных слабоструктурированных автоматов.

II. Переход от преобразований "химического типа" к логическим схемам и обратно».

Заключение. В статье исследованы некоторые свойства систем, которые, с одной стороны, могут рассматриваться как новая разновидность абстрактных автоматов, а именно - как слабоструктурированные гетерогенные самосинхронные автоматы с индивидуальными именами объектов операций; с другой - имеют много общего с типичными абстрактными описаниями различных схем химических реакций, процессов обработки разнородных данных в ООП и информации различного типа в современных программируемых аналого-цифровых (гетерогенных) «системах на кристалле». Наличие общности в абстрактном представлении подобных разнородных систем дает надежду на построение единой теории обработки и преобразования различных гетерогенных объектов (в т. ч. молекул, а также информации различного типа) на основе теории автоматов. Предлагаемый подход может оказаться более простым и понятным, чем некоторые существующие. Показано также, что подобные автоматы могут быть представлены в виде графов, блок-схем алгоритмов и различных формальных систем записей.

Библиографический список

1. Крылов С.М. Формально-технологические модели в общей теории систем // Известия Самарского научного центра РАН. - Т. 5. - №1. - 2003. - С. 83-90.

2. Крылов С.М. Формальная технология и эволюция. - М.: Машиностроение-1, 2006. - 384 с.

3. Крылов С.М., Сараев М.В. Синтез конфигурируемых блоков для аналого-цифровых систем на кристалле с использованием гетерогенных функциональных компонентов // Вестник Самарск. гос. техн. ун-та. Сер. Технические науки. - № 2 (20). - 2007. - С. 58-63.

4. Fontana W. Algorithmic Chemistry. In: Artificial Life II: Proceedings of the 2nd ALife Workshop, C.G. Langton et al. (eds.), Addison Wesley, Reading, MA, 1991, p. 159.

5. Fontana W., Buss L.W. The barrier of objects: From dynamical systems to bounded organizations. In: Boundaries and Barriers, J. Casti and A. Karlqvist (eds.), Addison-Wesley, 1996, pp. 56-116.

6. Хакен Г. Синергетика. - М.: Мир, 1980. - 408 с.

7. Общая химия / Под ред. Е.М. Соколовской, Г.Д. Вовченко, Л.С. Гузея. - М.: МГУ, 1980. - 726 с.

8. Адельсон-Вельский Г.М., Кузнецов О.П. Дискретная математика для инженера. - 2-е изд. - М.: Энергоатомиздат, 1988. - 480 с.

9. Josephs M.B., Udding J.T. An algebra for delay-insensitive circuits. Technical Report WUCS89-54. - St Louis, USA: Washington University, 1989.

10. Фон-Нейман Дж. Теория самовоспроизводящихся автоматов / Пер. с англ. - М.: Мир, 1971. - 284 с.

11. Крылов С.М. Модели молекулярных автоматов и различные типы функциональностей, необходимые для их реализации // Вестник Самарск. гос. техн. ун-та. - 2004. - Вып. 20. - С. 10-16.

Размещено на Allbest.ru