Игра жизни Конвея
"Игра Конвея" перенаправляет сюда. Для теории игр сюрреалистических чисел Конвея см. Сюрреалистическое число.
Игра жизни, также известная просто как Жизнь, представляет собой клеточный автомат, разработанный британским математиком Джоном Хортоном Конвеем в 1970 году. Это игра с нулевым игроком, это означает, что его эволюция определяется его начальным состоянием, не требуя дальнейшего ввода. Человек взаимодействует с Игрой Жизни, создавая начальную конфигурацию и наблюдая, как она развивается. Это полный Тьюринг и может имитировать универсальный конструктор или любую другую машину Тьюринга.
Правила
Вселенная Игры жизни представляет собой бесконечную двумерную ортогональную сетку квадратных ячеек, каждая из которых находится в одном из двух возможных состояний, живом или мертвом (или населенном и незаселенном соответственно). Каждая клетка взаимодействует со своими восемью соседями, которые являются соседними по горизонтали, вертикали или диагонали. На каждом шаге во времени происходят следующие переходы:
Любая живая клетка с менее чем двумя живыми соседями умирает, как будто из-за недостаточной численности населения. Любая живая клетка с двумя или тремя живыми соседями живет в следующем поколении. Любая живая клетка с более чем тремя живыми соседями умирает, как будто от перенаселения. Любая мертвая клетка с ровно тремя живыми соседями становится живой клеткой, как бы размножаясь.
Эти правила, которые сравнивают поведение автомата с реальной жизнью, можно свести к следующему:
Любая живая клетка с двумя или тремя живыми соседями выживает. Любая мертвая клетка с тремя живыми соседями становится живой клеткой. Все остальные живые клетки умирают в следующем поколении. Точно так же все остальные мертвые клетки остаются мертвыми.
Начальный паттерн составляет семя системы. Первое поколение создается путем одновременного применения вышеуказанных правил к каждой клетке семени, живой или мертвой; рождение и смерть происходят одновременно, и дискретный момент, в который это происходит, иногда называют тиком.[nb 1] Каждое поколение является чистой функцией предыдущего. Правила продолжают применяться неоднократно для создания последующих поколений. Происхождение
Станислав Улам, работая в Лос-Аламосской национальной лаборатории в 1940-х годах, изучал рост кристаллов, используя в качестве модели простую решеточную сеть.[7] В то же время Джон фон Нейман, коллега Улама в Лос-Аламосе, работал над проблемой самовоспроизводящихся систем.[8]: 1 Первоначальный проект фон Неймана был основан на идее одного робота, создающего другого робота. Эта конструкция известна как кинематическая модель.[9][10] Разрабатывая эту конструкцию, фон Нейман осознал огромную трудность создания самовоспроизводящегося робота и большую стоимость обеспечения робота "морем деталей", из которых можно построить его репликанта. Нейман написал статью под названием "Общая и логическая теория автоматов" для симпозиума Хиксона в 1948 году.[8]: 1 Улам был тем, кто предложил использовать дискретную систему для создания редукционистской модели самовоспроизведения.[8]: 3 [11]: xxix Улам и фон Нейман создали метод расчета движения жидкости в конце 1950-х годов. Движущая концепция метода состояла в том, чтобы рассматривать жидкость как группу дискретных единиц и вычислять движение каждой из них на основе поведения ее соседей.: 8 Так родилась первая система клеточных автоматов. Как и решетчатая сеть Улама, клеточные автоматы фон Неймана двумерны, а его саморепликатор реализован алгоритмически. В результате получился универсальный копировальный аппарат и конструктор, работающий в клеточном автомате с небольшой окрестностью (соседями являются только те клетки, которые соприкасаются; для клеточных автоматов фон Неймана - только ортогональные клетки) и с 29 состояниями на клетку. Фон Нейман дал доказательство существования того, что определенный паттерн будет создавать бесконечные копии себя в данной клеточной вселенной, разработав конфигурацию из 200 000 клеток, которая могла бы это сделать. Эта конструкция известна как модель тесселяции и называется универсальным конструктором фон Неймана[13].
Мотивированный вопросами математической логики и частично работой над симуляционными играми Улама, среди прочего, Джон Конвей начал проводить эксперименты в 1968 году с различными двумерными правилами клеточных автоматов. Первоначальная цель Конвея состояла в том, чтобы определить интересный и непредсказуемый клеточный автомат.[3] По словам Мартина Гарднера, Конвей экспериментировал с различными правилами, стремясь к правилам, которые позволили бы шаблонам "по-видимому" расти без ограничений, в то же время затрудняя доказательство того, что любой данный шаблон будет делать это. Более того, некоторые "простые начальные паттерны" должны "расти и меняться в течение значительного периода времени", прежде чем осесть в статическую конфигурацию или повторяющийся цикл.[1] Позже Конвей писал, что основной мотивацией для жизни было создание "универсального" клеточного автомата.[14][требуется лучший источник]
Игра впервые появилась в октябре 1970 года в Scientific American, в колонке Мартина Гарднера "Математические игры", которая была основана на личных беседах с Конвеем. Теоретически Игра жизни обладает силой универсальной машины Тьюринга: все, что может быть вычислено алгоритмически, может быть вычислено в Игре жизни.[15][2] Гарднер писал: "Из-за аналогий Жизни с подъемом, падением и изменениями общества живых организмов, этоотносится к растущему классу так называемых "симуляционных игр" (игр, напоминающих реальные процессы)"[1].
С момента своей публикации Игра жизни привлекла большой интерес из-за удивительных способов, которыми шаблоны могут развиваться. Она представляет собой пример возникновения и самоорганизации. Версия Жизни, включающая случайные флуктуации, использовалась в физике для изучения фазовых переходов и неравновесной динамики. Игра также может служить дидактической аналогией, используемой для передачи несколько нелогичного представления о том, что дизайн иорганизация может спонтанно возникнуть в отсутствие дизайнера. Например, философ Дэниел Деннет широко использовал аналогию с игрой жизни "вселенная", чтобы проиллюстрировать возможную эволюцию сложных философских конструкций, таких как сознание и свободная воля, из относительно простого набора детерминированных физических законов, которые могут управлять нашей вселенной.
Популярности Game of Life способствовало ее появление одновременно со все более недорогим доступом к компьютеру. Игра могла быть запущена в течение нескольких часов на этих машинах, которые в противном случае остались бы неиспользованными ночью. В этом отношении она предвосхитила более позднюю популярность компьютерных фракталов. Для многих Игра в жизнь была просто задачей программирования: забавный способ использовать впустую потраченные циклы процессора. Для некоторых, однако, Игра жизни имела более философские коннотации. В 1970-е и последующие годы она стала культовой; современные разработки зашли так далеко, что создали теоретические эмуляции компьютерных систем в рамках доски Game of Life.
Примеры паттернов
В Игре жизни встречается много различных типов паттернов, которые классифицируются в соответствии с их поведением. Распространенные типы паттернов включают в себя: натюрморты, которые не меняются от одного поколения к другому; осцилляторы, которые возвращаются в исходное состояние после конечного числа поколений; и космические корабли, которые переводятся через сетку.
Самые ранние интересные закономерности в Игре жизни были обнаружены без использования компьютеров. Простейшие натюрморты и осцилляторы были обнаружены при отслеживании судеб различных небольших стартовых конфигураций с использованием графической бумаги, досок и физических игровых досок, таких как те, которые используются в Go. Во время этого раннего исследования Конвей обнаружил, что R-пентомино не смог стабилизироваться в небольшом количестве поколений. На самом деле, для стабилизации требуется 1103 поколения, к этому времени его население составляет 116 человек, и он произвел шесть спасающихся планеров; [22] это были первые космические корабли, когда-либо обнаруженные.
Часто встречающиеся примеры (в том смысле, что они часто возникают из случайной начальной конфигурации клеток) трех вышеупомянутых типов паттернов показаны ниже, причем живые клетки показаны черным цветом, а мертвые - белым. Период относится к числу тиков, которые шаблон должен пройти, прежде чем вернуться к своей первоначальной конфигурации.