Клеточные автоматы (обзор Гарднера)

Книга Мартина Гарднера «Математические досуги» вышла в 1972 году. Её последняя глава посвящена игре «Жизнь», в которой также есть небольшой обзор теории клеточных автоматов. Многие сведения уже устарели. Например, было доказано, что в «Жизни» существует универсальный конструктор (машина Тьюринга), а в 2002 году универсальный конструктор был построен. Тем не менее, обзор всё равно опубликован, так как он может быть полезен при первом знакомстве с этой областью.

Игра Конуэя «Жизнь» вызвала огромный интерес у ученых, занимающихся разработкой проблем, связанных с использованием компьютеров. Поэтому остановимся на некоторых основных фактах развития «теории клеточных автоматов» — области науки, занимающейся изучением игр, аналогичных конуэевской «Жизни». Всё началось с 1950 года, когда Джон фон Нейман поставил перед собой задачу доказать возможность существования самовоспроизводящихся автоматов. Если такую машину снабдить надлежащими инструкциями, она построит точную копию самой себя. В свою очередь две машины («мама» и «дочь») смогут построить ещё две; четыре машины построят четыре и т. д. Фон Нейман впервые доказал возможность существования таких машин с помощью «кинематических» моделей машины, способной передвигаться по складу запасных частей, отбирать необходимые детали и собирать новые машины, как две капли воды похожие на неё. Позднее, воспользовавшись идеей, высказанной его другом Станиславом Уламом, фон Нейман дал более изящное и абстрактное доказательство возможности существования самовоспроизводящихся машин.

Новое доказательство фон Неймана существенно использовало понятие «однородного клеточного пространства», эквивалентного бесконечной шахматной доске. Каждая клетка такого пространства может находиться в любом, но конечном числе «состояний», в том числе в состоянии «покоя» (называемом также пустым, или нулевым, состоянием). На состояние любой клетки оказывает влияние конечное число соседних клеток. Во времени состояния пространства изменяются дискретно, в соответствии с «правилами перехода», которые необходимо применять одновременно ко всем клеткам. Клетки соответствуют основным частям автомата с конечным числом состояний, а конфигурация из «живых» клеток — идеализированной модели автомата. Именно в таком клеточном пространстве и развёртывается действие придуманной Конуэем игры «Жизнь». Соседними для каждой клетки в «Жизни» считаются восемь непосредственно окружающих её клеток. Клетка может находиться в двух состояниях (либо на ней стоит фишка, либо клетка пуста). Правила перехода определяются генетическими законами Конуэя (рождение, гибель и выживание). Фон Нейман, применяя правила перехода к пространству, каждая клетка (или ячейка) которого могла находиться в 29 состояниях и имела четыре соседние клетки (примыкающие к данной по вертикали и горизонтали), доказал существование самовоспроизводящейся конфигурации, состоящей примерно из 200 000 клеток.

Причина столь чудовищных размеров конфигурации объяснялась тем, что фон Нейман намеревался применить своё доказательство к реальным автоматам и специально подобрал клеточное пространство, способное имитировать машину Тьюринга — идеальный автомат, названный в честь изобретателя, английского математика А. М. Тьюринга, и способный производить любые вычисления. «Погрузив» универсальную машину Тьюринга в созданную им конфигурацию, фон Нейман получил возможность создать «универсальный конструктор», способный построить любую конфигурацию в пустых клетках пространства, в том числе и точную копию самого себя. За время, прошедшее после смерти фон Неймана (последовавшей в 1957 году), предложенное им доказательство существования самовоспроизводящейся системы (речь идет именно о «чистом» доказательстве существования, а не о построении используемой в доказательстве фон Неймана конфигурации) удалось значительно упростить. Рекорд по простоте установило доказательство, найденное выпускником инженерного факультета Массачусетского технологического института Эдвином Р. Бэнксом. В нём используются «ячейки», которые могут находиться лишь в 4 состояниях.

Самовоспроизведения в тривиальном смысле — без использования конфигураций, включающих в себя машину Тьюринга, — добиться легко. Удивительно простой пример «тривиальной» самовоспроизводящейся системы предложил около 10 лет назад Эдвард Фредкин. В этой системе ячейки могут находиться лишь в двух состояниях, каждая из них, как и в примере фон Неймана, имеет четырёх соседей, а правила перехода сводятся к следующим. Каждая клетка, имеющая в момент времени t четное число (0, 2, 4, ...) живых соседей, в момент времени t + 1 становится пустой (то есть переходит в нулевое состояние или, если она уже находилась в нулевом состоянии, остаётся в нём). Каждая клетка, имеющая в момент времени t нечетное число (1, 3, ...) соседей, в момент времени t + 1 становится живой (то есть переходит в ненулевое состояние или сохраняет его, если она уже в нём находилась). Через 2n ходов (число n зависит от выбора конфигурации) любая конфигурация живых клеток в таком пространстве воспроизведет себя четыре раза: одна копия расположится справа, другая — слева, третья — сверху, четвёртая — снизу от того (уже пустого) места, где находилась начальная конфигурация. Новая конфигурация через 2n шагов снова размножится (с коэффициентом воспроизводства, равным 4) и т. д. Число копий увеличивается в  геометрической прогрессии 1, 4, 16, 64... На рисунке показаны полтора цикла размножения тримино в форме прямого угла.

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

Множество автоматов такого рода, отличающихся друг от друга схемой примыкания соседних клеток, числом состояний и правилами перехода, исследовал С. Улам. В опубликованной им (совместно с Робертом Г. Шрандтом) в 1967 году статье «О рекурсивно определённых геометрических объектах и схемах роста» Улам описал несколько игр. На рисунке показано сорок пятое поколение организма, родившегося из одной-единственной фишки, стоявшей в центральной клетке.

Как и в игре Конуэя, клетки в игре Улама могут находиться в двух состояниях, но соседними считаются клетки, примыкающие к данной лишь по вертикали, но не по диагонали («соседи» в смысле фон Неймана). Рождение фишки происходит на клетке, имеющей одного и только одного соседа, а все клетки поколения n погибают после рождения поколения n + 2. Иначе говоря, на любом этапе эволюции выживают лишь два последних поколения. На рисунке черными изображены новорожденные клетки (их 444). Зеленые клетки предыдущего поколения — их 404 — исчезнут на следующем ходу. Обратите внимание на характерную деталь, которую Улам назвал «обглоданной костью». Улам проводил эксперименты и с такими играми, в которых две конфигурация могли расти до тех пор, пока они не сталкивались. В следующей за столкновением «битве» одной стороне иногда удавалось одержать верх над другой, а иногда обе армии исчезали. Улам рассмотрел также игры на трёхмерных досках — кубических «паркетах», заполняющих всё пространство. Основные результаты Улама собраны в его статьях, опубликованных в сборнике «Очерки теории клеточных автоматов» (Essays on Cellular Automata, University of Illinois Press, 1970, ed. by Arthur W. Burks).

Аналогичные игры можно вести и на бесконечных досках, клетки которых имеют форму равносторонних треугольников и правильных шестиугольников. Несмотря на сильное внешнее отличие, по существу эти игры не вносят ничего нового, и с помощью подходящего определения «соседних» клеток их всегда можно свести к эквивалентным играм на обычной доске с клетками в форме квадратов. Соседними могут быть не только клетки, имеющие общие стороны или вершины. Например, в шахматах для клетки, на которой стоит конь, соседними (то есть влияющими на её состояние) считаются все клетки, на которые можно пойти конём или на которых стоят угрожающие ему фигуры. Как заметил Беркс, такие игры, как шахматы, шашки и го, допустимо рассматривать как клеточные автоматы со сложными окрестностями каждой клетки (окрестностью называется совокупность соседей) и правилами перехода. Противники, делая очередной ход, выбирают среди множества допустимых состояний то, которое должно привести их к определённому конечному состоянию — выигрышу.

Среди наиболее значительных вкладов в теорию клеточных автоматов наибольшую известность получил предложенный Эдвардом Ф. Муром способ доказательства существования конфигураций, которые Джон У. Тьюки назвал «садами Эдема». Эти конфигурации не могут возникать в процессе игры, поскольку никакая конфигурация отличного от них типа не может их породить. «Сады Эдема» должны быть заданы с самого начала — в нулевом поколении. Поскольку конфигурации такого типа не имеют «предшественников», они не могут быть самовоспроизводящимися. Подробно метод Мура изложен в его популярной статье «Математика в биологических науках» (Scintific American, сентябрь 1964). Более строгое изложение дано в уже упоминавшемся сборнике под редакцией Беркса.

Алви Р. Смит обнаружил простой способ, позволяющий применять метод Мура к игре Конуэя. Из теоремы Мура следует, что конфигурация типа «садов Эдема» должна возникать в игре Конуэя. К сожалению, доказательство теоремы ничего не говорит о том, как найти «сады Эдема», и они до сих пор не обнаружены. Конфигурация типа «садов Эдема» может оказаться и простой, и чрезвычайно сложной. С помощью одной из выведенных Муром формул Смит сумел доказать, что такую конфигурацию всегда можно заключить в квадрат со стороной в 10 миллиардов клеток, но и этот результат ненамного облегчает поиски конфигурации.

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

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