Брайан Хэйес,
"В МИРЕ НАУКИ"

     Удивительно, что молекулы воды "знают", как создавать сложные симметричные снежинки. Никакой "архитектор" не руководит строительством, и молекулы не несут информации об этой кристаллической структуре. Весь узор возникает в результате ближних взаимодействий множества одинаковых частиц. Каждая молекула реагирует только на воздействие ближайших соседей, но расположение в определенном порядке сохраняется во всей структуре, состоящей примерно из 10^20 молекул.
     Чтобы лучше понять этот процесс, представим себе, что каждое место, где молекула может быть помещена (так называемый центр), управляется с помощью элементарного компьютера. По мере роста кристалла компьютер наблюдает за соседними центрами и, находя их, определяет по некоторому установленному правилу, должно ли быть занято его собственное место, или оно должно пустовать. Подобные вычисления проводятся для всех центров по одному и тому же правилу.
     Вычислительная модель роста снежинки является клеточным, или ячеистым, автоматом - однородной схемой многих идентичных клеток, или ячеек, причем каждая клетка имеет несколько возможных состояний и взаимодействует лишь с несколькими соседними клетками. Компоненты системы - клетки, или ячейки, и правило вычисления следующего состояния клетки может быть простым, но тем не менее вызывает весьма сложную эволюцию.

     Идея автомата с клеточной структурой почти также стара, как и идея электронно-вычислительной машины. Первые исследования были проведены в начале 50-х годов Дж. фон Нейманом (следует учесть важный вклад в эти разработки С. Улама). Первоначальная цель фон Неймана состояла в создании простой системы, способной воспроизводить саму себя подобно живому организму. Наиболее известный клеточный автомат - игра "Жизнь", придуманная в 1970 г. Дж. Конвеем, как ясно из названия, также имеет биологический аспект: клетки рождаются, живут или умирают в зависимости от локальной плотности популяции.
     В более поздних работах, посвященных клеточным автоматам, исследования приняли несколько другое направление. Конфигурации локально взаимодействующих клеток рассматриваются как потенциально важные модели физических систем - от снежинок до ферромагнетиков и Галлактики. Они применимы также к вопросам кибернетики и вычислительной математики, как практическим (как следует организовать сеть взаимодействующих ЭВМ?), так и теоретическим (каков самый крайний предел мощности вычислительной машины?). Возможно, наиболее интригующим является тот факт, что клеточный автомат может рассматриваться как "числовая вселенная", которая сама по себе достойна исследования, даже если отвлечься от ее полезности как модели реального мира.
     Возрождение интереса к клеточным автоматам было отмечено созданием рабочей группы по данной теме год назад в Лос-Аламосской национальной лаборатории. Был опубликован сборник работ (около 20 статей) в журнале "Physics D" и отдельным выпуском в издательстве "North-Holland". Почти все, что содержиться в этом сборнике, основано на работах обсуждавшихся на специальном симпозиуме в Лос-Аламосе.
     Для характеристики клеточного автомата полезно выделить четыре его аспекта. Во-первых, расположение клеток образует некоторую геометрическую структуру. Для модели роста снежинок достаточна двумерная шестиугольная схема, но в большинстве других случаев выбирается прямоугольная решетка, состоящая из квадратов. Легко можно построить трехмерную (и даже с большим числом измерений) схему, но гораздо труднее ее себе представить. Недавно поразительные открытия были сделаны с простейшей одномерной схемой: простой цепочкой клеток.
     Далее при заданной схеме необходимо определить ту окрестность, которую данная клетка изучает при вычислении своего следующего состояния. В случае двумерных прямоугольных схем особое внимание уделяется окрестностям двух видов. Фон Нейман рассматривал четыре ближайших соседа каждой клетки: на севере, юге, востоке и западе; это множество клеток теперь называют окрестностью фон Неймана. Окрестность, включающую эти четыре соседние клетки и четыре клетки, прилегающие к исходной по диагоналям, называют окрестностью Мура (в честь Э. Мура). Ясно, что окрестности пересекаются и данная клетка входит сразу в несколько окрестностей. В некоторых случаях считают, что центральная клетка - та клетка, которая производит вычисления, - сама входит в свою окрестность.
     Третий фактор, который следует рассматривать при описании клеточного автомата, - это число состояний, которое может принимать клетка. Фон Нейман построил самовоспроизводящуюся систему, составленную из клеток с 29 возможными состояниями, однако большинство автоматов гораздо проще. Имеется огромный диапазон для изменений даже у двоичных автоматов, у которых клетка имеет два возможных состояния. Состояния могут быть представлены как 1 или 0 (включено или выключено, живое или мертвое).
     Наконец, первоисточник изменений в мире клеточных автоматов - это огромное число возможных правил для определения будущего состояния клетки исходя из теперешней конфигурации ее соседей. Если k - число состояний, которое может принимать каждая клетка, а n - число клеток, входящих в окрестность, то существует k^k^n возможных правил. Так, для двоичного автомата с окрестностью фон Неймана (где n = 4) существует более чем 65000 возможных правил; для окрестности Мура (где n = 8) имеется 10^77 правил. Однако лишь малая их часть когда-либо изучалась.

     В игру "Жизнь" играют на прямоугольной решетке из клеток с двумя состояниями и с окрестностью Мура и дополнительным усложнением, согласно которому центральная клетка тоже считается членом своей окрестности. Другими словами, при каждом шаге эволюции системы каждая клетка проверяет состояния восьми своих соседей и свое собственное. Согласно правилам, установленным Конвеем, если центральная клетка жива, то она будет жить в следующем поколении, когда две или три клетки из ее окрестности живы. Если найдутся три живые клетки в рассматриваемой окрестности, то центральная клетка будет живой в следующем поколении независимо от ее теперешнего состояния. Во всех других случаях центральная клетка либо умирает, либо остается мертвой.
     Прелесть игры "Жизнь" состоит в ее непредсказуемости. Некоторые схемы полностью умирают; многие другие образуют устойчивые конфигурации либо циклические конфигурации с периодом в несколько поколений. Однако за прошедшие годы было найдено много очень интересных начальных состояний, таких, как "скользящая пушка", которая порождает нескончаемый поток снарядов. Исследование игры "Жизнь" в настоящее время продолжается. Последние достижения были описаны Мартином Гарднером в книге "Wheels, Life, and Other Mathematical Amusements". Здесь же я рассмотрю другие клеточные автоматы, свойства которых только начинают исследовать.
     Среди множества возможных правил перехода лишь немногие интересны сами по себе. Например, правило, устанавливающее, что данная клетка будет "включена" тогда и только тогда, когда клетка слева от нее включена, определяет эволюцию, которую очень легко предсказать: любая начальная схема сохраняет свою конфигурацию, но сдвигается на одну клетку вправо на каждом временном шаге. Подкласс правил, называемых счетными, или суммирующими, по-видимому, содержит образцы почти всех встречающихся типов клеточных автоматов. При правилах такого рода новое состояние клетки зависит только от числа соседей в данном состоянии, но не от их положения. Многие автоматы, основанные на таких правилах, были изучены членами группы информационной механики лаборатории вычислительной математики в Масачусетском технологическом институте. В эту группу входят Э. Фредкин, Н. Марголус, Т. Тоффоли и Дж. Вишняк.
     Одно из простейших счетных правил - это правило четности, которое приписывает клетке значение 1, если нечетное число соседей находится в состоянии 1, и значение 0 в других случаях. Любая начальная конфигурация повторяется четыре раза, затем эти четыре копии в свою очередь повторяются и т.д.
     Другий класс счетных правил - это правила "голосования", при которых центральной клетке приписывается значение 1, как только число единиц в ее окрестности превышает некоторое пороговое значение. В докладе на Лос-Аламосском симпозиуме Вишняк отметил, что по правилам такого типа получаются модели фильтрации (просачивания) и образования активных центров - очень важных явлений в физике твердого тела и других областях науки. Термином "фильтрация" обозначают образование непрерывного пути через некоторое пространство; например, когда металл распределен в изолирующей матрице, проводимость материала зависит от вероятности образования непрерывной цепочки атомов металла. Точно также передача инфекционного заболевания возможна только при наличии непрерывающейся последовательности восприимчивых индивидов. Образование активных центров - процесс, на котором основаны рост кристаллов, кипение жидкости и другие подобные явления.
     Одно из правил перехода, приводящее к фильтрации, присваивает центральной клетке значение 1 только тогда, когда значения по меньшей мере трех клеток из пяти - т.е. окрестности фон Неймана плюс центральная клетка - равны 1. Развитие фильтрации очень сильно зависит от исходной концентрации единиц. Если концентрация меньше половины, то непрерывная цепочка единиц, заполняющих схему, по-видимому, не образуется в ходе эволюции. При концентрации 1/2 и больше появляются цепочки, но вся решетка ими не заполняется; в заключительном устойчивом состоянии остаются "островки" нулей. Образование кристаллов, при котором схема прочно заполняется единицами, наблюдается в том случае, когда правило изменяется и требуется лишь две из пяти единиц в окрестности. Критическая концентрация равна 0,0822....

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

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

     Существует особый класс клеточных автоматов, называемых обратимыми. Из любого начального состояния на любое число временных шагов допускается эволюция обратимого автомата, а затем автомат останавливается и запускается обратным ходом, после чего он возвращается в свое точное начальное состояние. Конфигурации образованные типичным обратимым автоматом, качественно отличны от конфигураций, свойственных необратимому автомату. В частности, если конфигурация вначале случайна, то она и стремится остаться случайной - самоорганизующейся структуры не возникает.
     Необходимым условием обратимости является детерминированность правила перехода в обоих направлениях, вперед и назад, т.е. каждое возможное состояние окрестности должно иметь единственное предыдущее состояние и единственное последующее состояние. Игра "Жизнь" необратима, потому что предыдущий этап какого-нибудь состояния нельзя определить однозначно; например, если текущее состояние клетки - "мертва", в предыдущем поколении она могла иметь любое число "живых" соседей, отличное от трех. Систематический способ создания обратимых правил перехода был изобретен Фредкином, а позднее исследован Марголусом. Суть этого метода - заставить следующее состояние клетки зависеть от двух предыдущих состояний окрестности. Состояние в момент t+1 дается некоторой функцией окрестности в момент t минус та же функция в момент t-1. Тогда обращение производится непосредственно: состояние в момент t-1 должно даваться состоянием в момент t минус состояние в момент t+1.
...

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

На главную страницу