Возьмем следующее правило:
Если оба соседа клетки пребывают в том же состоянии, что и она сама, то клетка умирает в следующем поколении. В противном случае в следующем поколении она остается живой.
Это правило проиллюстрировано ниже. На рисунке показаны восемь возможных комбинаций клетки и двух ее соседей. Под каждой комбинацией изображено состояние клетки после смены поколения. В первой комбинации живая клетка находится в окружении двух живых соседних клеток. Значит, в следующем поколении она умрет. Вторая комбинация содержит живую клетку слева и мертвую справа, стало быть, средняя клетка останется в следующем поколении в живых. Если две соседние клетки одинакового цвета, внизу будет получена белая клетка. Если разного, нижняя клетка будет черной.
Чтобы понять суть этого правила, представьте себе группу людей, стоящих каждое утро в очереди на автобусной остановке, причем в одном и том же порядке. У каждого человека два соседа, по одному с каждой стороны. Пусть наше правило касается шляп: если оба ваши соседа носят шляпу, то шляпы — это слишком типичное явление, поэтому на следующий день вы шляпу не наденете. Если ни у одного из соседей шляпы нет, значит, они не в моде, поэтому на следующий день вы тоже шляпу не наденете. Однако если шляпу носит только один ваш сосед, то она еще не вышла из моды и не говорит о плохом вкусе. Данный клеточный автомат представляет собой модель изменения ежедневных предпочтений в ношении головных уборов.
Для того чтобы проиллюстрировать поведение одномерного клеточного автомата, давайте нарисуем ряд с одной живой клеткой (поколение 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 году Мэтью Кук доказал истинность предположения Вольфрама. Следовательно, теоретически единственный ряд клеток может сделать все, что и компьютер, используя всего один набор правил, определяющих, является ли клетка живой или мертвой, только на основании информации о состоянии двух ее соседей. Точно так же один ряд людей может сделать все, на что способен компьютер, воспользовавшись всего одним набором правил, определяющих, следует ли надевать шляпу или нет.
