Авторитетность издания
Добавить в закладки
Следующий номер на сайте
Модель конструктивно-универсального автомата
Аннотация:Рассмотрена модель конструктивно-универсального автомата, определены базовые элементы, из которых конструктивно-универсальный автомат может сконструировать любой другой автомат, предложен способ спецификации процедуры сборки автомата.
Abstract:The model of constructive universal automatic machine is taken into consideration, its basic elements which help to build any other automatic machine are determined, and a way of specification of automatic machine‘s assembling procedure is suggested.
Авторы: Дрождин В.В. (drozhdin@yandex.ru) - Пензенский государственный педагогический университет им. В.Г. Белинского, г. Пенза, Россия, кандидат технических наук, Жуков М.В. (drozhdin@spu-penza.ru) - Пензенский государственный педагогический университет им. В.Г. Белинского | |
Ключевые слова: конструирование автомата, описание автомата, конструктивно-универсальный автомат, универсальный автомат, клеточный автомат |
|
Keywords: building of automatic machines, the description of automatic machines, constructive-universal automatic machine, universal automatic machine, cellular automatic machine |
|
Всего комментариев: 1 Количество просмотров: 9962 |
Версия для печати Выпуск в формате PDF (4.85Мб) |
В своей работе по теории создания самовоспроизводящихся автоматов фон Нейман задался вопросом конструктивной универсальности, то есть способности автомата, заданного надлежащим образом и имеющего все необходимое сырье для построения других автоматов, сконструировать любой другой автомат [Дж. фон Нейман]. Более того, фон Нейману в рамках клеточной модели удалось построить логическую модель такого автомата. Однако она носит весьма специфический характер вследствие выбора первичных элементов, поэтому оказалась малопригодной для решения практических задач. Обозначим через A множество всевозможных автоматов. Каждый автомат строится из элементов четырех типов: рецепторов, тела автомата, соединительных элементов и эффекторов. Рецепторы (входы) – элементы автомата, которые способны воспринимать сигналы из внешней среды или от эффекторов. Множество рецепторов обозначим через I={i}. Эффекторы (выходы) – элементы автомата, передающие сигнал, сгенерированный телом автомата, во внешнюю среду или рецепторам. Выходной сигнал является реакцией автомата на внешнее воздействие или на изменение своего внутреннего состояния. Множество эффекторов обозначим через O={o}. Соединительные элементы – элементы автомата, реализующие каналы связи между парами элементов. Среди соединительных элементов выделим элементы двух типов – простые соединения и адаптеры. Простое соединение может соединять рецептор с телом автомата или тело автомата с эффектором и передает сигнал от входа к выходу без каких-либо изменений. Адаптеры – более сложные соединители, но их описание зададим при конструировании конструктивно-универсального автомата (КУА). Множество соединительных элементов обозначим через C={c}. Тело автомата задается в виде f Будем считать, что конструктивные элементы всегда имеются в требуемом количестве. Каждому автомату сопоставим уникальный идентификатор id Î Id, где Id – множество идентификаторов. Тогда множество возможных автоматов задается пятеркой A={a½a=, CаÍС}. Представим автомат в виде схемы: Примечание: здесь и далее в схемах обозначения структурных элементов автомата зададим в виде: В множестве А выделим подмножество A0 элементарных автоматов, то есть минимальных автоматов, из которых строятся сложные автоматы. Каждый автомат A0 состоит только из рецепторов, тела автомата, эффекторов и простых соединений. Например, элементарные автоматы для вычисления выражения [(a+b) * c] представляются в виде Конструирование КУА начнем с создания подсистемы – реестра автоматов R, представляющего собой бесконечно расширяемый словарь автоматов, то есть R - get, возвращающую из R автомат с id=idа, задаваемую в виде get: idа®a; - contains, проверяющую, содержится ли автомат с идентификатором idа в R, задаваемую в виде contains: idа ®true| false. В начальном состоянии реестр R будет состоять из множества первичных элементов. По мере функционирования КУА в R будут включаться все сконструированные автоматы. Функционирование КУА представим отображением Сu вида Сu: 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с задается пятеркой Среди всех описаний автоматов выделим вырожденное описание вида Описание Будем говорить, что описание D(ac) допустимо Cu с реестром R, если каждое описание Для проверки первого условия допустимости 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:
{x1,x2,x3}, {out}> Если описание D(ac) допустимо, то Cu приступает к построению автомата ac, которое заключается в последовательном построении всех обособленных элементов и включении их в шаблон Для построения обособленного элемента a' автомата ac Cu выполняет следующие действия: - с помощью операции get извлекает из реестра R все необходимые элементы для автома- та a'; - по матрице Rela' соединяет рецепторы и эффекторы элементов a' между собой. Построенный автомат a' с помощью операции Адаптеры могут соединять рецепторы с рецепторами или рецепторы с эффекторами и в процессе передачи сигнала способны изменять его структуру. Алгоритм изменения сигналов Cu определяется на основе совместимости типов сигналов, которыми оперируют соединяемые адаптером элементы. Предварительно сделаем аксиоматическое допущение, упрощающее процесс построения модели, от которого придется отказаться при решении практических задач: полагаем, что все передаваемые сигналы имеют одинаковую структуру и отличаются только своей мощностью. При этом роль адаптеров сводится лишь к передаче и согласованию входного и выходного сигналов. Итак, после того как Сu осуществил все необходимые соединения, для созданного автомата ac генерируется уникальный идентификатор, и новый автомат регистрируется в реестре R (в случае простого автомата Пример. Схематичное изображение автомата (a+b)*c: Примечание: здесь и далее на схемах адаптер обозначен как Покажем, как в рамках предложенной модели реализуются ветвления и циклы. Для этого рассмотрим две задачи: 1) построить автомат asf, реализующий кусочную функцию f(a)= 2) построить автомат aff, вычисляющий a-факториал (a!). Для построения требуемых автоматов необходимо наличие в реестре элементарного умножающего автомата (a*ÎA0). Автоматы asf и aff в предлагаемой модели можно построить двумя способами: с использованием вырожденного описания либо при помощи шаблонов 1) если resi равен null, то на выход reso подать сигнал ai, иначе – сигнал resi; 2) ai=ai-1; 3) если ai меньше 2, то на выход out подать тот же сигнал, что и на выход reso, иначе на выход ao подать сигнал ai; 4) конец. Автоматы asf и aff будут иметь следующий вид:
В случае использования шаблонов hsf и hff автоматы можно представить следующим образом.
Таким образом, если в реестре КУА находятся все необходимые компоненты, он сможет построить любой корректно заданный автомат. Предложенная модель КУА, несмотря на принятые допущения, имеет законченный вид и может использоваться для автоматической генерации программных систем. Литература Дж. фон Нейман. Теория самовоспроизводящихся автоматов. М.: Мир, 1971. 382 с. |
Постоянный адрес статьи: http://swsys.ru/index.php?page=article&id=2391&lang= |
Версия для печати Выпуск в формате PDF (4.85Мб) |
Статья опубликована в выпуске журнала № 4 за 2009 год. | Версия для печати с комментариями |
Назад, к списку статей
Comments
автор: Роман [2009-12-27 20:37:23]Оценка пользователя: 10 баллов