Обзор клеточных автоматов
Книга Т. Тоффоли и Н. Марглоуса «Машины клеточных автоматов», вышедшая в 1987 году, посвящена одной такой машине
В греческой мифологии механизмом Вселенной являлись сами боги. Они самолично тащили солнце по небу, посылали дождь и гром и вкладывали подходящие мысли в человеческие головы. Согласно более новым представлениям, мир создан завершенным, т. е. вместе с механизмом его функционирования; будучи однажды приведен в движение, он продолжает двигаться сам собой. Бог сидит снаружи и наслаждается наблюдением за ним.
Клеточные автоматы являются стилизованными, синтетическими мирами, определенными простыми правилами, подобными правилам настольной игры. Они имеют свой собственный вид материи, которая кружится в своих собственных пространстве и времени. Можно вообразить удивительное разнообразие этих миров. Можно действительно построить их и наблюдать, как они развиваются. Поскольку творцы мы неопытные, вряд ли нам удастся получить интересный мир с первой попытки; как люди, мы можем иметь разные представления о том, что делает мир интересным, или о том, что мы могли бы захотеть сделать с ним. В любом случае, после того как нам покажут мир клеточного автомата, нам захочется сотворить его самим; создав один, мы захотим попытаться создать еще один. После создания нескольких мы сможем создать мир, специально предназначенный для определенной цели, с некоторой уверенностью.
Клеточные автоматы являются дискретными динамическими системами, поведение которых полностью определяется в терминах локальных зависимостей, в значительной степени так же обстоит дело для большого класса непрерывных динамических систем, определенных уравнениями в частных производных. В этом смысле клеточные автоматы в информатике являются аналогом физического понятия «поля».
Как отмечено во введении, клеточный автомат может мыслиться как стилизованный мир. Пространство представлено равномерной сеткой, каждая ячейка которой, или клетка, содержит несколько битов данных; время идет вперед дискретными шагами, а законы мира выражаются единственным набором правил, скажем, небольшой справочной таблицей, по которой любая клетка на каждом шаге вычисляет свое новое состояние по состояниям ее близких соседей. Таким образом, законы системы являются локальными и повсюду одинаковыми.
Если задан подходящий набор правил (рецепт), то такой простой операционный механизм достаточен для поддержания целой иерархии структур и явлений. Клеточные автоматы дают полезные модели для многих исследований в естественных и вычислительных науках и комбинаторной математике; они, в частности, представляют естественный путь изучения эволюции больших физических систем. Клеточные автоматы к тому же образуют общую парадигму параллельных вычислений, подобно тому, как это делают машины Тьюринга для последовательных вычислений.
Клеточные автоматы изобретались много раз под разными названиями, и несколько отличающиеся друг от друга понятия употреблялись под одним и тем же названием. В чистой математике их можно обнаружить как один из разделов топологической динамики, в электротехнике они иногда называются итеративными массивами, а студенты младших курсов могут знать их как вид игры на домашнем компьютере.
В обычных моделях вычислений, таких как машина Тьюринга, различают структурную часть компьютера, которая фиксирована, и данные, которыми компьютер оперирует — они являются переменными. Компьютер не может оперировать своей собственной «материальной частью»; он не может себя расширять или модифицировать, строить другие компьютеры.
Клеточные автоматы ввел в конце сороковых годов Джон фон Нейман, следуя идее Станислава Улама, для того чтобы обеспечить более реалистические модели поведения сложных, пространственно протяженных систем; в клеточном автомате и объекты, которые могут быть интерпретированы как пассивные данные, и объекты, которые могут быть интерпретированы как вычислительные устройства, собираются на одного типа структурных элементов и подчиняются одним и тем же «мелкозернистым» законам; вычисление и конструирование являются просто двумя возможными типами активности.
Хотя фон Нейман был ведущим физиком в такой же степени, как и математиком, точные физические рассуждения отсутствуют в его работе по клеточным автоматам; его больше интересовало редукционистское объяснение определенных аспектов биологии. Действительно, механизмы, которые он предложил для получения самовоспроизводящихся структур на клеточном автомате, сильно напоминают открытые в следующем десятилетии механизмы, которые на самом деле наблюдаемы в биологических системах.
В конце войны, когда фон Нейман создавал один из первых электронных компьютеров, немецкий инженер К. Цусе прятался от нацистов в Австрии; там, в уединении на вершине горы, у него возникли наброски многих идей параллельной обработки, включая языки программирования высокого уровня и «вычисляющие пространства» — т. е. клеточные автоматы. К. Цусе особенно интересовался численными моделями в механике, и физические мотивы играли основную роль в его работе. К несчастью, исторические обстоятельства воспрепятствовали более широкой известности его работ в то время.
Работа фон Неймана по самовоспроизводящимся автоматам была завершена и описана А. Берксом, который сохранил активный интерес к этой области на протяжении нескольких последующих лет. Его «Очерки по клеточным автоматам» являются хорошим введением в вопросы о клеточных автоматах, которые ставились в годы формирования вычислительных наук. В той же среде, т. е. в группе компьютерной логики Университета шт. Мичиган, Дж. Голланц приступил к использованию клеточных автоматов в задачах адаптации и оптимизации; был разработан программный имитатор универсальных клеточных автоматов общего назначения.
Тем временем профессиональные математики обратили внимание на итерационные преобразования, действующие на пространственно распределенные структуры с дискретным набором состояний —
Игра Джона Конуэя «Жизнь», представленная широкой общественности ведущим рубрику математических игр и развлечений в журнале Scientific American М. Гарднером, некоторое время пользовалась популярностью, близкой к культу, и сделала выражение «клеточные автоматы» частью бытового жаргона целого поколения молодых ученых.
Вопрос о том, могут ли клеточные автоматы моделировать непосредственно законы физики, а не только общие феноменологические аспекты нашего мира, был вновь поставлен Э. Фредкином, который проявлял активность и в более традиционных областях исследований клеточных автоматов, и Т. Тоффоли. Основной целью настоящего исследования является формулировка компьютероподобных моделей в физике, сохраняющих информацию, а значит и одно из наиболее фундаментальных свойств микроскопической физики, а именно обратимость
Модели, которые явным образом сводят макроскопические явления к точно определенным микроскопическим процессам, представляют наибольший методологический интерес, потому что они обладают огромной убедительностью и ясностью. Но для того, чтобы они вообще могли что-то нам сказать, в общем случае нет иного выхода, кроме непосредственной реализации предписаний этих моделей, на деле преодолевающей пропасть между микроскопическим и макроскопическим масштабами: имитаторы клеточных автоматов, способные обновлять состояния миллионов клеток за предельно короткое время, становятся незаменимыми инструментами.
Этот подход был использован для того, чтобы обеспечить предельно простые модели обычных дифференциальных уравнений физики, таких как уравнение теплопроводности, волновое уравнение и уравнение Навье — Стокса, которые могут мыслиться как предельные случаи исключительно простых процессов комбинаторной динамики. В частности, клеточные автоматы были созданы для того, чтобы дать точные модели динамики жидкостей, которые не только будят мысль, но и конкурентоспособны, по крайней мере, в некоторых обстоятельствах, с точки зрения их вычислительной эффективности.
Бурно развивающийся раздел теории динамических систем изучает возникновение хорошо описанных коллективных явлений — упорядочение, турбулентность, хаос, нарушение симметрии, фрактальность и др. в системах, состоящих из большого числа частиц, взаимодействующих друг с другом нелинейно; цели исследований и их математический аппарат здесь больше похожи на присущие макроскопической физике и материаловедению. Клеточные автоматы обеспечивают богатую и непрерывно растущую коллекцию типичных моделей, в которых эти явления могут быть изучены относительно легко.
Итак, клеточные автоматы, по-видимому, нашли устойчивое (и все более важное) применение в качестве концептуальных и практических моделей пространственно распределенных динамических систем, для которых физические системы являются первыми и наиболее важными прототипами.