ПРОГРАММИРОВАНИЕ, 2009, № 4, с. 15-23
ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ПРОГРАММИРОВАНИЯ ~
УДК 681.32
ПРОГРАММА-КОНСТРУКТОР КЛЕТОЧНЫХ САМОВОСПРОИЗВОДЯЩИХСЯ СТРУКТУР
© 2009 г. С. М. Ачасова
Институт вычислительной математики и математической геофизики СО РАН 630090 Новосибирск, просп. Академика Лаврентьева, 6 E-mail: achasova@ssd.sscc.ru Поступила в редакцию 24.09.2007 г.
На основе алгоритма параллельных подстановок (АПП) - пространственной модели мелкозернистых параллельных вычислений - разработана простая программа для построения клеточной прямоугольной самовоспроизводящейся петли, имеющей произвольный размер. Для запуска самовоспроизведения петли конкретного размера достаточно подать ее описание на входную ленту. Программа снабжена командами предварительного очищения клеточного массива, что позволяет легко изменять его внутреннюю функциональную структуру. Программа разработана в двух вариантах. Первый вариант строит цепочку из самовоспроизводящихся петель заданного размера, второй - массив из таких петель.
1. ВВЕДЕНИЕ
Систематические исследования самовоспроизводящихся структур были начаты Джоном фон Нейманом более 40 лет назад с целью определить, какого сорта логическая организация достаточна для того, чтобы устройство, имеющее такую организацию, было способно воспроизвести свою копию [1]. Фон Нейман желал алгоритмически описать основное свойство всего живого - порождать себе подобных. Для своих построений фон Нейман использовал идею клеточного автомата (КА) в качестве формальной математической основы. Фон Нейманом был создан клеточный автомат, который являлся универсальным вычислителем и был способен конструировать в клеточном пространстве любой другой КА, описание которого было дано в виде некоторой конфигурации на его входной ленте. Если был описан сам автомат, то это был случай самовоспроизведения. Далее Кодд [2] упростил неймановскую универсальную машину, сократив число состояний клетки с 29 до 8. Но это все еще была весьма громоздкая структура, с огромным числом правил изменения состояний клетки, и ее логическая организация являлась достаточной для самовоспроизведения.
Следующим важным событием в развитии теории самовоспроизведения была работа Лангто-на [3]. В ней было показано, что можно построить существенно более простую по сравнению с автоматом фон Неймана структуру, которая, не будучи универсальной, обладает способностью к самовоспроизведению и чья логическая организация является только необходимой для самовоспроизведения. Структура имеет вид прямоугольной петли, помещенной в 2Б клеточно-автоматное пространство. В петле динамически хранится ее самоописание (геном) в виде циркулирующей в ней последовательности состояний клеток. Эта последовательность управляет построением дочерней петли и одновременно переписывается в нее, благодаря чему дочерняя петля способна построить свою дочку. Таким образом, информация, циркулирующая в петле, используется двояко: она служит программой для построения копии и переписывается в дочернюю структуру как неинтерпрети-руемые данные. Хотя самовоспроизводящаяся петля Лангтона - довольно простая структура (86 клеток), она имеет несколько сотен правил перехода клетки из одного состояния в другое. Последовали упрощения [4, 5], были созданы са-
мовоспроизводящиеся петли, включающие в себя меньшее (до 12) число клеток и имеющие меньшее (до нескольких десятков) число правил перехода.
Петля Лангтона стала удобной и популярной моделью самовоспроизводящейся структуры для различного рода исследований. Среди них - использование петли в качестве модели при проверке гипотез, относящихся к возникновению биологической жизни (изучались условия спонтанного появления репликаторов из случайного начального распределения состояний клеток в пространстве, взаимодействие репликаторов, способность их мутировать) [6, 7]. Петлю наделяют свойствами универсального конструирования [8], или делают ее способной взаимодействовать с внешним наблюдателем [9].
Кроме того, самовоспроизводящиеся в клеточном пространстве петли интересны тем, что предлагают новую парадигму для построения параллельных мелкозернистых алгоритмов и архитектур. Предложена идея программировать репликатор таким образом, чтобы можно было производить дополнительную работу вместе с реплицированием [10]. На основе петли Лангтона предложено несколько вариантов так называемого "полезного репликатора", в нем самоописание или программа реплицирования дополняется некоторой вычислительной программой, и вместе с построением копий решается некоторая вычислительная задача [10-12] (например, выполняются арифметические операции, или решается комбинаторная задача). Исследования показывают, что программируемые репликаторы могут привести к созданию новых быстрых вычислительных методов и стать основой для создания новой мощной вычислительной среды с массовым параллелизмом. Построение различных моделей самовоспроизведения, в том числе, с возможностями перепрограммирования, и использование для этого новых выразительных средств вносят свой вклад в эту работу.
В статье предлагается простая программа построения клеточной прямоугольной самовоспроизводящейся петли любого заданного размера. До сих пор для построения самовоспроизводящейся петли определенного размера создавалась конкретная клеточно-автоматная програм-
ма, и есть указания (например, в [9]), что на основе классической клеточно-автоматной модели синтезировать одну программу для построения петли любого размера можно только ценой существенного увеличения числа правил перехода автомата.
Предлагаемая работа является развитием темы, изложенной в [13]. Свою простую программу мы строим на основе алгоритма параллельных подстановок (АПП), беря в качестве прототипа АПП-модель самовоспроизводящейся петли размера 3x3, описанной в [13]. Алгоритм параллельных подстановок, являясь расширенной парадигмой классического клеточного автомата, имеет по сравнению с КА некоторые новые свойства, усиливающие его выразительные возможности [14, 15]. Эти свойства состоят в следующем. Допускается произвольный шаблон подстановки. В каждом такте одна подстановка может изменять состояния сразу нескольких клеток. Введен новый тип подстановки -функциональная подстановка, в ней новые состояния клеток являются функциями от состояний соседних клеток. Эти свойства АПП дают возможность строить лаконичное, легко обозримое и структурированное описание самовоспроизведения петли произвольного размера.
В работе представлены две программы на основе алгоритма параллельных подстановок (Ш Сопэ^ и 2Б Сопз1г), первая из которых строит цепочку из клеточных самовоспроизводящихся петель заданного размера, вторая -массив из таких петель. Программа Ш Сопв^ содержит 12 параллельных подстановок, в их числе подстановки, осуществляющие стирание ранее построенной структуры. Стирание старой структуры и построение новой начинается от границы клеточного массива, а именно, от левого нижнего угла, где расположена входная лента. Команда об очищении клеточного массива подается на входную ленту. Описание новой структуры в виде последовательности состояний автомата также приходит на входную ленту. Программа 2Б Сопв^ состоит из 19 параллельных подстановок, в их числе также имеются подстановки, осуществляющие очищение клеточного массива от ранее построенных структур.
Р1 V и Р2 и 8 РЗ в г Р4 г у Р5 в г Рб г
г в у г и V 8 и 8
Р7
V и и) Р8
г в
IV
и в V г
Р9 в г
РЮ
г у в и 11)
Рис. 1.
5 1 2 1 4
1 2 1 1 4
- 2 1
- 3 5 -
- 5
- 1
Рис. 2.
в6: ш Р7 (1о /о в7: ш Р1, Р4 с!о /1 6>8: ш Р2 с!о /2 : ш РЗ ао /3 0ю: т Р1, Р2, РЗ, Р4 с!о /4 6»ц: т Р5, Р6 с!о /5 012: т Р7, Р9, РЮ с!о /6
2. АЛГОРИТМ ПАРАЛЛЕЛЬНЫХ ПОДСТАНОВОК
В данной работе АПП функционирует в двумерном пространстве, разделенном на клетки, и в дискретном времени. Каждая клетка может находиться в одном состоянии из набора возможных и изменять свое текущее состояние согласно локальному правилу или подстановке, в которой новое состояние клетки определяется ее текущим состоянием и состояниями клеток, входящих в шаблон подстановки. Подстановки могут иметь произвольный шаблон - геометрический образ в дискретном пространстве. Левая часть подстановки определяет условие ее применимости и состоит из двух частей - базы и контекста. Правая часть подстановки задает новые состояния клеткам базы. Состояния клеток своего контекста подстановка не изменяет. Новые состояния базовых клеток могут быть либо просто состояниями из множества возможных (тогда подстановка называется символьной), либо функциями от состояний клеток
левой части подстановки (в этом случае подстановка называется функциональной). Все применимые в некотором такте дискретного времени подстановки выполняются одновременно. Поскольку в АПП допускается произвольный шаблон подстановки, то возможна ситуация, в которой одна и та же клетка оказывается в зоне применимости двух подстановок. Если эта клетка в обеих подстановках является контекстной, или в одной - контекстной, а в другой - базовой, то не возникает проблемы с изменением ее состояния. Не возникает проблемы и в том случае, когда клетка является базовой в обеих подстановках и ее новое состояние является одним и тем же в этих подстановках. Противоречие в применимости подстановок возникает, если состояние общей клетки изменяется двумя подстановками по-разному. Алгоритм параллельных подстановок должен содержать непротиворечивое множество подстановок. В [14, 15] сформулированы критерии непротиворечивости и даны способы проверки множества параллельных подстановок на непротиворечивость.
IV и V
х
/о т = V. Я [и = = У А (то = 0 V ш = 3)]
/1 V = и, а [(« = 2 V 5 = з у г = 2 у г = 3) Аи Ф 0 д и ф 5]
/2 V = и, а [(« = з) V г = = 3 У г = 2) Аи /0]
/з V = и, а [(« = 2 V 5 = ЗУ в = 5У г =
и V = 1, а [(« = 2\/г = 2) А V = 0 А и = 4]
/5 г = •5, а = = X У (5 = = у д г = з) V 5 = ЗА^ = 2)]
/б г = •5, а = = 2/М = 2)Лъи = 4Ли = = 4А V = 0]
Рис. 3.
3. Ш СОШТИ, ДЛЯ ПОСТРОЕНИЯ САМОВОСПРОИЗВОДЯЩЕЙСЯ ПЕТЛИ ПРОИЗВОЛЬНОГО РАЗМЕРА
С помощью предлагаемой программы строится цепочка из петель заданно
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.