Готовый перевод Richard Dawkins The Oxford Book of Modern Science Writing / Ричард Докинз Оксфордская книга публикаций современной науки: Martin Gardner THE FANTASTIC COMBINATIONS OF JOHN CONWAY’S NEW SOLITAIRE GAME ‘LIFE’ / Мартин Гарднер "Фантастические комбинации Джона Конвея новый пасьянс «Жизнь»

Мартин Гарднер

"Фантастические комбинации Джона Конвея новый пасьянс «Жизнь»

Математик Джон Конвей придумал игру, к несчастью названную Жизнью, которая должно быть внесла неожиданно плодотворный вклад, когда либо сделанный математиком в умы не-математиков.

Кто бы мог подумать, что столько всего возникнет (используя специальный термин) из таких простых правил? Этот урок не пропадет даром для людей, задумывающихся о том, как мог возникнуть такой сложный и прекрасный мир, который нас окружает, весь неуправляемый с простыми первичными началами (необычайно изобретательный компьюторщик Стивен Вольфрам написал гигантскую книгу, "новый вид науки" на эту тему).

Описание игры Конвея, которое я выбрал принадлежит Мартину Гарднеру, чьи математические головоломки, игры, задачки любимы поколениями читателей журнала "В мире науки" и принесли ему горячих поклонников по всему миру.

Таим образом здесь колонка Гарднера из октябрьского выпуска 1970 г., заполненная задачками для читателей.■

Большинство работ Джона Хортона Конвея математика колледжа Гонвилл и Киз кембриджского универтитета принадлежит к чистой математике.

Например, в 1967г. Он открыл новую группу - некоторые называют ее "созвездие конвея" - туда включены все , кроме двух известных на тот момент спорадических групп.

(Они называются спорадическими поскольку не подходят не по какую классификацию.)

Это прорыв, который нашел прекрасное отражение как в теории групп, так и в теории чисел.

Это тесно связано с более ранним открытием Джона Лича об наиболее плотной упаковке сфер в 24-мерном пространстве, где каждая сфера соприкасается с 196560 другими сферами.

Как высказался Конвей "там много места".

В дополнение к таким серьезным работам Конвей также занимался развлекательной математикой.

Несмотря на то, что он был весьма продуктивен на этом поприще, он редко публиковал свои открытия.

Одно исключение его работа "лоскутное одеяло миссис Перкинс", задача сечений, обсужденная в сентябрьском выпуске 1966г "Математических игр".

Моя заметка для июльского выпуска 1967 г. была об игре Рассада. Это топологическая игра с карандашем и бумагой, придуманная Конвеем и Патерсоном. Конвей там был упомянут еще несколько раз.

В этом месяце мы рассмотрим последние детище Конвея, фантастическую развлекательную игру, которую он назвал "жизнь".

Из-за сходства с подъемами, падениями, изменениями как в сообществе живых организмов, игра принадлежит к растущему классу так называемых "симуляций" - игр, которые напоминают процессы реальной жизни.

Для игры «Жизнь» вам может понадобиться большая доска, разграфлённая на клетки, и много плоских фишек двух цветов (например, просто несколько наборов обычных шашек небольшого диаметра или пуговиц двух цветов).

Можно рисовать ходы и на бумаге. Но значительно проще воспользоваться программами, моделирующими эту игру на компьютере.

Основная идея «Жизни» состоит в том, чтобы, начав с какого-нибудь простого расположения фишек (организмов), расставленных по одной в клетке, проследить за эволюцией исходной позиции под действием «генетических законов» Конуэя, которые управляют рождением, гибелью и выживанием фишек.

Конуэй тщательно подбирал свои правила, и долго проверял их «на практике», добиваясь, чтобы они по возможности удовлетворяли трём условиям:

1.Не должно быть ни одной исходной конфигурации, для которой существовало бы простое доказательство возможности неограниченного роста популяции.

2.В то же время должны существовать такие начальные конфигурации, которые заведомо обладают способностью беспредельно развиваться.

3.Должны существовать простые начальные конфигурации, которые в течение значительного промежутка времени растут, претерпевают разнообразные изменения и заканчивают свою эволюцию одним из следующих трёх способов: полностью исчезают (либо из-за перенаселённости, то есть слишком большой плотности фишек, либо наоборот, из-за разрежённости фишек, образующих конфигурацию), переходят в устойчивую конфигурацию и перестают изменяться вообще или же, наконец, выходят на колебательный режим, то есть бесконечный цикл превращений с определенным периодом.

Короче говоря, правила должны быть такими, чтобы поведение популяции было непредсказуемым.

Генетические законы Конуэя удивительно просты.

Прежде, чем мы их сформулируем, обратим внимание на то, что каждую клетку доски (доска считается бесконечной), окружают восемь соседних клеток: четыре имеют с ней общие стороны, четыре другие — общие вершины.

Правила игры (генетические законы) сводятся к следующему:

1. Выживание. Каждая фишка, имеющая вокруг себя две или три соседние фишки, выживает и переходит в следующее поколение.

2. Гибель. Каждая фишка, у которой больше трёх соседей, погибает, то есть снимается с доски из-за перенаселённости.

Каждая фишка, вокруг которой свободны все соседние клетки или же занята всего одна клетка, погибает от одиночества.

3. Рождение. Если число фишек, с которыми граничат какая-нибудь пустая клетка, в точности равно трём (не больше и не меньше), то на этой клетке происходит рождение нового «организма», то есть следующим ходом на неё ставится одна фишка.

Важно понять, что рождение и гибель всех «организмов» происходит одновременно.

Вместе взятые, они образуют одно поколение или, как мы будем говорить, один ход в эволюции начальной конфигурации.

Ходы Конуэй рекомендует делать следующим образом:

1.начать с конфигурации, целиком состоящей из черных фишек;

2.определить, какие фишки должны погибнуть, и положить на каждую из обреченных фишек по одной черной фишке;

3.найти все свободные клетки, на которых должны произойти акты рождения, и на каждую из них поставить по одной фишке белого цвета;

4.выполнив все эти указания, ещё раз внимательно проверить, не сделано ли каких-либо ошибок, затем снять с доски все погибшие фишки (то есть столбики из двух фишек), а всех новорожденных (белые фишки) заменить черными фишками.

Проделав все операции, вытекающие из генетических законов, вы получите первое поколение в эволюции первоначальной конфигурации.

Аналогичным образом получаются и все последующие поколения.

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

Допустить ошибку, в особенности, если вы играете впервые, очень легко.

Со временем вы будете делать всё меньше и меньше ошибок, однако даже опытные игроки должны очень внимательно проверять каждое новое поколение перед тем, как снимать с доски погибшие фишки и заменять чёрными фишками новорожденные белые.

Начав игру, вы сразу заметите, что многие популяции непрестанно претерпевают необычные, нередко очень красивые и всегда неожиданные изменения.

Иногда первоначальная колония организмов постепенно вымирает, то есть все фишки исчезают, однако произойти это может не сразу, а лишь после того, как сменится очень много поколений.

В большинстве своем исходные конфигурации либо переходят в устойчивые (любители спокойной жизни), и перестают изменяться, либо навсегда переходят в колебательный режим. Конфигурации, не обладавшие в начале игры симметрией, обнаруживают тенденцию к переходу в симметричные формы.

Обретённые свойства симметрии в процессе дальнейшей эволюции не утрачиваются (генетические законы не зависят от расположения фишек на доске), симметрия конфигурации может лишь обогащаться.

Конуэй высказал гипотезу, согласно которой не существует ни одной начальной конфигурации, способной беспредельно расти.

Иначе говоря, любая конфигурация, состоящая из конечного числа фишек, не может перейти в конфигурацию, в которой число фишек превосходило бы некий конечный верхний предел.

Это, наверное, одна из самых глубоких и самых сложных задач, возникающих в «Жизни».

Когда описание игры появилось в октябрьском номере журнала Scientific American за 1970 год, Конуэй предлагал премию в 50$ тому, кто до конца года первым докажет или опровергнет его гипотезу.

Одним из способов опровергнуть это была бы находка такой конфигурации, которая постоянно добавляет фишки на поле: "ружье" (конфигурация, которая периодически выстреливает движущимися объектами, такими как "глиссер", ниже объясним что это такое или "паровоз" (конфигурация, которая движется и оставляет позади себя след "дыма").

Я отправлю все доказательства Конвею, как главному арбитру,

Теперь посмотрим, что происходит с некоторыми простыми конфигурациями.

Одна фишка, а также любая пара фишек, где бы они ни стояли, очевидно, погибают после первого же хода.

Исходная конфигурация из трёх фишек (будем называть её триплетом), как правило, погибает. Выживает триплет лишь в том случае, если, по крайней мере, одна фишка граничит с двумя занятыми клетками.

Пять триплетов, не погибающих на первом же ходу, изображены на рисунке 13.

(Как расположены триплеты на плоскости — прямо, «вверх ногами» или косо, не существенно.)

Первые три конфигурации на втором ходу погибают.

Относительно третьей конфигурации заметим, что любой диагональный ряд фишек, каким бы длинным он ни был, с каждым ходом теряет стоящие на его концах фишки и, в конце концов, совсем исчезает.

Рис. 13. Судьба пяти триплетов в "жизни".

Скорость, с которой шахматный король перемещается по доске в любом направлении, Конуэй называет скоростью света. (Причины этого станут понятны в дальнейшем.)

Пользуясь этой терминологией, можно сказать, что диагональный ряд фишек распадается с концов со скоростью света.

Четвёртая конфигурация на втором ходу переходит в устойчивую конфигурацию — блок размером 2×2.

Пятая конфигурация служит простейшим примером так называемых флип-флопов (кувыркающихся конфигураций, возвращающихся в исходное состояние через каждые два хода).

Она попеременно превращается то в вертикальный, то в горизонтальный ряд из трёх фишек.

Конуэй называет этот триплет мигалкой.

Рассмотрим эволюцию пяти тетрамино (четыре клетки, из которых состоит элемент тетрамино, связаны между собой ходом ладьи). Рис.14.

Как мы уже видели, первый квадрат относится к категории любителей спокойной жизни. Вторая и третья конфигурация после второго хода переходит в устойчивую конфигурацию, называемую ульем. Ульи в игре возникают часто. Четвёртое тетрамино также превращается в улей, но на третьем ходу.
Особый интерес вызывает ещё одно тетрамино, которое после девятого хода распадается на четыре отдельные мигалки (вся конфигурация носит название навигационные огни).

Навигационные огни относятся к разряду флип-флопов и возникают довольно часто.

На рисунке 15 отображены 12 наиболее распространенных форм натюрмортов.

Двенадцать наиболее часто встречающихся конфигураций из числа любителей спокойной жизни (то есть устойчивых конфигураций) приведены на рисунке 15. Пасека является устойчивой конфигурацией из четырёх ульев, в которую после 14 ходов переходит горизонтальный ряд из 7 фишек. Квадрат размером 5×5 после первого же хода переходит в конфигурацию, которая возникает лишь на четвёртом этапе эволюции семиклеточного ряда. Поэтому квадрат 5×5 становится пасекой после 11 ходов.Вы можете самостоятельно поэкспериментировать с двенадцатью фигурами пентамино (фигуры, состоящие из пяти клеток, связанных между собой так, что их можно обойти ходом ладьи) и посмотреть, во что они превращаются. Оказывается, что пять из них на пятом ходу погибают, две быстро переходят в устойчивые конфигурации из семи клеток, а четыре после небольшого числа ходов превращаются в навигационные огни.Единственным исключением является элемент пентамино, имеющий форму буквы r, превращения которого заканчиваются не столь быстро (превращения конфигурации считаются исчерпанными, если та исчезает, переходит в устойчивую конфигурацию или начинает периодически пульсировать).

Рисунок 14. Истории жизни пяти тетрамино.

Рисунок 15. Наиболее распространенные стабильные формы.

Их судьба пока неизвестна.

Конуэй проследил развитие r-образного пентамино (рис 16) вплоть до четыреста шестидесятого хода, после которого конфигурация распалась на множество планеров.

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

После сорока восьми ходов r-образное пентамино превратилось в конфигурацию, левая часть которой состоит из семи фишек, а правая — из фишек, заполняющих две симметричные области. Если бы левой части не было, то эти области развивались бы в пасеку с четырьмя ульями и навигационные огни.

Возмущение, вносимое левой частью, приводит к тому, что пасека быстро вгрызается в навигационные огни и образующие их четыре мигалки гаснут одна за другой, оставляя после себя на доске „нечто бесформенное“».

Изучая эволюцию долгожителей наподобие r-пентамино, Конуэй иногда пользуется вычислительной машиной, устройство которой позволяет выводить выходные данные на экран и таким образом наблюдать все изменения, происходящие на игровом поле.

Без программы, которую написали М. Дж. Т. Гай и С. Р. Бурн, многие особенности игры были бы обнаружены лишь с большим трудом.

Эволюция r-пентамино была прослежена до конца с помощью компьютерных вычислений. Она завершается лишь после тысяча сто третьего хода. Шесть возникших на доске планеров удаляются от центра на всё большее и большее расстояние (находятся за пределами рисунка), и, в конце концов, вокруг бывшего пентамино (показано красным цветом) остаются четыре мигалки, один корабль, одна лодка, один каравай, четыре улья и восемь блоков.

Следующие три фигуры были исследованы Симоном Нортоном.

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

В противоположность букве „Н“, эволюция которой заканчивается быстро, ворота оказываются весьма долгоживущей конфигурацией.

Лишь после 173 ходов она распадается на 5 мигалок, 6 блоков и 2 пруда.

Конуэй проследил эволюцию всех элементов гексамино и всех элементов гептамино, за исключением семи.

Одним из самых замечательных открытий Конуэя следует считать конфигурацию из 5 фишек — планер. (Рис. 17)

После второго хода планер немного сдвигается и отражается относительно диагонали.

В геометрии такой тип симметрии называется скользящей симметрией, отсюда и название фигуры (По-английски планер называется glider, от glide — скользить. — Прим. перев.).

В результате двух последующих ходов планер «выходит из пике», ложится на прежний курс и сдвигается на одну клетку вправо и на одну клетку вниз относительно начальной позиции.

Выше уже писалось, что скорость шахматного короля в «Жизни» принято называть скоростью света.

Выбор Конуэя пал именно на этот термин из-за того, что в изобретённой им игре большие скорости просто не достигаются.

Ни одна конфигурация не воспроизводит себя достаточно быстро, чтобы двигаться с такой скоростью.

Рисунок 16. Пентомино R (а) и упражнения для читателя.

Рисунок 17. Планер

Конуэй доказал, что максимальная скорость по диагонали составляет одну четверть скорости света.

Поскольку планер переходит сам в себя после четырех ходов и при этом опускается на одну клетку по диагонали, то говорят, что он скользит по полю со скоростью, равной одной четвёртой скорости света.

Конуэй также показал, что скорость любой конечной фигуры, перемещающейся по вертикали или по горизонтали на свободные клетки, не может превышать половину скорости света.

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

Восьмёрка — это периодически восстанавливающая себя конфигурация, открытие которой принадлежит Нортону. Она не только по форме напоминает восьмёрку, но и имеет период, равный восьми.

Следующая конфигурация называется пульсар СР 48-56-72. Она также периодически восстанавливает себя через каждые три хода.

Начальное состояние пульсара образовано 48 фишками; на втором этапе число фишек возрастает до 56, а на третьем — до 72, после чего пульсар снова возвращается в исходное состояние, а число фишек понижается до 48.

Пульсар образуется после 32 ходов из элемента гептамино, имеющего вид растянутой буквы П: горизонтального ряда из пяти фишек, у которого под первой и последней фишкой располагается ещё по одной фишке.

Конуэй исследовал эволюцию всех горизонтальных рядов из n фишек вплоть до n = 20.

Мы уже знаем, что происходит при n < 5.

Рисунок 18. Три замечательных образца, один стабильный и два колеблющиеся.

Пятиклеточный ряд переходит в навигационные огни, шестиклеточный исчезает, из семиклеточного получается пасека, из восьмиклеточного — четыре улья и четыре блока, девятиклеточный ряд превращается в два комплекта навигационных огней, а ряд, состоящий из десяти фишек, переходит в пентадекатлон — периодически воспроизводящую себя конфигурацию с периодом, равным пятнадцати.

Ряд из одиннадцати фишек эволюционирует, превращаясь в две мигалки; двенадцатиклеточный ряд переходит в два улья, тринадцатиклеточный — в две мигалки. Если ряд состоит из 14 или 15 фишек, то он полностью исчезает, а если фишек 16, то получается большой набор навигационных огней, состоящий из восьми мигалок. Эволюция семнадцатиклеточного ряда заканчивается четырьмя блоками; ряды, состоящие из 18 или 19 фишек, полностью исчезают с доски, а эволюция двадцатиклеточного ряда завершается двумя блоками.

Конуэй также исследовал эволюцию рядов, образованных пятиклеточными группами, отделенными друг от друга одной свободной клеткой.

Ряд 5-5 после двадцать первого хода превращается в пульсар СР 48-56-72. Ряд 5-5-5 переходит в четыре блока и четыре мигалки; в результате эволюции ряда 5-5-5-5 получаются четыре пасеки и четыре мигалки; ряд 5-5-5-5-5 заканчивает свои превращения «эффектно разбросанными» по доске восемью планерами и восемью мигалками.

Затем планеры попарно сталкиваются и, разрушаясь, превращаются в восемь блоков.

Ряд, состоящий из шести групп по пяти клеток в каждой (5-5-5-5-5-5), превращается в четыре мигалки, а эволюция следующего ряда 5-5-5-5-5-5-5, по мнению Конуэя, представляет «замечательное зрелище, если наблюдать её на экране вычислительной машины».

Однако он до сих пор не отслеживал его дальнейшую судьбу.

Переведено на Нотабеноиде
http://notabenoid.org/book/35417/126980

Переводчики: Irina73, karapanov, Junazzz