О росте конфигураций в однородных структурах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

п Г '

v ^

} 7 ^

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ г () ¡\ И КИБЕРНЕТИКИ

\ 1 «я

На правах рукописи УДК 519.713

Думов Алексей Сергеевич

О РОСТЕ КОНФИГУРАЦИЙ В ОДНОРОДНЫХ СТРУКТУРАХ

специальность 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1997

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета им. М.В.Ломонособ

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, академик АТН, профессор Кудрявцев В.Б.

доктор физико-математических-наук Подколзин А.С. кандидат физико-математических наук, доцент Болотов А.А.

Вычислительный центр Российской Академии Наук

Защита состоится " 2\ " _1997 г.

в Уу ч. мин. на заседании диссертационного совета Д.053.05.38 при Московском государственном университете им. М.ВЛомоносова по адресу: 119899, ГСП, Москва, Воробьевы горы, МГУ, факультет ВМиК, ауд. ¿Ьъ .

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан " 23 " _1997 г.

Ученый секретарь диссертационного совета профессор

Н.П.Трифонов

Общая характеристика работы.

Актуальность темы. Однородные структуры представляют 160Й вид управляющих систем, изучающих возможности тематического моделирования различных реальных процессов, в >торых важно учитывать такие компоненты, как пространство, юмя, причинная связь, дискретность и др. К ним могут быть несены волновые и тепловые явления в физике, изнедеятельность биологических организмов, информационный >мен в электронных системах и т.п.

Однородные структуры возникают на пути обобщения )нятия конечного автомата за счет рассмотрения бесконечных [ециально организованных сетей автоматов. Впервые эта модель ,ша предложена Дж. фон Нейманом в несколько ином виде, и тем им же, Э.Муром, Т.Майхиллом, К.Эльготом и Д.Райтом в >м виде, какой сейчас и рассматривается. С помощью такой вдели Дж. фон Нейман получил положительный ответ на вопрос воспроизведении одного объекта с помощью другого [алогичного объекта, т.е. получил математическую модель мовоспроизведения. Затем указанные авторы и другие ¡следователи изучали разные, но, как правило, простые свойства ких структур. Большой вклад в создание контуров теории (нородных структур осуществил А.С.Подколзин. Изложению :нов новой теории и ее развитию посвящена монография Б.Кудрявцева, А.С.Подколзина, А.А.Болотова "Основы теории (нородных структур".

предлагаемой работе на базе указанной монографии и ее хники решаются новые задачи теории однородных структур, язанные с явлениями устойчивого поведения таких структур и ожности его начального кодирования. Исследуются 13можности моделирования развития форм в однородных руктурах. В первом приближении можно выделить два типа □вития: 1) рост форм с относительно несложными >верхностями (сюда можно отнести в биологии - рост органов, »ганизмов, сообществ, в химии - создание материалов, в технике строительство предприятий) и 2) рост графовых и древовидных руктур (органы управления, кровеносная и нервная системы, ¡фтепроводы, электрические цепи). В представленной работе [имание акцентируется на этих двух типах развития. Ставятся тросы сложности задания в однородных структурах той или

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

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

Цель работы. Основной целью работы является изучение "внешнего" и "внутреннего" моделирования в однородных структурах и оценка числа состояний автоматов и взаимосвязей между автоматами, требуемых для моделирования роста различи форм.

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

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

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

Методика исследования. В работе использованы методы гории однородных структур, теории функциональных систем, гории алгоритмов.

Апробация работы. Результаты докладывались на :еждународной конференции "Интеллектуальные системы" в 992, на конференции "Дискретная математика" в 1995 г., а также ногократно на семинарах по теории автоматов на механико-атематическом факультете МГУ.

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

Объем и структура работы. Работа изложена на 102 границах печатного текста и состоит из введения и трех глав, иблиография состоит из 17 наименований, из которых 2 - на ностранных языках.

Содержание работы.

Во введении рассматривается краткая история вопроса и ается общая характеристика работы.

Первая глава посвящена моделированию роста выпуклых и ревовидных конфигураций в однородных структурах.

В §1.1 приведены необходимые понятия. Однородной пруктурой (ОС) .У назовем четверку £ = Е„, V, /), где & -множество ^-мерных векторов с целыми координатами, '„ = {0, 1, ..., /г-1}, У= (яо, я/1-1) - упорядоченный набор опарно различных векторов из /- функция /г переменных, /. Еп)Ь —> Е„, причем ДО, ..., 0) = 0. Элементы множества

называются ячейками ОС S; элементы множества Е„ - состояниям ячеек', набор V называется шаблоном соседства и определяет для каждой ячейки а ОС S набор V(a) = (а + ..., а + которы назовем окрестностью ячейки а; функция / называется локальной функцией переходов ОС S. Состоянием ОС S назовем произвольна функцию g, определенную на множестве и принимающую значения из Е„. Если а е tf и g - состояние ОС S, то значение g{a) называем состоянием ячейки а, определяемым состоянием g однородной структуры S. Диаметром D состояния g ОС S назове\ max р(а,Ь), где а = (аи ..., ак), Ъ = (¿ь ..., Ък) - ячейки ОС S, \

- метрика в р(a,b) = |а,- - Ь,\. Силуэтом состояния g ОС S назовем состояние g, получаемое из g переводом всех ячеек в ненулевом состоянии в состояние 1. Обозначим силуэт g состояния g через A(g). Границей состояния g назовем множество ячеек а, состояние g(a) которых отлично от нулевого, и которые имеют в своей окрестности V(a) хотя бы одну ячейку в нулевом состоянии. Периметром состояния g назовем мощность его границы. На множестве Г всех состояний ОС S определим основную функцию переходов F однородной структуры S, полагая F(g\) = g2, если gi, g2 е Г и выполняется тождество gi(a) =f{g\{a ab), + ah_!>).

Функционирование ОС S представляет собой последовательность ее состояний G = go> Яь •••> для которых выполняется равенство gi+\ = F(g,), i = 0, 1, ... . Состояние go интерпретируется как некоторое изначально задаваемое состояние. Состояние gt иногда интерпретируется как состояние ОС в момент времени /. Если g, и gj - два элемента последовательности состояний G, t = i—j, t > 0, то пишем gj = F'(g,), и говорим, что gj выращивается из за время t, а сам процесс называем выращиванием. Конфигурациями ОС S назовем такие ее состояния g, для которых равенство g(a) = 0 выполняется на множестве всех ячеек а, кроме, быть может, конечного их числа. Если неравенство g(a) ф 0 выполняется ровно для одной ячейки с то такие конфигурации будем называть одноячеечными, или инициальными. Под временем существования (или временем жизни) T(S, g) конфигурации g в ОС S будем понимать минимальное /, при котором в последовательности состояний go = g, gi = Figo), gl = F(g[), ... ОС ¿"возникает тождественно нулевое состояние gh

удем полагать время жизни конфигурации равным есконечности, если такого i не существует.

Далее, дадим ряд определений, отражающих некоторые астные случаи введенных выше объектов. Так, однородную груктуру S = (2^, Еп, V, f) назовем линейной однородной груктурой, если к = 1, и плоской однородной структурой, если к : 2. Шаблон соседства V будем называть естественным, если в его входят такие и только такие векторы а, что ||о|| < 1, где ||о|| -

лина вектора а, ||о|| = ^x¡+...+x2k . Естественный шаблон

оседства плоской однородной структуры будем называть шблоном соседства в форме креста. Обозначим через С класс всех лоских ОС с шаблоном в форме креста, и через С(п) - подкласс ласса С, состоящий из всех ОС с п состояниями ячейки.

В §1.2 доказывается теорема о времени существования онфигураций в ОС, на которую опирается ряд последующих горем. Число D назовем представимым однородной структурой S, ели время жизни некоторой одноячеечной конфигурации в этой 1С равно D. Число D назовем непрерывно представимым классом цнородных структур с фиксированными размерностью, оличеством состояний ячейки и шаблоном соседства, если для юбого d, d < D, существует ОС S из этого класса, которой редставимо это число d. Пусть Ку(п) - класс ОС с п состояниями чейки и шаблоном соседства V, причем V включает в себя :тественный шаблон соседства, т.е. {(О, 0), (-1, 0), (1, 0), (0, -), (0, 1)} с V. Мощность множества ^обозначим через \V\. Пусть, алее, Lm{х) - функция, обратная функции х*". Имеет место тедующая

еорема 1.2.1. Для непрерывного представления числа D классом 'у(п) однородных структур необходимо выполнение условия п > \у\(D) и достаточно выполнения условия п < L\y\ (D) + с.

В §1.3 вводится понятие плоской фигуры и доказывается юрема о сложности выращивания выпуклых и выпуклых отзольных фигур и теорема о сложности выращивания тгоритмически задаваемых фигур. Назовем плоской дискретной игурой, или просто фигурой, конечное подмножество множества 2 двухмерных векторов с целыми координатами. Назовем ломаной торядоченный набор (а\, ..., ат) таких попарно различных гкторов из 2й, что \a¡+\ — a¡ || = 1, 1 < i < т. Ломаную (а\, ..., ат)

назовем замкнутой, если для нее выполняется условие Ца^ — ат\\: 1. В случае к = 2 замкнутая ломаная (а\, ..., ат) вьщеляет из множества 2к подмножества и ¿2, соответственно внутреннее внешнее по отношению к ломаной. Множество Х= 2\ и а\ и ... и ат называем контурной фигурой, ограниченно! замкнутой ломаной, а саму ломаную - границей контурной фигуры X. Контурную фигуру X назовем невыпуклой, если существуют такие три вектора а = (а^, а2), Ь = (Ь\, ¿»2), с = (сь сг), а е X, Ъ е X, с е X, что точки (а\, а2), (¿>ь 62). (с1> сг) лежат на одной прямой, вертикальной либо горизонтальной, причем (С), с^) леж* между (а\, а{) и (¿ь ¿2)- В противном случае назовем контурную фигуру X выпуклой. Будем говорить, что конфигурация g и фигур; X эквивалентны, и обозначать это как g <=> X, если для любого вектора а выполняется либо условие (а е X) & = 1), либо (1

X) & = 0). Конфигурацию g назовем равной фигуре X, и обозначим это как Е = X, если g эквивалентна фигуре X*, полученной из фигуры X некоторым параллельным переносом. Назовем контурную выпуклую фигуру т-угольником, если ровно , ячеек конфигурации, соответствующей этой фигуре, имеют в своей окрестности двух соседей в нулевом состоянии.

Будем говорить, что фигура X представима однородной структурой »У, если существует такая последовательность состояний go, g^, ..., gm, ... этой ОС, где #о - инициальная конфигурация, что A(gm) = =...= X, где - силуэт

конфигурации g. (Заметим, что равенство между конфигурациям] А и В означает их повекторное равенство, а не существование параллельного переноса, который переводил бы А в В.) Величин} т будем называть временем представления фигуры X. Будем говорить, что класс Кх фигур представим классом однородных структур с фиксированными размерностью, количеством состояний ячейки и шаблоном соседства, если для любой фигурь X в Кх существует ОС .У е в которой эта фигура Л1 представима.

Обозначим через Ур класс всех выпуклых фигур периметр р, а через Ур т - класс всех выпуклых ш-утольников периметра р. обоих случаях предполагаем выполнение условия р > ро. Пусть

(р-т)И

Цх) - функция, обратная функции х" , и пусть Р(р,т) =

'еорема 1.3.1. Для представления класса W= Vp \W= Vpm] фигур лассом С(п) однородных структур, необходимо выполнение условия

> L(2P) — с [п > L(F(p,m)) — с] и достаточно выполнения условия < L(7P) + с [п < L(F(p,m)) + с]. При этом время представления

юбой фигуры X из W не превосходит величины с*-р.

Если отказаться от требования линейности времени ыращивания фигур, то можно сформулировать более общую еорему. Пусть Ку = Xj, ...} - произвольное упорядоченное четное множество фигур, и пусть существует алгоритм „г/, озоляющий однозначно определять фигуру X-t по ее номеру /. )бозначим через К^т) первые т элементов Кх-'еорема 1.3.2. Для представления множества Kj^m), т > то, лассом С{п) однородных структур, необходимо выполнение условия

> L(m) и достаточно выполнения условия п < L(m) + с.

В §1.4 рассматривается рост конфигураций в условиях озможных сбоев. Пусть g - произвольное состояние ОС S. »бозначим через g* состояние, получаемое из состояния g ереводом некоторых ячеек из ненулевого в нулевое состояние. !сли при этом хотя бы одна ячейка а ОС S в состоянии, отличном т нулевого, не поменяет своего состояния, то говорим, что остояние g* получено из состояния g простым сбоем и бозначаем это как g ~> g*.

Будем говорить, что фигура X устойчиво пред ставима ОС если она представима ОС S, т.е. существует такая оследовательность G = go, g\, ..., gm состояний этой ОС, g/+1 = \g,), i > 0, где go - одноячеечная конфигурация, что A(gm) = (Sm+i) = ••■ <=> Д и если для любой последовательности G* = go*, ..., gk*, ... состояний ОС S, gJ+l* = F(gj*), j > 0, где g0*: g,- ~> g0*, ' - произвольный элемент последовательности G, выполняется :ловие A{g^) = A(gk+\*) = ... <=> X. Содержательно это означает, го ОС S выращивает фигуру X независимо от того, произойдет ли ростой сбой. (Замена знака "=" из определения представимости а знак "о" говорит о том, что фигура X будет выращена в любом тучае в одном и том же месте плоскости.)

Назовем фигуру X, X с 27е, связной, если для любых двух гкторов а е X, Ь € X, существует такое множество векторов Ч, С/с), С/ 6 X, 1 < / < к, что а = сь Ь = ск, ||с/+1 - с,-1| = 1, 1 < / <

Теорема 1.4.1. Для устойчивого представления произвольной связног фигуры X однородной структурой Я е С необходимо и достаточно п = \Х | + 1 состояний ячейки, где \Х \ - мощность множества X.

Теоремы, аналогичные теореме 1.4.1, могут быть сформулированы и для классов фигур. Так, пусть /д ,о - класс плоских связных фигур, все векторы а = (ах, ау) которых удовлетворяют условиям 0 < ах < Д 0 < ау < Х>. Теорема 1.4.2. Для устойчивого представления класса фигур классом С(п) однородных структур необходимо и достаточно выполнение условия п = Б 2 + 1.

В §1.5 определяется понятие клеточного выращивания и приводятся теоремы о сложности клеточного выращивания древовидных и выпуклых конфигураций. Возьмем произвольные натуральные числа х, у и поставим в соответствие произвольному вектору (/,/) е Z2 множество Р^д = {(а, Ь) |х / < а < л>(/+1), у-у < < )>•(/+1)} векторов из Z2, представляющее собой дискретный прямоугольник со сторонами х и у. Несложно видеть, что совокупность всевозможных прямоугольников Р(,- у) образует разбиение множества Z2 на попарно непересекающиеся подмножества, которые мы будем иногда называть клетками. Пусть X - произвольная плоская дискретная фигура. Будем говорить, что состояние С клеточно тождественно фигуре X, и обозначать это как если для любого вектора уе 72

выполняется условие V е 1о ^асР > 0. Это условие

означает, что принадлежность вектора V фигуре X эквивалентна тому, что в прямоугольнике Ру найдется хотя бы одна ячейка в состоянии, отличном от нулевого. Прямоугольники (клетки) Рх, обладающие таким свойством, мы будем называть живыми. Пуст] далее, <7 - произвольное состояние ОС Я. Обозначим через С* состояние ОС б1, получаемое из состояния б1 переводом некоторь ячеек из ненулевого в нулевое состояние. Если при этом ни одна из ячеек какой-либо живой клетки не поменяет своего состоянш то говорим, что состояние С* получено из состояния С простым сбоем, и обозначаем это как С ~> (7*.

Будем говорить, что фигура X клеточно-представима однородной структурой »У, если существует такая последовательность ее состояний Со, ..., С^,..., где Со -инициальная конфигурация, что для всех номеров /, начиная с

^которого m, выполняется условие G, » X. Возьмем теперь роизвольный элемент Gy последовательности Gb, ..., Gm,... . Пусть Gj ~> G*, т.е. состояние G* получено из состояния G простым 5оем. Если для последовательности G*, F(G*), F2(G*), ..., где F -шовная функция переходов ОС S, выполняется начиная с жотрого номера т* условие Fm*(G*) » X, то говорим, что фигура устойчиво клеточно представима однородной структурой S. ласс Кх фигур называем [устойчиво] клеточно представимым iaccoM Ks 'однородных структур, если для любой фигуры X е Кх ' шествует ОС S е Ks, в которой эта фигура X представима.

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

азис индукции. Назовем фигуру Г={(0, 0)} бинарным деревом с щим ярусом.

ндуктивный переход. Пусть Т\ и Tj — бинарные деревья с р\ и

ярусами соответственно и пусть Р = 2max(p"p2)_1. Тогда 1зовем фигуру Т= Тх + (Р, 0) и Т2 + (0, Р) и и,<р (/, 0) и кр (fi>J) бинарным деревом с р = max(pb pi) + 1 ярусами, яожение множеств Т\ и Tj с векторами означает здесь их ютветствующие параллельные переносы.

Обозначим через В{р) класс всех бинарных деревьев с телом ярусов, не превосходящим р. Имеет место следующая ;орема 1.5.1. Для устойчивого клеточного представления класса [р) классом С(п) однородных структур, необходимо выполнение ■ловия п > L(\B(p)\) и достаточно выполнения условия < 4 • L{\B(p)\) + с. При этом размеры клетки будут составлять с' х , а время выращивания каждого дерева не будет превосходить •Dj, где Dj - диаметр дерева, с, с', с", с* - некоторые константы.

Сложность устойчивого клеточного представления класса игур F о Ул, введенного в предыдущем параграфе, может быть :арактеризована следующей теоремой.

юрема 1.5.2. Для устойчивого клеточного представления класса •) Уо фигур классом С(п) однородных структур, достаточно

толнения условия п < A* L{2° ) + с. При этом размеры клетки 'дут составлять с' х с", а время выращивания каждой фигуры не

будет превосходить c*-Df, где Dp - диаметр фигуры F, с, с', с", с* -некоторые константы.

Глава вторая посвящена исследованию универсальных мозаичных однородных структур.

В §2.1 приведены необходимые понятия. Плоской мозаичной однородной структурой, или просто мозаичной однородн структурой (МОС) S, назовем набор S = (Z, Е„, V,f), где Z -мозаика на плоскости, т.е. множество, состоящее из равных меж • собой непересекающихся равносторонних ш-угольников, в совокупности полностью покрывающих плоскость, причем устроенное таким образом, что каждая сторона каждого т-угольника является стороной еще одного /и-угольника (отметим, что мозаики существуют только для т = 3, 4, 6, и в зависимости от значения т будем иногда называть мозаичные однородные структуры треугольными, квадратными или шестиугольными соответственно), Еп = {0, 1, ..., п — 1} - отрезок расширенного натурального ряда, V= {oq, ..., а^} - конечный упорядоченный набор элементов Z, а,- * о,- при 1 < i <j <h, f - функция h переменных, /: (En)h -> En. Элементы множества Z называются ячейками МОС S. Элементы множества Еп называются состояниями ячеек. Набор V, называемый шаблоном соседства, определяет для каждой ячейки а МОС S набор V(a) следующим образом: в V(a) включаются те ячейки (/и-угольники), которые попадают в множество, получаемое таким параллельным переносом множества V, при котором элемент ац множества V оказывается совмещенным с а; или, если такого параллельного переноса не существует, что возможно при т = 3, то параллельным переносом множества V, повернутого на угол 180° Элемент а0 множества К назовем центральным элементом множества V, а полученный набор V(a) - окрестностью ячейки а. Отметим, что из неравенства 1 < / < J < h, использованного при определении шаблона соседства V, вытекает возможность повторного вхождения в набор, что означает принадлежность любой ячейки а своей окрестности.

Шаблон соседства будем называть естественным, если окрестность каждой ячейки составляет она сама и ячейки, имеющие с ней общую сторону. Шаблон соседства будем называ естественным проколотым, если окрестность каждой ячейки составляют только ячейки имеющие с ней общую сторону, но не

ама ячейка. Функция / называется локальной функцией переходов ЮС £

Состоянием МОС £ называем произвольную функцию g, пределенную на множестве Z и принимающую значения из Еп. !сли а е Zи g - состояние МОС Я, то значение д(а) называем остоянием ячейки а, определяемым состоянием g мозаичной днородной структуры Б. На множестве Г всех состояний МОС Б пределим основную функцию переходов Т7 мозаичной однородной груктуры Я, полагая Р(&\) = g2, если g\, g2 е Г и выполняется ождество g2(a) =/(£1 (а1), ..., g\(аА)), где а' - ячейка из шаблона оседства ячейки а, в которую переходит ячейка а1 при араллельном переносе, определяющем окрестность ячейки а. Акционирование МОС представляет собой последовательность г состояний go, g\, ..., для которых выполняется равенство gt^.\ = '(&/)> 1 = 0. 1, •••• Конфигурациями МОС »Убудем называть одмножества множества ячеек в состояниях, отличных от улевого.

Далее, перейдем к определению представимости |ункционирования одной мозаичной однородной структуры осредством функционирования другой. Сначала дадим пределение разбиения мозаики. Под разбиением мозаики из т-гольников будем понимать мозаику из /л-угольников меньшего азмера, удовлетворяющих следующим правилам: а) стороны т-гольников разбиения должны быть параллельны сторонам т-гольников исходной мозаики; б) множество вершин т-гольников разбиения должно включать множество вершин сходной мозаики. Отметим, что в случае с треугольными и вадратными мозаиками разбиение может быть получено роблением каждого треугольника (квадрата) на равные между эбой треугольники (квадраты) меньшего размера. К сожалению, с [естиугольными мозаиками этот прием не проходит, поскольку [естиугольник нельзя разбить на меньшие шестиугольники, [усть (Д Еп, V,/), Б' = Еп., V',/') - некоторые МОС, ричем мозаика Z/является разбиением мозаики Z. Сопоставим аждой ячейке а МОС »У множество (блок) Р{а) ячеек МОС Б', 1ких, что отождествляемые с ними /и-угольники либо полностью ринадлежат /и-угольнику, отождествляемому с ячейкой а, либо ересекаются правой или нижней сторонами этого т-угольника. торое условие имеет смысл только при т = 6. Термины

"правый" и "нижний" в этом случае могут трактоваться естественным образом в рамках произвольно выбранной системь координат, ось абсцисс которой параллельна некоторой стороне некоторого шестиугольника, составляющего мозаику. Таким образом, мы получаем разбиение множества ячеек ^У'на блоки с одинаковым количеством ячеек, совпадающие с точностью до параллельного переноса. Пусть IV - взаимно однозначное отображение множества Еп состояний ячейки а МОС £ на подмножество М множества состояний блока ячеек МОС Б' Р(а), одинаковое для всех ячеек МОС Б. (Под состоянием блока ячеек мы понимаем совокупность состояний всех ячеек блока.) Сопоставим произвольному состоянию А МОС такое состояние А' МОС Б', что для любой ячейки а МОС Б состояние блока ячеек Р(а) МОС Б' определяется как и'(а), и обозначим это как А = Я(Н). Если существует такое натуральное ./V, что для любого функционирования go, g^, ... МОС Б функционирование £'о = Л(§о), 8'и 8ъ - удовлетворяет соотношению = / = 1, 2, ..., то говорим, что МОС Б представима в МОС Б' с замедлением N. Если произвольная МОС »У представима в некоторой МОС Б', то МОС Б' называется универсальной.

В §2.2 приводятся примеры простых универсальных мозаичных однородных структур и устанавливаются следующие утверждения.

Теорема 2.1. Существует универсальная мозаичная однородная структура с треугольными ячейками, с тремя состояниями и естественным, шаблоном соседства.

Теорема 2.2. Существует универсальная мозаичная однородная структура с квадратными ячейками, с двумя, состояниями и естественным, шаблоном соседства.

Теорема 2.3. Существует универсальная мозаичная однородная структура с квадратными ячейками, с тремя состояниями и естественным, проколотьш шаблоном соседства. Теорема 2.4. Существует универсальная мозаичная однородная структура с щестиугольньши ячейками, с двумя, состояниями и естественньш шаблоном соседства.

Теорема 2.5. Существует универсальная мозаичная однородная структура с щестиугольньши ячейками, с тремя состояниями и естественньш проколотым шаблоном соседства.

В третьей главе рассматривается вопрос алгоритмической 1зрешимости существования устойчивых конфигураций амородков) в линейных и плоских однородных структурах, азовем состоянием-самородком такое состояние g, отличное от »ждественно нулевого, что F(g) = g. Аналогично, назовем тфигурацией-самородком такую конфигурацию g, отличную от »ждественно нулевой, что F(g) = g.

В §3.1 доказывается алгоритмическая разрешимость >проса существования самородков в линейных ОС. горема 3.1. Существует алгоритм Л, который для любой линейной С устанавливает, есть ли в ней (А) конфигурации-самородки, (В) стояния-самородки.

В §3.2 доказывается алгоритмическая неразрешимость >проса существования самородков в плоских ОС. зорема 3.2. Не существует алгоритма Л, который для любой юской ОС устанавливает, есть ли в ней (А) конфигурации-шородки, (В) состояния-самородки.

Автор выражает глубокую благодарность научному тсоводителю, акад. В.Б.Кудрявцеву, за постоянное внимание и шощь.

Думов А. С. О моделировании роста выпуклых и »евовидных конфигураций в однородных структурах. Дискретная тематика. Том 7, вып.2 - 1995. С. 61-79.

Думов А. С. О времени существования конфигураций в [нородных структурах. Фундаментальная и прикладная тематика. - В печати.

Думов А. С. О сложности выращивания конфигураций в дородных структурах. Фундаментальная и прикладная тематика. - В печати.

Думов А. С. О простых универсальных мозаичных дородных структурах. Дискретная математика. Том 8, вып.4 -96.

Думов А. С. О существовании устойчивых конфигураций в ;нородных структурах. Интеллектуальные системы. Том 1, вып.1-- 1996. С. 165-172.

список литературы.