Клеточные автоматы с более простой структурой, чем игра «Жизнь», могут демонстрировать столь же сложное поведение. Рассмотрим в качестве примера одномерный клеточный автомат: ряд клеток, в котором каждая клетка имеет только двух соседей. Кроме того, каждая клетка может быть либо живой, либо мертвой.
Возьмем следующее правило:
Если оба соседа клетки пребывают в том же состоянии, что и она сама, то клетка умирает в следующем поколении. В противном случае в следующем поколении она остается живой.
Это правило проиллюстрировано ниже. На рисунке показаны восемь возможных комбинаций клетки и двух ее соседей. Под каждой комбинацией изображено состояние клетки после смены поколения. В первой комбинации живая клетка находится в окружении двух живых соседних клеток. Значит, в следующем поколении она умрет. Вторая комбинация содержит живую клетку слева и мертвую справа, стало быть, средняя клетка останется в следующем поколении в живых. Если две соседние клетки одинакового цвета, внизу будет получена белая клетка. Если разного, нижняя клетка будет черной.
Чтобы понять суть этого правила, представьте себе группу людей, стоящих каждое утро в очереди на автобусной остановке, причем в одном и том же порядке. У каждого человека два соседа, по одному с каждой стороны. Пусть наше правило касается шляп: если оба ваши соседа носят шляпу, то шляпы — это слишком типичное явление, поэтому на следующий день вы шляпу не наденете. Если ни у одного из соседей шляпы нет, значит, они не в моде, поэтому на следующий день вы тоже шляпу не наденете. Однако если шляпу носит только один ваш сосед, то она еще не вышла из моды и не говорит о плохом вкусе. Данный клеточный автомат представляет собой модель изменения ежедневных предпочтений в ношении головных уборов.
Для того чтобы проиллюстрировать поведение одномерного клеточного автомата, давайте нарисуем ряд с одной живой клеткой (поколение 0), а затем применим указанное выше правило к каждой клетке для создания нового ряда, расположенного ниже (поколение 1). Затем применим это правило к каждой клетке данного ряда, чтобы получить следующий новый ряд (поколение 2), и т. д. На представленном рисунке показано, что при этом произойдет. (Обратите внимание, что вершина треугольника — это живая клетка первого ряда, а каждый новый ряд — следующее поколение, в отличие от игры «Жизнь», где вся сетка образует одно поколение. Я опустил на рисунке саму сетку, чтобы полученная конфигурация была видна более четко.) В итоге мы получим прекрасный математический зиккурат, известный как «треугольник Серпинского», — фрактальную структуру, состоящую из вложенных треугольников.
Существует 8 комбинаций клетки и ее соседей, а также два возможных состояния (живая или мертвая клетка), а значит, есть 28 = 256 разных наборов «генетических правил» для одномерных клеточных автоматов. Эти правила пронумерованы от 1 до 256. На представленном выше рисунке показано правило 90, порождающее упорядоченные фигуры. Другие правила, такие как правило 30, более причудливы. Это правило, а также конфигурация, которую оно порождает, начиная с одной живой клетки, проиллюстрировано на рисунке ниже. Данная конфигурация представляет собой совокупность упорядоченных и хаотичных фрагментов. Зигзагообразная корка на левой боковой поверхности демонстрирует упорядоченность. Однако по мере передвижения направо мы видим неупорядоченную бугристую поверхность, состоящую из треугольников самых разных форм и размеров.
На визитных карточках Стивена Вольфрама изображен рисунок фигуры, которую порождает правило 30. Когда я встретился с ним, он вынул такую визитку из бумажника и дал мне. Мы расположились в главном офисе его компании Wolfram Research, находящемся в городе Шампейн. У Вольфрама лицо обладающего необыкновенными математическими способностями ребенка, достигшего средних лет: круглое и бледное, с хохолками волос вокруг типичной профессорской макушки. Во время разговора он пристально всматривался куда-то, думая о чем-то своем, а его глаза за стеклами очков мерцали, подобно электронному дисплею, демонстрируя неустанную работу мозга. Вольфрам рано начал научную карьеру, опубликовав свою первую исследовательскую работу еще во время учебы в Итоне в 1970-х. Когда ему исполнилось немногим более двадцати лет, он уже работал в Институте перспективных исследований в Принстоне. Став одним из первых новообращенных в компьютерную веру, он разработал язык программирования, который лег в основу системы компьютерной алгебры Mathematica — пакета программ, позволяющих чертить кривые и решать уравнения. В настоящее время она широко используется в сфере образования и разных отраслях экономики. С 1987 года Вольфрам возглавляет компанию Wolfram Research, которая благодаря успеху системы Mathematica дала ему возможность проводить собственные научные исследования независимо от университетов.
Правило 30: его генетические законы, его эволюция после 50 поколений и эволюция после более 200 поколений
Вольфрам первым в восьмидесятых годах достаточно глубоко изучил одномерные клеточные автоматы; нумерация правил от 1 до 256 берет свое начало именно в его работе. Когда Вольфрам увидел правило 30, это было подобно удару молнии в его научной интуиции. «Это самое удивительное, с чем я когда-либо встречался в науке», — сказал он. Вольфрам был поражен тем, что такое простое правило способно сгенерировать столь сложную конфигурацию. Он внимательно проанализировал колонку, расположенную под исходной живой клеткой в первом ряду. Если взять за основу то, что живая клетка — это 1, а мертвая — 0, то эта колонка состояла из таких клеток: 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0… В этом не было никакой закономерности. К большому удивлению Вольфрама, стандартные статистические тесты показали, что это абсолютно произвольная последовательность. Правило 30 полностью детерминировано, однако конфигурация ячеек в центральном столбце настолько непредсказуема, что ее невозможно отличить от последовательного подбрасывания монеты. (Вольфрам запатентовал правило 30 как генератор случайных чисел и применил его в системе Mathematica.)
Внимание Вольфрама привлекло еще одно правило — правило 110. Оно формировало сетку ячеек, которая тоже представляла собой совокупность регулярных и случайных фигур. Вольфрам предположил, что данного уровня сложности достаточно для такой же имитации работы компьютера, на которую способна игра «Жизнь». В 2004 году Мэтью Кук доказал истинность предположения Вольфрама. Следовательно, теоретически единственный ряд клеток может сделать все, что и компьютер, используя всего один набор правил, определяющих, является ли клетка живой или мертвой, только на основании информации о состоянии двух ее соседей. Точно так же один ряд людей может сделать все, на что способен компьютер, воспользовавшись всего одним набором правил, определяющих, следует ли надевать шляпу или нет.
Клеточные автоматы — это дискретные математические модели, в которых фиксированные локальные правила генерируют неожиданно сложное поведение в более крупном масштабе. Вольфрам — один из главных сторонников той точки зрения, что клеточные автоматы — не только увлекательная математическая игра, но и способ объяснить сложность физического мира. Мысли Вольфрама по этому поводу изложены в книге A New Kind of Science («Новый вид науки»), которую он опубликовал за свой счет в 2002 году [9]. В частности, в ней Вольфрам утверждает, что информация, полученная благодаря анализу правила 30, открывает новую научную парадигму. Возьмем в качестве примера раковину ядовитой парчовой улитки, изображенную на рисунке ниже. Общепринятое представление об эволюции объясняет такой рисунок как результат естественного отбора. Но посмотрите на иллюстрацию правила 30! «Я считаю, что это просто удивительно, — говорит Вольфрам. — Достаточно всего лишь наугад выбрать эти простые [правила клеточных автоматов] — и вы получите нечто подобное [рисунку на этой раковине]».
Раковина парчовой улитки, или текстильного конуса
© iStock.com/busypix
Однако Вольфрам на этом не останавливается, поскольку убежден, что на базовом уровне Вселенная представляет собой клеточный автомат. Другими словами, он считает, что структура Вселенной аналогична решетке в игре «Жизнь», но существует вне пространства и времени. Следовательно, то, что происходит с вами сейчас, когда вы читаете эту книгу, — это энное поколение исходной конфигурации клеток, прошедших процесс эволюции в соответствии с небольшим набором локальных правил. Вольфрам поставил перед собой цель найти эти правила. «Если окажется, что они сводятся к трем строкам программы, а мы так и не начнем искать их в текущем столетии, это будет весьма досадно», — сетует он.
