Во что играют математики? В “Жизнь”!

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

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

  1. В мертвой клетке, имеющей ровно три живые соседние клетки, зарождается жизнь в след. поколении.
  2. Живая клетка выживает до след. поколения только при наличии двух или трех живых соседей.
  3. Живая клетка умирает при меньше двух или больше трех живых соседей от одиночества или перенаселения соответственно.

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

Кто-то поиграл в “Жизнь”

Заметную роль в игре занимают шаблоны (от англ. pattern) или фигуры возникающие при определенных условиях. Их принято классифицировать по типу поведения в игре: “устойчивые” не изменяются в ходе эволюции, “периодические фигуры” имеют конечный цикл жизни, а “ружья” генерируют время от времени “движущиеся” фигуры. Тематическое вики посвященное игре “Жизнь” насчитывает 1063 открытые фигуры на сегодняшний день.

Игра, в своей сущности, представляет собой незатейливую вариацию клеточного автомата, дискретной модели работающей на поле из клеток, и следовательно берет начало с 40-х годов прошлого столетия. В этот период плодовитый математик Джон фон Нейман задает основу теории клеточных автоматов, пока только на бумаге. Идея создания самовоспроизводимой системы привлекает его, изначально в физическом воплощении, но позже исключительно в теоретическом виде. Уже в следующем десятилетии, в сотрудничестве с Станиславом Уламом, он создает метод разбивающий частицы жидкости на отдельные единицы и рассчитывающий их дальнейшее перемещение. Правил у его игры было, правда, больше.

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

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

И хотя начинал разработку игры “Жизнь” Джон Конвей один, спустя время его поддержали другие математики. Публикация в научном журнале Scientific American (1970), ставшая первой посвященной игре Конвея, привлекла к проекту энтузиастов, занятых открытием новых фигур. Одним из них был Бил Госпер, он откликнулся на предложенный в журнале приз в $50 тому, кто докажет или опровергнет заявление Конвея до 1980 года. Заявление заключалось в том, что для любой начальной конфигурации игры, рост популяции прекратится после определенного числа поколений. Но Бил совершил прорывное опровержение!

Ружье Госпера (1970)

Новая фигура была названа в честь первооткрывателя. Задавая необходимое начальное расположение живых клеток, ружье генерировало свой первый планер (от англ. glider) в 15 поколении, а затем еще один каждое 30-е. Так как в теории игровая плоскость не ограничена, то ружье Госпера создавало постоянный прирост населения – именно то, что и требовалось!

Планерка (1970)

Фигура, генерируемая ружьем, была открыта еще раньше Ричардом Гай. Ошибочное мнение, что заслуга принадлежит самому Конвею, было однозначно опровержено в его биографии. Там же Джон заявил о своем разочаровании в названии фигуры: она скорее походила на муравья, чем на планер. Тем не менее, планер оказался невероятно полезен, целый ряд более комплексных фигур образовывался в результате столкновения несколько планеров. Более того, планер являлся первой и простейшей движущейся фигурой или космическим кораблем (от англ. spaceship).

С течением времени группа Конвея обнаруживала все больше математических загадок. В 1971 была выявлена фигура под названием “Сад Эдема”, не имеющая предыдущего поколения, то есть единственный способ получения сада – построить его перед началом игры. Отсюда взяла отсчет гонка нахождения наименьшей фигуры с подобным свойством.

Сам по себе сад не появится. Как философски!

Игра “Жизнь” Джона Конвея удивительно научная. Уже давно определена игровая “скорость света”, за обозначение которой отвечает символ c. И хотя ее значение равно размножению или перемещению на одну клетку за поколение, фактически такая скорость недостижима в игре. Доказано, что максимальная скорость движения диагонально – c/4 (одна клетка за четыре поколения), а ортогонально – c/2. Никакой корабль не сможет двигаться быстрее. Никак!

История о безграничных возможностях игры “Жизнь” тоже попирается научными столпами. В далеком 1936 Алан Тьюринг изобретает математическую модель машины, названной в его честь, и разрабатывает набор правил для нее. Он сумел доказать, что для любой задачи, описываемой алгоритмом, существует машина Тьюринга, решающая ее. Сверх того, был выдвинут тезис Чёрча-Тьюринга, который в своем упрощенном варианте гласит: “Никакой метод вычислений, проводимый механическим устройством, не может быть мощнее машины Тьюринга”. В довесок было введено понятие полноты по Тьюрингу – способности симулировать работу машины Тьюринга.

Связь между работами английского математика и игрой Конвея тонка, но значительна. Суть дела заключалась в том, что если “Жизнь” является тьюринг-полной, значит она способна выполнять любую задачу, да еще и эффективнее любого механического исполнителя, согласно тезису. Но является ли детище Джона Конвея полным по Тьюрингу? Безусловно!

Puffer: великий и ужасный

Во-первых, в рамках игры известны изощренные системы на основе нескольких планеров, симулирующие работу логических вентилей (И, ИЛИ, НЕ) и счетчиков для создания устройства с конечным числом состояний (от англ. finite state machine). Схема требует пространства в тысячи клеток, но разве в нашем мозгу их не миллиарды? Во-вторых, определенные фигуры способны на неограниченное самовоспроизведение, что заставляет систему работать непрерывно, совсем как машина. Отсюда и выходит, что Джон Конвей создал игру с невероятным потенциалом.

Легенда гласит, что в одном из военных отчетов армии США заявлялось об оценке стоимости часов, потраченных на наблюдение за игрой «Жизнь», в миллионы долларов.

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

Дополнительные материалы:

  • Здесь можно почитать доказательство максимальных скоростей и наблюдать построение логических вентилей
  • Здесь перевод интереснейшей биографии самого Джона Хортона Конвея
  • Здесь представлена браузерная версия игры с готовыми фигурами

 

Поделиться постом
Written by MrKasimov
Программист и фанат научной фантастики. В свободное время пропагандирую технооптимизм и математическую составляющую вселенной.
Have your say!
1 0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>