Software & Systems

В своей работе по теории создания самовоспроизводящихся автоматов фон Нейман задался вопросом конструктивной универсальности, то есть способности автомата, заданного надлежащим образом и имеющего все необходимое сырье для построения других автоматов, сконструировать любой другой автомат [Дж. фон Нейман]. Более того, фон Нейману в рамках клеточной модели удалось построить логическую модель такого автомата. Однако она носит весьма специфический характер вследствие выбора первичных элементов, поэтому оказалась малопригодной для решения практических задач.

Обозначим через A множество всевозможных автоматов. Каждый автомат строится из элементов четырех типов: рецепторов, тела автомата, соединительных элементов и эффекторов.

Рецепторы (входы) – элементы автомата, которые способны воспринимать сигналы из внешней среды или от эффекторов.

Множество рецепторов обозначим через I={i}.

Эффекторы (выходы) – элементы автомата, передающие сигнал, сгенерированный телом автомата, во внешнюю среду или рецепторам. Выходной сигнал является реакцией автомата на внешнее воздействие или на изменение своего внутреннего состояния. Множество эффекторов обозначим через O={o}.

Соединительные элементы – элементы автомата, реализующие каналы связи между парами элементов. Среди соединительных элементов выделим элементы двух типов – простые соединения и адаптеры. Простое соединение может соединять рецептор с телом автомата или тело автомата с эффектором и передает сигнал от входа к выходу без каких-либо изменений. Адаптеры – более сложные соединители, но их описание зададим при конструировании конструктивно-универсаль­ного автомата (КУА). Множество соединительных элементов обозначим через C={c}.

Тело автомата задается в виде f: X  Y, где X=[i, i, ..., i], iÎI, j= – вектор входных воздействий, поступающих от рецепторов; Y=[o, o ,..., o], oÎO, j= – вектор выходных воздействий автомата, воспроизводимых эффекторами. Отношение соответствия между рецептором и положением во входном векторе, а также между положением в выходном векторе и эффектором задается простым соединением. Тело автомата переходит в возбужденное состояние (генерирует реакцию), если каждый его рецептор находится в возбужденном состоянии (отметим, что среди всех сигналов будем выделять специальный null-сигнал, указывающий на отсутствие информации; рецепторы, способные фиксировать такой сигнал и переходить под его воздействием в возбужденное состояние, назовем сверхчувствительными рецепторами и обозначим как , ÎI).

Будем считать, что конструктивные элементы всегда имеются в требуемом количестве.

Каждому автомату сопоставим уникальный идентификатор id Î Id, где Id – множество идентификаторов. Тогда множество возможных автоматов задается пятеркой A={a½a=, CаÍС}.

Представим автомат в виде схемы:

Примечание: здесь и далее в схемах обозначения структурных элементов автомата зададим в виде:  – рецептор;  – эффектор;  – тело автомата; ¾¾¾ – простой соединитель.

В множестве А выделим подмножество A0 элементарных автоматов, то есть минимальных автоматов, из которых строятся сложные автоматы. Каждый автомат A0 состоит только из рецепторов, тела автомата, эффекторов и простых соединений. Например, элементарные автоматы для вычисления выражения [(a+b) * c] представляются в виде

Конструирование КУА начнем с создания подсистемы – реестра автоматов R, представляющего собой бесконечно расширяемый словарь автоматов, то есть RA. На множестве R определим две операции:

-    get, возвращающую из R автомат с id=idа, задаваемую в виде get: idа®a;

-    contains, проверяющую, содержится ли автомат с идентификатором idа в R, задаваемую в виде contains: idа ®true| false.

В начальном состоянии реестр R будет состоять из множества первичных элементов. По мере функционирования КУА в R будут включаться все сконструированные автоматы.

Функционирование КУА представим отображением Сu вида Сu: d(ас)ас, где ас – конструируемый автомат; d(ас) – описание автомата ас.

Для определения d(ас) введем понятие обособленного элемента.

Обособленный элемент a' – это композиция элементов из R, обладающая свойствами целостности (рассматривается и используется как элемент) и локальности (реализует законченную последовательность действий).

Следовательно, обособленный элемент a' является автоматом.

Каждый обособленный элемент a' – элемент множества A (a'ÎA), но, в отличие от ас, элемент a'ÏR. Описание обособленного элемента d(a') задается четверкой d(a')=, где Ida'={ida'} – множество идентификаторов элементов, из которых строится a'; Ia' – рецепторы автомата a'; Oa' – эффекторы автомата a'; Rela' – матрица смежности ориентированного графа, вершинами которого являются множество рецепторов и эффекторов a', а также множество рецепторов, эффекторов и идентификаторов всех элементов из a'.

Описание автомата aс задается пятеркой  где  – множество описаний обособленных элементов автомата aс;  – шаблон aс, задающий алгоритм работы автомата и определяющий места подстановки элементов a' в шаблон;  – рецепторы aс;  – эффекторы aс;  – операция подстановки {a'}, заданного описаниями   в вида

Среди всех описаний автоматов выделим вырожденное описание вида   или  где null – пусто (отсутствие), мощность множества  равна единице, а входы и выходы автомата  задаются входами и выходами единственного обособленного элемента a'.

Описание  которое обозначим как , задает простой автомат .

Будем говорить, что описание D(ac) допустимо Cu с реестром R, если каждое описание  допустимо. Описание d(a') допустимо, если для любого идентификатора из Ida' в реестре существует автомат с таким идентификатором и если a' локален; это означает, что, если возбудить все рецепторы автомата a', то хотя бы один эффектор перейдет в возбужденное состояние, то есть вершины Oa' графа G с матрицей смежности Rela' разрешимы относительно вершин Ia'.

Для проверки первого условия допустимости a' Cu последовательно проверяет все элементы множества Ida' с помощью операции contains на наличие требуемого автомата в реестре R.

Локальность конструируемого автомата проверяется по следующему алгоритму:

1) все вершины графа G, являющиеся входами автомата a', отметить маркером разрешимая, остальные – неразрешимая;

2) если каждая вершина графа G, являющаяся выходом автомата a', отмечена маркером разрешимая, то автомат a' локален и следует перейти к шагу 5;

3) последовательно просматриваем все неразрешимые вершины графа в поисках новых разрешимых вершин (неразрешимая вершина будет разрешимой, если все ее входы разрешимы);

4) если найдены новые разрешимые вершины, то отмечаем их маркером разрешимая и переходим к шагу 2, иначе граф G неразрешим и a', а следовательно, и ac нелокальны;

5) завершить алгоритм.

В качестве примера рассмотрим решение весьма тривиальной задачи: построить автомат, способный вычислять выражение (a+b)*c.

Описание автомата (a+b)*c:

=<{id+, id*},

 ,

{x1,x2,x3}, {out}>

Если описание D(ac) допустимо, то Cu приступает к построению автомата ac, которое заключается в последовательном построении всех обособленных элементов и включении их в шаблон с помощью операции . Отметим, что Cu не соединяет рецепторы и эффекторы конструируемого автомата ac с рецепторами и эффекторами обособленных элементов, так как правила их взаимодействия определяются операцией  и шаблоном .

Для построения обособленного элемента a' автомата ac Cu выполняет следующие действия:

-    с помощью операции get извлекает из реестра R все необходимые элементы для автома- та a';

-    по матрице Rela' соединяет рецепторы и эффекторы элементов a' между собой.

Построенный автомат a' с помощью операции  и шаблона  включается в автомат ac путем соединения рецепторов и эффекторов автомата a' с эффекторами и рецепторами автомата ac. Такие соединения будем выполнять с помощью адаптеров.

Адаптеры могут соединять рецепторы с рецепторами или рецепторы с эффекторами и в процессе передачи сигнала способны изменять его структуру. Алгоритм изменения сигналов Cu определяется на основе совместимости типов сигналов, которыми оперируют соединяемые адаптером элементы.

Предварительно сделаем аксиоматическое допущение, упрощающее процесс построения модели, от которого придется отказаться при решении практических задач: полагаем, что все передаваемые сигналы имеют одинаковую структуру и отличаются только своей мощностью. При этом роль адаптеров сводится лишь к передаче и согласованию входного и выходного сигналов.

Итак, после того как Сu осуществил все необходимые соединения, для созданного автомата ac генерируется уникальный идентификатор, и новый автомат регистрируется в реестре R (в случае простого автомата  регистрируется обособленный элемент a').

Пример. Схематичное изображение автомата (a+b)*c:

Примечание: здесь и далее на схемах адаптер обозначен как .

Покажем, как в рамках предложенной модели реализуются ветвления и циклы. Для этого рассмотрим две задачи:

1) построить автомат asf, реализующий кусочную функцию f(a)=;

2) построить автомат aff, вычисляющий a-фак­ториал (a!).

Для построения требуемых автоматов необходимо наличие в реестре элементарного умножающего автомата (a*ÎA0). Автоматы asf и aff в предлагаемой модели можно построить двумя способами: с использованием вырожденного описания либо при помощи шаблонов  и  соответственно. В первом случае к реестру необходимо добавить автоматы:  имеющий один вход a, два выхода l и r и работающий по правилу «если a0, то подать сигнал a на выход r, иначе на выход l»; , имеющий два входа ai и resi, три выхода ao, reso, out и работающий по алгоритму:

1)   если resi равен null, то на выход reso подать сигнал ai, иначе – сигнал resi;

2)   ai=ai-1;

3)   если ai меньше 2, то на выход out подать тот же сигнал, что и на выход reso, иначе на выход ao подать сигнал ai;

4)   конец.

Автоматы asf  и aff  будут иметь следующий вид:

В случае использования шаблонов h_sf и h_ff автоматы можно представить следующим образом.

Таким образом, если в реестре КУА находятся все необходимые компоненты, он сможет построить любой корректно заданный автомат.

Предложенная модель КУА, несмотря на принятые допущения, имеет законченный вид и может использоваться для автоматической генерации программных систем.

Литература

Дж. фон Нейман. Теория самовоспроизводящихся автоматов. М.: Мир, 1971. 382 с.