Клеточные автоматы. Часть I. Обзор.

В этой части мы исследуем выразительные возможности (в плане синтеза систем) конкретного набора средств, а именно законов, структур и явлений, поддерживаемых клеточными автоматами, чтобы эти системы стали реально доступными для экспериментирования посредством использования машины клеточных автоматов с адекватными характеристиками. Данная глава является введением в клеточные автоматы и включает краткие исторические замечания и ссылки.

КЛЕТОЧНЫЕ АВТОМАТЫ

То, что сделано однажды, может быть сделано вновь.

Традиционная формула, оправдывающая использование математической индукции

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

В этой части мы исследуем выразительные возможности (в плане синтеза систем) конкретного набора средств, а именно законов, структур и явлений, поддерживаемых клеточными автоматами, чтобы эти системы стали реально доступными для экспериментирования посредством использования машины клеточных автоматов с адекватными характеристиками. Данная глава является введением в клеточные автоматы и включает краткие исторические замечания и ссылки.

1.1. Основные понятия

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

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

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

1.2. Мультипликация вручную

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

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

Выберите клетку и посмотрите на область 3x3, центром которой она является, ее "окрестность". Если вы увидите в этой области (на листе,находящемся прямо под этим) в точности три черные клетки, пометьте слегка вашу клетку карандашом; также пометьте эту клетку, если она находится непосредственно над черной клеткой.

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

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

Рис. 1.1. Несколько кадров типичной последовательности INKSPOT.

Масштаб таков, что отдельные клетки едва различимы. Это в сущности все, что нужно для клеточного автомата. Измените начальные условия, и вы получите несколько иную историю. Измените рецепт, и вы получите новое множество "динамических законов новый мир. Вы можете использовать сетку иной формы (скажем, гексагональную), или, может быть, трехмерную. Рецепт может относиться к окрестности с другой формой и размером, чем окрестность 3x3, и может включать чернила более чем одного цвета; однако как число соседей, так и число цветов (т. е. число возможных состояний клетки) должны быть конечными, потому что мы хотим, чтобы обновление состояния клетки требовало конечного числа операций.

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

1.3. Машины клеточных автоматов

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

Чтобы синтезировать структуры значительной сложности, необходимо использовать большое количество клеток, а для того чтобы эти структуры взаимодействовали друг с другом и существенно эволюционировали, необходимо позволить автомату работать на протяжении большого количества шагов. Для элементарных научных проблем удовлетворительная экспериментальная работа может потребовать вычисления миллиардов событий (событием является обновление одной клетки); для более сложных приложений может быть желательным значение в тысячу или миллион раз больше (т. е. 1012-1015 событий); в действительности пределы устанавливаются тем, сколько мы можем выполнить, а не тем, сколько хотим.

В связи с этим обычные компьютеры здесь малопригодны. Моделирование события в клеточном автомате может потребовать около тридцати машинных операций, содержащих каждая несколько машинных циклов, скажем 10 мс на быстродействующем компьютере. Для того чтобы вычислить 1013 событий, при таком подходе потребовалось бы несколько лет!

С другой стороны, структура клеточного автомата идеально пригодна для реализации на ЭВМ, обладающей высокой степенью параллелизма, локальными и единообразными взаимосвязями;

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

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

1.4. Исторические замечания и литература

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

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

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

В конце войны, когда фон Нейман создавал один из первых электронных компьютеров, немецкий инженер К. Цусе прятался от нацистов в Австрии; там, в уединении на вершине горы, у него возникли наброски многих идей параллельной обработки, включая языки программирования высокого уровня и "вычисляющие пространства"  т. е. клеточные автоматы. К. Цусе особенно интересовался численными моделями в механике, и физические мотивы играли основную роль в его работе. К несчастью, исторические обстоятельства воспрепятствовали более широкой известности его работ в то время. Работа фон Неймана по самовоспроизводящимся автоматам была завершена и описана А. Берксом, который сохранил активный интерес к этой области на протяжении нескольких последующих лет. Его "Очерки по клеточным автоматам"  являются хорошим введением в вопросы о клеточных автоматах, которые ставились в годы формирования вычислительных наук. В той же среде, т. е. в группе компьютерной логики Университета шт. Мичиган, Дж. Голланд приступил к использованию клеточных автоматов в задачах адаптации и оптимизации; был разработан программный имитатор универсальных клеточных автоматов общего назначения. Месяцы работы с этим имитатором убедили одного из авторов (Тоффоли) в необходимости более непосредственной и эффективной аппаратной реализации машины клеточных автоматов.

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

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

Игра Джона Конвея "жизнь", представленная широкой общественности ведущим рубрику математических игр и развлечений в журнале "Сайентифик Америкен" М. Гарднером, некоторое время пользовалась популярностью, близкой к культу, и сделала выражение "клеточные автоматы" частью бытового жаргона целого поколения молодых ученых.

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

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

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

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

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