Монография по однородным структурам

Monograph on Cellular Automata

В.З. Аладьев, В.К. Бойко, Е.А. Ровба. Классические однородные структуры: Теория и приложения.– Гродно: Гродненский государственный университет, 2008, 486 c., ISBN 978-9985-9508-4-5, 978-985-551-020-7

Содержание

Список принятых сокращений

Предисловие

Введение

Глава 1. Базовая концепция однородных структур (ОС-моделей)

1.1. Основные понятия, определения и обозначения

1.2. Основные типы однородных структур

1.3. Архитектура теории однородных структур и ее приложений

1.4. Аппарат исследований в теории однородных структур

Глава 2. Проблема неконструируемости в классических однородных структурах

2.1. Предварительные сведения по проблематике

2.2. Типы неконструируемости в классических ОС-моделях

2.3. Критерии существования в классических ОС-моделях основных типов неконструируемости конфигураций

2.4. Алгоритмические аспекты проблемы неконструируемости и связанные с нею вопросы динамики классических ОС-моделей

2.5. Суръективность и инъективность глобальных параллельных отображений в классических ОС-моделях

2.6. Специальные вопросы проблемы неконструируемости в ОС-моделях

2.7. Особенности проблемы неконструируемости для конечных классических однородных структур

2.8. Вопросы обратимости динамики классических однородных структур

2.9. Особенности проблемы неконструируемости для однородных структур на разбиении

Глава 3. Экстремальные конструктивные возможности классических однородных структур

3.1. Универсальные конечные конфигурации в классических ОС-моделях

3.2. Самовоспроизводящиеся конечные конфигурации в ОС-моделях

3.3. Универсальные и самовоспроизводящиеся конечные конфигурации для однородных структур на разбиении

Глава 4. Проблема сложности конечных конфигураций в классических однородных структурах

Глава 5. Параллельные формальные грамматики и языки, определяемые классическими однородными структурами

5.1. Основные свойства параллельных языков, определяемых классическими однородными структурами

5.2. Параллельные грамматики, определяемые ОС-моделями, и формальные грамматики других классов и типов

5.3. Параллельные грамматики, определяемые недетерминированными однородными структурами

5.4. Алгоритмические проблемы теории параллельных грамматик, определяемых классическими однородными структурами

Глава 6. Проблема моделирования в классических однородных структурах и связанные с ней вопросы

6.1. Понятия моделирования в классических однородных структурах

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

6.3. Моделирование классических однородных структур структурами из того же класса формальных объектов

6.4. Специальные вопросы моделирования в классических однородных структурах, связанные с их динамическими свойствами

6.5. Формальные параллельные алгоритмы, определяемые классическими одномерными однородными структурами

6.6. Программное обеспечение и аппаратура для симулирования ОС-моделей

Глава 7. Проблема декомпозиции глобальных функций перехода в классических ОС-моделях

7.1. Декомпозиция специальных глобальных функций перехода в ОС-моделях

7.2. Некоторые подходы к решению общей проблемы декомпозиции

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

7.4. Проблема сложности глобальных функций перехода в ОС-моделях

7.5. Специальные вопросы исследований в ТОС-проблематике

Глава 8. Некоторые прикладные аспекты ОС-проблематики

8.1. Некоторые аспекты использования ОС-моделей в математике

8.1.1. Решение одной комбинаторной проблемы Г. Штейнгауза

8.1.2. Решение одной проблемы С. Улама из теории чисел

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

8.2. Некоторые аспекты использования ОС-моделей в биологии

8.2.1. Основные предпосылки модельного подхода в биологии развития

8.2.2. Формальные дискретные модели самовоспроизведения

8.2.3. Формальное моделирование процессов роста в среде однородных структур

8.2.4. Формальные ОС-модели дифференциации, регуляции и регенерации в биологии развития

8.2.5. Сравнительный анализ ОС-моделей и L-систем как формального аппарата модельных исследований в биологических науках

8.3. Вопросы использования ОС-моделей в вычислительных науках

8.4. Некоторые другие области приложений однородных структур

Заключение

Summary of the General Results

Литература

Предисловие

Современные тенденции развития перспективных архитектур высоко параллельной вычислительной техники (ВТ), проблемы моделирования дискретных параллельных процессов, теория параллельных дискретных динамических систем, дискретная математика и синергетика, задачи искусственного интеллекта и робототехники, параллельные алгоритмы и обработка информации, физическое и биологическое моделирование, а также целый ряд других важных предпосылок в различных областях современного естествознания определяют в последние годы новый подъем интереса к различного рода клеточным формальным моделям высоко параллельного образа действия, важнейшими из которых являются однородные структуры (ОС; основной синоним – «клеточные автоматы»; в англоязычной терминологии соответственно – «Homogeneous Structures» и «Cellular Automata»). За время, прошедшее после выхода в свет первых монографий и сборников статей, посвященных различным теоретическим и прикладным аспектам ОС-проблематики, достигнут определенный прогресс в этом направлении, что связано, в первую очередь, с успехами теоретического характера, существенным расширением сферы приложений ОС-моделей (главным образом, в вычислительных науках, физике, биологии, информатике и кибернетике) и значительным увеличением числа исследователей в данной области. Наряду с этим, в США, Японии, Великобритании, Германии и Эстонии появился ряд монографий и сборников, обобщающих и суммирующих итоги развития тех или иных направлений теории ОС (ТОС) и ее многочисленных приложений. Наши монографии на содержательном уровне представили обзор основных результатов по ТОС-проблематике, полученных Таллиннской Творческой Группой за 30-летний период ее научно-прикладной деятельности, исключая десятилетний перерыв (1997 – 2006), обусловленного активной работой над системами компьютерной алгебры (CAS) такими, как Mathematica и Maple.

С теоретической точки зрения клеточные автоматы (Cellular Automata – CA) были введены в конце 1940-х Джоном фон Нейманом с подачи С. Улама как формальные модели самовоспроизведения организмов. При этом, изученные ими структуры были, главным образом, 1- и 2-мерными, хотя рассматривались и более высокие размерности. Вопросы универсальности вычислений наряду с другими теоретическими вопросами поведения такого типа структур также не были упущены из вида. СА-модель Дж. фон Неймана получила свое дальнейшее развитие в работах его непосредственных последователей, результаты которых вместе с законченной и отредактированной работой самого Дж. фон Неймана были изданы А. Берксом. Дальнейшее развитие и популяризация СА-проблематики связаны с именами таких исследователей как В.З. Аладьев, S. Amoroso, E. Banks, J. Buttler, E. Codd, S. Cole, G. Hedlund, G. Herman, J. Holland, M. Kimura, Y. Kobuchi, A. Maruoka, E.F. Moore, J. Myhill, H. Nishio, T. Ostrand, A.R. Smith, T. Yaku, H. Yamada, A. Waksman и некоторых других, чьи работы в 1960-х – 1970-х привлекли внимание к данной проблематике с теоретической точки зрения, а также решили и сформулировали целый ряд достаточно интересных проблем. Впоследствии, математики, физики и биологи начали изучать и использовать клеточные автоматы (однородные структуры) для проблем моделирования в своих собственных областях исследования.

В настоящее время ОС-модели исследуются со многих точек зрения и взаимосвязь этих однородных структур с уже существующими проблемами постоянно обнаруживаются. В целях общего ознакомления с обширной СА-проблематикой в целом и с ее отдельными направлениями рекомендуется обратиться к интересным и разноплановым обзорам таких исследователей, как В.З. Аладьев, V. Cimagalli, K. Culik, D. Hiebeler, A. Lindenmayer, A.R. Smith, P. Sarkar, M. Mitchell, T. Toffoli, R. Volmar, S. Wolfram и др. Ряд книг и монографий таких авторов, как В.З. Аладьев, A. Aдаматский, E. Codd, A. Ильяшинский, M. Duff, M. Garzon, P. Kendall, M. Duff, В. Кудрявцев, N. Margolus, T. Toffoli, O. Martin, K. Preston, M. Sipper, R. Vollmar, B. Voorhees, S. Wolfram и некоторых других также содержат некоторые исторические экскурсы в ОС-проблематику; к сожалению, единой точки зрения по данному историческому вопросу не существует. Наконец, библиография, представленная в настоящей монографии, содержит много очень полезных ссылок на работы по СА-проблематике, включая ее многочисленные прикладные аспекты. Данная библиография полезна, прежде всего, именно начинающим исследователям в данной области.

С начала наших научных исследований в 1969 г. по ТОС и ее приложениям, прежде всего, в математической биологии развития постепенно сформировалась неформальная Таллиннская творческая группа (ТТГ), включающая исследователей из ряда крупных научных центров бывшего Союза. Состав ТТГ не являлся строго определенным и изменялся в зависимости от тематики исследуемых проблем в тот или иной период времени. Полная библиография работ ТТГ, включая работы по ТОС-проблематике, может быть найдена в наших монографиях. Там же представлена обширная библиография работ и других исследователей, внесших существенный вклад в развитие теоретических и прикладных аспектов данного направления современной математической кибернетики, выходящего на уровень междисциплинарного предмета. Весьма обширная библиография к настоящей монографии содержит наиболее доступные наши работы, содержащие основные, полученные ТТГ, результаты по ТОС-проблематике, а также целый ряд наиболее известных зарубежных работ в данном направлении. В настоящее время ТОС интенсивно развивается большим коллективом исследователей во многих странах мира и, в первую очередь, в США, Германии, Великобритании, Италии, Франции, Японии и Венгрии. Сформировался целый ряд исследовательских групп в этих странах. До последнего времени активная научная деятельность в этом направлении проводилась и в Эстонии в рамках ТТГ (впоследствии Балтийского отделения Международной Академии Ноосферы), целый ряд результатов которой получил международное признание и составил существенную часть современной ТОС.

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

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

(1) формальная модель высоко параллельной обработки информации во всей ее общности;

(2) удобная среда моделирования разнообразных естественных и искусственных дискретных систем, процессов, явлений и феноменов, допускающих высокий уровень распараллеливания.

Интерес к ним усиливается также возможностью практической реализации высоко параллельных вычислительных ОС-моделей на основе современных успехов микроэлектроники и перспективами обработки информации на молекулярном уровне (нанотехнология). ОС-концепция обеспечивает построение концептуальных и практических моделей пространственно-распределенных динамических систем, из которых физические являются наиболее интересными и перспективными.

Модели, явным образом сводящие макроскопические процессы к строго определенным микроскопическим процессам, представляют особый гносеологический и методический интерес, ибо они обладают большой убедительностью и прозрачностью. Именно с этой точки зрения ОС-модели представляют особый интерес (прежде всего) в прикладном отношении при исследовании целого ряда процессов, явлений и феноменов в различных областях, и в первую очередь в физике. В частности, на основе ОС можно создавать весьма простые модели дифференциальных уравнений физики (Навье-Стокса, теплопроводности и др.), динамики жидкостей и газов, целого ряда задач коллективного поведения, например хаос, турбулентность, фрактальность, упорядочение и др. И еще на одном весьма существенном аспекте следует остановиться особо, а именно на месте ТОС-проблематики в системе современных наук.

Именно в этой связи имеет смысл вкратце остановиться на книге «A New Kind of Science» (Наука нового типа и не менее) С. Вольфрама и именно в свете корректной идентификации места ТОС-проблематики в составе других разделов современного естествознания. Объемное издание лишь на первый взгляд может служить неким откровением для тех, кто ни в малейшей мере не знаком с ТОС-проблематикой (клеточными автоматами, Cellular Automata). Несмотря на то, что книга содержит немало (в целом ряде случаев весьма интересных) примеров применения ОС-моделей (клеточных автоматов), как ее стиль, так и целый ряд содержащихся в ней утверждений носит тенденциозный характер, не имея реального подтверждения. Само же ее название носит, скорее, коммерческий характер, рассчитанный на широкую публику, а не на серьезную научную аудиторию. Отметим только некоторые из авторских откровений, а именно. «Эта книга – результат двадцатилетнего труда по созданию науки нового типа. Я и не предполагал, что все так затянется. Работа затрагивает практически все сферы познания и даже простирается немного дальше за их пределы. Я пришел к выводу, что мое открытие – одно из наиболее важных во всей истории теоретической науки.». Далее автор утверждает, что компьютерные модели, названные клеточными автоматами, представляют ключ к пониманию всех сложностей природы, от кварков до экономических систем. Он утверждает, что его книга была понята как «инициирующая в науке сдвиг парадигмы исторической важности, с новыми приложениями, появляющимися каждый год все в большем количестве.»

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

Не вдаваясь в детальный обзор указанной книги (некоторые из отзывов и рецензий на нее можно найти в нашей монографии и в Интернете), только отметим, что вопреки преследуемым целям, она не только не явилась откровением для специалистов, работающих по ТОС-проблематике, но и в определенной мере сформировала несколько искаженное представление о самой области исследований, на самом деле достаточно перспективной со многих точек зрения. Хотя, быть может, она и явилась откровением для любителей, интересующихся различного рода околонаучными теориями, либо неспециалистов. Не красит книгу не только откровенно спекулятивный характер изложения (когда в целом ряде случаев автор пишет о вещах, не имея на то понятия), но и уничижительный тон к своим коллегам, которыми в целом ряде случаев получены намного более серьезные результаты, искажение истории предмета, косвенное приписывание чужих результатов, менторский тон, ничем не обоснованные утверждения и многое другое, что не позволяет нам рассматривать данную книгу в качестве серьезного научного исследования. При этом, не стоит рассматривать наше мнение слишком предвзято, из многочисленных отзывов на книгу оно смотрится в достаточно выдержанных тонах (Internet по фразе «A Collection of Reviews of ANKOS» - http://shell.cas.usf.edu/~eclark/ANKOS_reviews.html).

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

(1) ОС (клеточные автоматы) представляют собой один из типов бесконечных абстрактных автоматов со специфической внутренней организацией, обуславливающей весьма высокий уровень распараллеливания обработки информации и вычислений; они образуют специфический класс дискретных динамических систем, функционирующих сугубо параллельным образом на основе принципа локального близкодействия; это позволяет исследовать их в русле и методами систем подобного типа;

(2) ОС могут служить вполне удовлетворительной моделью параллельных вычислений аналогично тому, как машины Тьюринга (нормальные алгоритмы Маркова, системы продукций Поста, TAG-, LAG-системы и др.) служат в качестве формальных моделей последовательных вычислений; подобно вторым ОС-модели обладают свойством универсальной вычислимости; с этой точки зрения ОС можно рассматривать и как алгебраические системы переработки конечных слов на основе правил параллельных подстановок;

(3) принцип локального взаимодействия составляющих ОС единичных конечных автоматов, определяющего в результате их глобальную динамику, позволяет использовать ОС в качестве прекрасной среды моделирования/симулирования весьма широкого круга процессов, явлений и феноменов; при этом, феномен обратимости ОС-динамики делает ОС весьма интересной средой как для физического моделирования, так и для создания перспективных вычислительных структур, использующих нанотехнологии. При этом, ОС можно рассматривать, прежде всего, как модельную альтернативу дифференциальным уравнениям в частных производных.

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

В целом же, ТОС-проблематику, на наш взгляд, с большой долей достоверности можно представить себе как две составляющие, а именно:

(1) ОС в качестве самостоятельного математического объекта исследований (например, как высоко параллельные дискретные динамические системы, формальные параллельные алгоритмы и грамматики и др.);

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

Как правило, первая составляющая достаточно интенсивно развивается математиками, тогда как свой вклад в развитие второй составляющей вносит существенно более представительный круг исследователей из различных естественно-научных как теоретических, так и прикладных областей (физика, химия, биология, техника и др.). При этом, если сугубо теоретические исследования по ТОС-проблематике в основе своей ограничиваются классическими, полигенными и стохастическими ОС, то результаты второй составляющей базируются на существенно более широком представительстве и типов, и классов ОС-моделей, наделяющих составляющие их элементарные автоматы самыми разнообразными свойствами и с достаточно сложными правилами локального взаимодействия между ними. В целом, если классические ОС-модели представляют собой, прежде всего, формальные математические системы, исследуемые именно в данном контексте, то их многочисленные модификации и обобщения – достаточно перспективная среда моделирования тех либо иных процессов, явлений, объектов и феноменов.

Как нами уже отмечалось, в отличие от целого ряда других современных разделов естественных наук теоретическая составляющая ТОС-проблематики не столь существенно пересекается с ее второй прикладной составляющей и в этом отношении вполне уместно говорить о ТОС-проблематике как о двух достаточно самостоятельных направлениях – исследование математических ОС-объектов как таковых и использование ОС-среды для моделирования/симулирования; при этом, второе направление характеризуется и более широким спектром направлений сугубо прикладного характера. Уровень развития второго направления в значительной мере определяется возможностями современной ВТ, ибо ОС-модели, как правило, реализуются на большом числе единичных автоматов и, как правило, с достаточно сложными правилами локального взаимодействия единичных автоматов.

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

Наряду с попыткой, по-возможности, полнее охватить CA-проблематику, лежащую как в русле наших интересов, так и в фундаменте собственно ТОС, в данной монографии с достаточной степенью полноты представлены результаты и отечественных исследователей. Многие из этих результатов малоизвестны или совсем неизвестны англоязычному читателю, хотя целый ряд из них внесли весьма существенный вклад в становление современной теории однородных структур (Homogeneous Structures) {синоним «клеточных автоматов» (Cellular Automata)} и их приложений в качестве самостоятельного раздела современной математической кибернетики. Впоследствии целый ряд из них были заново переоткрыты другими исследователями. Часть из них представлены нами более детально, тогда как другие указаны в перечне работ, содержащих наиболее важные результаты.

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

Монография базируется на специальном курсе лекций «Классические Однородные Структуры (Классические Клеточные Автоматы)", который был проведен первым автором в Гродненском государственном университете (Гродно, Беларусь) в апреле – мае 2008.

Aladjev V.Z., Boiko V.K., Rovba E.A. Classical Cellular Automata: Theory and Applications.– Grodno: Grodno State University, 2008, 486 c., ISBN 978-9985-9508-4-5, 978-985-551-020-7

Introduction

In the monograph we present certain results of the work we have done in mathematical theory of the classical homogeneous structures (HS; synonym «Cellular Automata») during 1968 – 2007. Much of our research has been stimulated by scientific programs of Tallinn Research Group (TRG) and International Academy of Noosphere (IAN). At present, Cellular Automata (CA) problems is the well enough developed independent field of the modern mathematical cybernetics, which has considerable sphere of applications. Above all, it is necessary to emphasize, that in Russian terminology (basics of which in our monograph were presented for the first time) for the concept «Cellular Automata (CA)» the most widespread synonym «Homogeneous Structures (HS)» is used. Therefore this term is used most widely for the space of the given monograph.

The HS is a parallel information processing system consisting of intercommunicating identical finite automata. Although homogeneous structures will be used throughout this monograph as the usual term, it should be borne in mind that cellular automata, iterative networks etc. are essentially synonyms. We can interpret HS as a theoretical framework of artificial parallel information processing systems. From the logical point of view the HS is an infinite automaton with characteristic internal structure. The HS theory can be considered as structural and dynamical theory of the infinite automata. HS can serve as the basis for modeling of many discrete processes and they present interesting enough independent objects for investigations as well. In recent years has arisen undoubted interest to the HS theory and in this direction many remarkable results have been obtained. Much of this work has been activated by the growing interest in computer science and mathematical modeling. At present, the HS theory forms an original part of the modern mathematical cybernetics.

The monograph is based on the special lecture course «Classical Homogeneous Structures (Classical Cellular Automata)» that has been given by the first writer at the Grodno State University (Grodno, Belarus) during April – May, 2008.

Contents

Preface

Introduction

Chapter 1. The basic concept of homogeneous structures (HS-models, Cellular Automata)

1.1. The basic concepts, definitions and designations

1.2. The basic types of homogeneous structures

1.3. Architecture of the theory of homogeneous structures and its applications

1.4. Technique of researches in the theory of homogeneous structures

Chapter 2. Nonconstructibility problem in classical homogeneous structures (impossibility to generate certain configurations)

2.1. Preliminary information on the problems

2.2. Types of nonconstructibility in classical HS-models (NCF, NCF-1, NCF-2, NCF-3)

2.3. Criteria of existence in classical HS-models of the basic types of nonconstructibility

2.4. Algorithmic aspects of the nonconstructibility problem and the associated questions of dynamics of classical HS-models

2.5. Surjectivity and injectivity of global parallel maps in classical HS-models

2.6. Special questions of the nonconstructibility problem in classical HS-models

2.7. Peculiarities of the nonconstructibility problem for finite classical homogeneous structures

2.8. Questions of reversibility of dynamics of classical homogeneous structures

2.9. Features of the nonconstructibility problem for homogeneous structures on splitting

Chapter 3. Extreme constructive opportunities of classical homogeneous structures

3.1. Universal finite configurations in classical homogeneous structures

3.2. Self-reproduction of finite configurations in classical homogeneous structures

3.3. Universal and self-reproducing finite configurations for homogeneous structures on splitting

Chapter 4. Problem of complexity of finite configurations in classical homogeneous structures

Chapter 5. Parallel formal grammar and languages defined by homogeneous structures

5.1. The basic properties of parallel languages defined by classical homogeneous structures

5.2. Parallel grammars, determined by classical homogeneous structures along with formal grammars of other classes and types

5.3. Parallel grammars, defined by non-deterministic homogeneous structures

5.4. Algorithmic problems of the theory of parallel grammars, defined by homogeneous structures

Chapter 6. Problem of modeling in classical homogeneous structures, and the connected questions

6.1. Concepts of modeling in classical homogeneous structures

6.2. Modeling of the known formal algorithms of processing of words by classical homogeneous structures

6.3. Modeling of classical homogeneous structures by structures from the same class

6.4. Special questions of modeling in the classical homogeneous structures, linked with their dynamic behavior

6.5. The formal parallel algorithms defined by classical one-dimensional homogeneous structures

6.6. The software and hardware for simulation of homogeneous structures

Chapter 7. Problem of decomposition of the global transition functions in classical homogeneous structures

7.1. Decomposition of the special global transition functions in classical HS-models

7.2. Certain approaches to decision of the general problem of decomposition

7.3. Problem of complexity of global transition functions in classical HS-models, and questions of its algorithmic solvability

7.4. Problem of complexity of global transition functions in HS-models

7.5. Special questions of researches in the HS problems

Chapter 8. Certain applied aspects of the HS problems

8.1. Certain aspects of use of HS-models in mathematics

8.1.1. The solution of a combinatory H. Steinhaus problem

8.1.2. The solution of a S. Ulam problem from the theory of numbers

8.1.3. Algebraic system for polynomial representation of local transition functions in classical homogeneous structures

8.2. Certain aspects of use of HS-models in biology

8.2.1. The basic prerequisites of the model approach in biology of development

8.2.2. Formal discrete models of self-reproduction

8.2.3. Formal modeling of processes of growth in the HS-environment

8.2.4. Formal HS-models of differentiation, regulation and regeneration in biology of development

8.2.5. The comparative analysis of HS-models and L-systems as a formal method of the model investigations in biological sciences

8.3. Certain questions of use of HS-models in computer sciences

8.4. Some other fields of applications of homogeneous structures

Conclusion

References

Paperback: 485 pages

Publisher: Grodno State University (May, 2008)

Language: Russian & English

ISBN: 978-9985-9508-4-5,  978-985-551-020-7

Product Dimensions: 295 x 210 x 28 mm

Shipping Weight: 1.5 kg

Price: $19 (for countries of the CIS) and $36 (for other countries) including shipping

Orders for the above monograph should be sent into the following addresses, namely:

sales@lit.by,  http://www.ozon.ru/context/detail/id/4034873/

At last, on the following web-sites you can find the extended bibliography on Cellular Automata (Homogeneous Structures):

http://www.geocities.com/ca_hs_ref/biblio.htm

http://www.geocities.com/vz_aladjev

http://www.website-hit-counters.com

Grsu, Grodno, Belarus, May-June 2008