Состояния единичных автоматов ОС можно ассоциировать с различными понятиями, такими как состояния биологических клеток, команды (инструкции) клеточных микропроцессоров, символы некоторых параллельных формальных систем и др. Тогда как сама история конфигураций в ОС ассоциируется с динамикой погружаемых в структуру различного рода дискретных моделей, процессов, алгоритмов и явлений. Подобные модели могут быть применены в таких различных областях как: распознавание образов, машинное самовоспроизведение, морфогенез, адаптивные и динамические системы, теория эволюции и развития, искусственный интеллект и робототехника, вычислительная техника и информатика, математика, кибернетика, синергетика, физика, космология и др. Мы можем интерпретировать ОС не только как абстракцию биологических клеточных систем, но также как теоретическую основу искусственных параллельных систем обработки информации и вычислений.
С логической точки зрения ОС являются бесконечными абстрактными автоматами со специфической внутренней структурой, определяющей целый ряд важных свойств и допускающей использование ее в качестве новой перспективной среды моделирования различных дискретных процессов, допускающих режим максимального распараллеливания. ТОС, в целом, может рассматриваться как структурная и динамическая теория бесконечных абстрактных автоматов, наделенных специфической внутренней организацией, носящей качественный характер. В настоящее время ТОС образует вполне самостоятельный раздел современной математической кибернетики со своими проблематикой, методами и приложениями, а сами структуры служат формальной средой для моделирования многих дискретных процессов и явлений в различных областях науки и техники. В нашей монографии [36] представлена архитектура ТОС и ее приложений с учетом достигнутых на тот момент результатов, а также основных тенденций развития данного направления исследований. Представленные материалы позволяют получить единую картину составляющих частей ТОС и ее приложений со всеми основными их взаимосвязями. На фоне предложенной архитектуры рельефнее вырисовывается и общая структура данного предмета исследований.
Наше дальнейщее изложение материала будет базироваться на так называемом классическом понятии 1-мерных (d=1) однородных структур (1-ОС), относительно которого здесь вводится ряд основных определений. Классическое понятие 1-ОС определяется как упорядоченная четверка компонент следующего вида:
1-ОС = <Z1, A, τ(n), X>
где A – конечное непустое множество, называемое алфавитом внутренних состояний единичных автоматов структуры и представляющее собой множество состояний, которые может принимать каждый элементарный (единичный) автомат структуры. Алфавит A содержит так называемое состояние покоя, обозначаемое символом “0”; суть этого особого состояния будет выяснена несколько позже. Не нарушая общности, в качестве A-алфавита будем использовать множество состояний A = {0, 1, 2, 3, ..., a-1}, содержащее a элементов – чисел от 0 до (a - 1).
Компонента Z1 представляет собой множество всех 1-мерных кортежей – целочисленных координат точек в евклидовом E1 пространстве, т. е. E1 представляет собой целочисленную решетку в E1, элементы которой служат для пространственной идентификации единичных автоматов структуры. Компонента E1 определяет однородное пространство структуры, в котором она функционирует. Естественно, что в целом ряде прикладных аспектов ОС их геометрия играет, порой, существенную роль, однако здесь данный вопрос не рассматривается.
В каждую точку пространства Z1 помещается копия конечного автомата Мура, алфавит внутренних состояний которого есть A. Как известно, автомат Мура представляет собой конечный автомат, выход которого в данный момент времени t зависит только от его внутреннего состояния в этот же момент времени t и не зависит от значения его входов. В этом случае каждая точка Z1 определяет имя или координату единичного автомата, помещенного в данную точку. Для удобства в дальнейшем будем идентифицировать точки пространства Z1 с расположенными в них единичными автоматами. Таким образом, термины “автомат z” и “автомат с координатой z ∈ Z1” будем полагать идентичными. Компонента X, называемая индексом соседства структуры, есть упорядоченный кортеж n элементов из Z1, который служит для определения автоматов-соседей любого единичного автомата структуры, т.е. тех ее автоматов, с которыми данный единичный автомат непосредственно связан информационными каналами.
Каждый единичный автомат структуры в любой дискретный момент времени t может получать информацию только от своих непосредственных соседей и передавать информацию о своем текущем состоянии также только им. Таким образом, непосредственными соседями единичного автомата z ∈ Z1 являются автоматы z+x1,z+x2 ,..., z+xn, где X={x1,x2, ..., xn}; xj ∈Z1 (j=1..n). Индекс соседства X описывает единый шаблон соседства
(геометрический образ соседей-автоматов) для каждого единичного z-автомата структуры. Он определяет позиции автоматов-соседей относительно каждого конкретного единичного z-автомата, который имеет с ними непосредственный информационный интерфейс. В дальнейшем, не нарушая общности, будем полагать, что X-индекс соседства содержит 01-элемент, определяющий центральный автомат шаблона соседства. Далее рассматриваются 1-ОС с индексами соседства X = {0, 1, ..., n-1}.
Первые три рассмотренные компоненты 1-ОС, а именно, A-алфавит состояний единичных автоматов, однородное пространство Z1 и X-индекс соседства образуют однородную среду, являющуюся статической частью ОС-модели. Данная часть описывает физическую организацию структуры и ее геометрию, но не специфицирует взаимодействия (динамики) среди составляющих ее единичных автоматов. Для определения функционирования 1-ОС необходимо иметь возможность описывать текущие состояния всех единичных автоматов структуры в любой дискретный момент времени t ≥ 0.
Состояние всей однородной среды называется конфигурацией (КФ) 1-ОС и представляет собой набор текущих состояний всех составляющих ее единичных автоматов. А именно, конфигурация 1-ОС есть любое отображение КФ: Z1 → A и C(A, 1) обозначает множество всех таких конфигураций относительно Z1 и A, т.е. C(A, 1) = {КФ|КФ: Z1 → A}. Множество C(A,1) включает и пассивную конфигурацию, содержащую автоматы только в состоянии покоя.
Функционирование 1-ОС осуществляется в дискретной шкале времени t=0,1,2,... и определяется локальной функцией перехода (ЛФП) σ(n), которая задает состояние каждого единичного z-автомата структуры в момент времени t на основе состояний всех соседних ему автоматов (согласно X-индекса соседства) в момент времени (t - 1). Иными словами, ЛФП есть любое отображение σ(n): An → A; в дальнейшем для ЛФП классических структур будем использовать следующие основные обозначения: a1a2 ... an → a1` – можество параллельных подстановок
где aj – состояния любого z-автомата 1-ОС и его соседей (согласно индекса соседства X = {x1, x2, ..., xn}) в момент времени (t - 1), а a1` – состояние этого z-автомата в следующий момент времени t > 0. Множество параллельных подстановок определяет программу (параллельный алгоритм) функционирования классической ОС-модели; параллельные подстановки представляют собой параллельный язык программирования низшего уровня в среде ОС-моделей. Мы будем рассматривать структуры, чьи ЛФП подчиняются определяющему соотношению σ(n): 0n → 0, т.е. структуры с ограничением на скорость передачи информации в них.
Одновременное применение ЛФП σ(n) к текущей конфигурации шаблона соседства каждого единичного z-автомата 1-ОС определяет глобальную функцию перехода (ГФП) τ(n) структуры, переводящую текущую КФ c ∈ C(A, 1) в следующую КФ c τ(n) ∈ C(A, 1) структуры. Именно для программной реализации глобальной функции перехода на основе заданной локальной функции и была создана процедура HS_1, представленная ниже.
| HS_1 := proc(Co::symbol, A::set(symbol), p::symbol, n::posint) local a b c d k f r, , , , , , ; global _LTF; if not belong(convert(Co, 'set1'), A) then error "1st argument should contain symbols from %1 only, but had received <%2>" , A, Co else f := proc(a p, ) local k j, ; for k to length(a) do if a k[ ] ≠ p then break end if end do; for j from length(a) by -1 to 1 do if a j[ ] ≠ p then break end if end do; |
| if k = 0 or j = 0 then p else a[k .. j] end if end proc end if; if member("" || ,p map(convert A, , 'string')) then assign(a = "", d = A, b = cat(p $ (k = 1 .. n))), assign(c = "" || b || Co || b); if not type(_LTF, 'table') then seq(assign(' 'd = [seq(seq(cat(k j, ), k = d), j = A)]), k = 1 .. n − 1), assign(r = rand 1 .. ( nops(A))); seq(assign(_LTF k[ ] = A[r( )]), k = d), assign('_LTF b[ ]' = p) end if; seq(assign('a' = cat(a, _LTF[`` || c[k .. k + n − 1]])), k = 1 .. length(c) − n), assign(' 'a = `` || ( (f a, "" || p))), a else error "3rd argument should belong to set %1 but had received <%2>", A p, end if end proc > HS_1(abcabcabcabcabc, {a,b,c}, c, 3); ⇒ baacaacaacaacaab > HS_1(cccccccccccccccccccccccccc, {a,b,c}, c, 3); ⇒ c > eval(_LTF); table([ccb = a, cba = c, aac = a, aca = c, ccc = c, bac = c, bca = c, cac = a, cca = b, abc = a, aab = b, bbc = a, bab = b, cbc = b, cab = a, acc = a, abb = a, aaa = a, bcc = b, bbb = c, baa = c, cbb = c, caa = a, acb = b, aba = c, bcb = a, bba = b]) > S:= abbabacbabccab: for k to 9 do assign('S' = HS_1(S, {a, b, c}, c, 3)), S end do; baabbccbcbabbaab accbaababacbabcbab baaaccbcbccbcbaacbab accaaaababbabaccabcbab baabaaabcbabbccabaaacbab accbccabaacbaabbaccaabcbab baaabbbaccabccbabcababaacbab accabacbcabaabacbacacbccabcbab baabaccbbcaccbccbcccabbbbaaacbab |
Предыдущий фрагмент представляет исходный текст процедуры и примеры ее применения для генерации конечных конфигураций из некоторой начальной конфигурации структуры 1-ОС. В качестве формальных аргументов процедуры HS_1(Co,A,p,n) выступают кратко рассмотренные выше такие элементы классических 1-ОС как начальная КФ (Со), алфавит внутренних состояний единичного автомата (А), состояние покоя (р) и размер связного шаблона соседюства структуры (n). Для генерации последовательностей конфигураций (историй развития начальных конфигураций) необходимо определить локальную функцию перехода (ЛФП), которая определяется стохастическим образом на основе rand-генератора псевдослучайных целых чисел. ЛФП определяется глобальной таблицей _LTF, чьи входы определяют все допустимые конфигурации шаблона соседства над А-алфавитом внутренних состояний, а выходы – соответствующие им состояния, получаемые центральным автоматом шаблона в следующий момент времени. Сгенерированная один раз таблица _LTF, сохраняется в течение всего текущего сеанса до ее переопределения, например, по restart-предложению. Ее текущее состояние можно получать по вызову функции eval(_LTF). Следует отметить, что для обеспечения отмеченного выше определяющего соотношения σ(n): 0n → 0, после генерации таблицы производится соответствующее переопределение одного ее входа (в приведенном выше фрагменте в таблице он выделен bold-шрифтом). Таким образом, задав начальную конфигурация на конечном отрезке единичных автоматов 1-ОС (Со), алфавит внутренних состояний А, состояние покоя р∈А и размер шаблона соседства (n), мы вызовом процедуры HS_1(Co, A, p, n) получаем следующую КФ структуры, т.е. конфигурацию в следующий момент времени. Применяя многократно вызов процедуры (как это показано фрагментом), получаем историю начальной КФ Со с течением времени под действием ГФП, определяемой заданной ЛФП. При этом, на Со, состоящей только из состояний покоя, вызов процедуры возвращает состояние покоя.