Муравей Лэнгтона
Годы идут, и становится все более очевидным, что традиционные методы математического моделирования уже не справляются с задачами, которые ставит перед собой человечество: моделированием глобальной финансовой системы, динамики экосистем, роли генов в росте и развитии живых организмов. Во многие из этих систем входит гигантское количество действующих «лиц» — людей, компаний, организмов, генов, взаимодействующих между собой. Нередко эти взаимодействия можно смоделировать при помощи достаточно простых правил. В последние 30 лет получил развитие новый тип модели, который пытается разобраться с поведением подобных систем, что называется, «в лоб». К примеру, чтобы понять, как 100 000 человек будут вести себя на стадионе, мы не станем усреднять их и превращать в своего рода человеческую жидкость, течение которой затем следует рассматривать. Нет, мы строим компьютерную модель из 100 000 отдельных модулей, накладываем на них подходящие ограничения, устанавливаем правила и запускаем процесс моделирования, чтобы посмотреть, что будет делать эта компьютерная толпа. Такого рода модели в математике называют сложными системами.
Чтобы дать вам некоторое представление об этой новой и очень интересной области математики, я опишу одну из простейших сложных систем и объясню, почему мы не понимаем ее до конца. Эта система называется муравьем Лэнгтона. Кристофер Лэнгтон был одним из первых сотрудников Института Санта-Фе, который основали в 1984 г. физики Джордж Коуэн, Марри Гелл-Ман и другие для развития теории и приложений сложных систем. Лэнгтон придумал своего муравья в 1986 г. Технически это клеточный автомат, система клеток квадратной решетки, состояния которых обозначаются цветом. На каждом временно́м шаге цвет каждой клетки изменяется в соответствии с цветом соседних с ней клеток.
Правила просты до нелепости. Муравей живет на бесконечной квадратной решетке из клеток, и первоначально все они белые. Он всегда носит с собой неиссякаемый горшочек с черной краской и такой же горшочек с белой краской. Он может идти на север, на восток, на юг или на запад. Из соображений симметрии скажем, что первый шаг он делает на север. В каждый момент времени муравей смотрит на цвет клетки, в которой оказался, и перекрашивает ее из черной в белую или из белой в черную. Если клетка была белой, то после перекрашивания муравей поворачивает на 90° направо и делает один шаг вперед. Если клетка была черной, то он поворачивает на 90° налево и делает то же самое. И так до бесконечности. Если вы смоделируете поведение муравья, то сначала он будет рисовать простой симметричный узор из белых и черных квадратов. Время от времени он возвращается на клетку, где уже был, но петля при этом не замыкается, потому что цвет клетки изменился, и муравей повернет в другую сторону. Моделирование продолжается, и рисунок становится хаотичным и случайным. При этом в нем невозможно различить никаких закономерностей: в основе своей это просто беспорядок. На этой стадии можно подумать (и вполне здраво), что такое хаотичное поведение будет продолжаться бесконечно. В конце концов, вернувшись в хаотично раскрашенный регион, муравей непременно сделает серию хаотичных шагов. Если вы будете продолжать моделирование, то следующие примерно 10 000 шагов подтвердят ваше предположение. Однако затем, если вы будете настойчивы, проявится закономерность. В движениях муравья возникнет повторяющийся цикл из 104 шагов, в результате которого он проходит две клетки по диагонали. После этого он будет двигаться, прорисовывая широкую диагональную полосу из черных и белых клеток, которую иногда называют магистралью, и так до бесконечности (см. рис. 49).
Все описанное до сих пор может быть доказано по всей строгости просто последовательным перебором муравьиных шагов. Это будет достаточно длинное доказательство — список из 10 000 шагов, — но все же доказательство. Но математика системы станет более интересной, если мы зададимся чуть более общим вопросом. Что если еще до начала движения муравья мы перекрасим некоторое конечное число клеток решетки в черный цвет? Мы можем выбрать для этого любые клетки: это может быть случайный набор, черный квадрат или Мона Лиза. Их может быть миллион, или миллиард, или еще больше, но не бесконечное количество. Что произойдет?
Обычное движение муравья резко меняется при встрече с любой из новых черных клеток. Он может долго бродить окрест, рисуя сложные орнаменты и раз за разом перерисовывая их заново… Но во всех до сих пор предпринятых попытках, какой бы ни была первоначальная конфигурация, в конце концов муравей непременно принимался за строительство магистрали при помощи все того же 104-шагового цикла. Всегда ли это происходит? Является ли магистраль единственным «аттрактором» движения муравья? Никто не знает. Это одна из фундаментальных нерешенных задач теории сложности. Максимум, что нам известно, — это то, что, какой бы ни была первоначальная конфигурация черных клеток, муравей не останется навечно в пределах ограниченной области поля.