Game of Life

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

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

правила

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

  1. Любая живая клетка с менее чем двумя живыми соседями умирает, как будто из-за недостаточного населения.
  2. Любая живая клетка с двумя или тремя живыми соседями доживает до следующего поколения.
  3. Любая живая клетка с более чем тремя живыми соседями умирает, как если бы она была перенаселена.
  4. Любая мертвая клетка с ровно тремя живыми соседями становится живой клеткой, как будто путем размножения.

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


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

Вдохновленный вопросами математической логики и, в частности, работой над играми-симуляторами Улама, Джон Конвей начал проводить эксперименты в 1968 году с различными правилами 2D-клеточных автоматов [3]. Первоначальная цель Конвея состояла в том, чтобы определить интересный и непредсказуемый клеточный автомат. Таким образом, он хотел, чтобы некоторые конфигурации сохранялись в течение долгого времени до смерти, другие конфигурации продолжались бесконечно, не допуская циклов и т. Д. Это было серьезной проблемой и открытой проблемой в течение многих лет, прежде чем специалистам по клеточным автоматам удалось доказать, что, действительно, Игра Жизни Конвея допускала конфигурацию, которая была живой в смысле удовлетворения двух общих требований фон Неймана. В то время как определения до Жизни Конвея были ориентированы на доказательства, конструкция Конвея была нацелена на простоту, без априорного доказательства того, что автомат был жив.

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

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

Многие паттерны в Игре Жизни в конечном итоге становятся комбинацией натюрмортов, осцилляторов и космических кораблей; другие модели можно назвать хаотичными. Шаблон может оставаться хаотичным в течение очень долгого времени, пока в конечном итоге не достигнет такой комбинации.