Введение к работе
Актуальность темы. Однородные структуры представляют ібой вид управляющих систем, изучающих возможности ітематического моделирования различных реальных процессов, в >торых важно учитывать такие компоненты, как пространство, іемя, причинная связь, дискретность и др. К ним могут быть несены волновые и тепловые явления в физике, лзнедеятельность биологических организмов, информационный імен в электронных системах и т.п.
Однородные структуры возникают на пути обобщения )нятия конечного автомата за счет рассмотрения бесконечных іециально организованных сетей автоматов. Впервые эта модель .їла предложена Дж. фон Нейманом в несколько ином виде, и тем им же, Э.Муром, Т.Майхиллом, К.Эльготом и Д.Райтом в м виде, какой сейчас и рассматривается. С помощью такой вдели Дж. фон Нейман получил положительный ответ на вопрос воспроизведении одного объекта с помощью другого [алогичного объекта, т.е. получил математическую модель мовоспроизведения. Затем указанные авторы и другие следователи изучали разные, но, как правило, простые свойства ких структур. Большой вклад в создание контуров теории ;нородных структур осуществил А.С.Подколзин. Изложению :нов новой теории и ее развитию посвящена монография Б.Кудрявцева, А.С.Подколзина, А.А.Болотова "Основы теории [нородных структур".
предлагаемой работе на базе указанной монографии и ее хники решаются новые задачи теории однородных структур, язанные с явлениями устойчивого поведения таких структур и ожности его начального кодирования. Исследуются ізможности моделирования развития форм в однородных руктурах. В первом приближении можно выделить два типа ізвития: 1) рост форм с относительно несложными >верхностями (сюда можно отнести в биологии - рост органов, «ганизмов, сообществ, в химии - создание материалов, в технике строительство предприятий) и 2) рост графовых и древовидных руктур (органы управления, кровеносная и нервная системы, :фтепроводы, электрические цепи). В представленной работе іимание акцентируется на этих двух типах развития. Ставятся тросы сложности задания в однородных структурах той или
иной формы, определяется количество состояний ячейки, необходимое или достаточное для моделирования процессов роста. Рассматривается также "устойчивое" развитие форм - их способность к росту в агрессивной среде. Последнее может был содержательно проиллюстрировано ростом биологического организма в условиях влияния внешних неблагоприятных факторов, либо работой компьютера при условии возможных сбоев, происходящих в составляющих его элементах.
Помимо описанного моделирования, которое можно условно назвать "внешним" в силу того, что однородная структу моделирует некоторый реальный процесс, можно рассматривать моделирование "внутреннее", при котором однородная структур выступает в качестве модели другой однородной структуры. Возникающая при этом задача поиска универсальных однородні структур, т.е. таких структур, которые позволяют моделировать любую структуру соответствующего класса, имеет важное практическое значение в свете создания вычислительных устройств, способных моделировать любые процессы, моделирование которых принципиально возможно в однородны структурах. Возникает также вопрос нахождения по возможності простых, в смысле числа состояний и количества связей автомат универсальных однородных структур. Движение в направлении уменьшения количества связей естественным образом приводит некоторому расширению понятия однородной структуры. В данной работе вводится такое расширенное понятие - мозаичны однородные структуры, и приводится несколько универсальных мозаичных однородных структур, приближенных по своим параметрам к предельно простым структурам.
Цель работы. Основной целью работы является изучение "внешнего" и "внутреннего" моделирования в однородных структурах и оценка числа состояний автоматов и взаимосвязей между автоматами, требуемых для моделирования роста различи форм.
Научная новизна. Получены оценки числа состояний, необходимого и достаточного для моделирования выращивания плоской однородной структуре форм, приближающих выпуклые многоугольники и деревья, в том числе в условиях возможных внешних помех. В области универсальных однородных структур построены однородные структуры, превосходящие по своим
араметрам известные до этого. Кроме того, как расширение днородных структур, определены мозаичные однородные груктуры, и среди них найдены простые универсальные юзаичные однородные структуры. Исследован вопрос озможности проверки однородной структуры на существование в ей конфигураций, не изменяющихся во времени. Получена лгоритмическая разрешимость его для случая линейных и еразрешимость для случая плоских однородных структур.
Практическая ценность. Работа носит теоретический арактер. Результаты и методы работы могут быть применены в гории однородных структур, теории автоматов, теории »ункциональных систем.
Методика исследования. В работе использованы методы гории однородных структур, теории функциональных систем, гории алгоритмов.
Апробация работы. Результаты докладывались на :еждународной конференции "Интеллектуальные системы" в 992, на конференции "Дискретная математика" в 1995 г., а также ногократно на семинарах по теории автоматов на механико-атематическом факультете МГУ.
Публикации. Большая часть материалов, составляющих энную работу, может быть найдена в статьях автора, приводимых списке литературы.
Объем и структура работы. Работа изложена на 102 границах печатного текста и состоит из введения и трех глав, иблиография состоит из 17 наименований, из которых 2 - на ностранных языках.