stringtranslate.com

Игра жизни Конвея

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

Игра в жизнь , также известная как Игра в жизнь Конвея или просто Жизнь , — это клеточный автомат, разработанный британским математиком Джоном Хортоном Конвеем в 1970 году. [1] Это игра с нулевым количеством игроков , [2] [3] что означает, что ее эволюция определяется ее начальным состоянием, не требуя дополнительных входных данных. Человек взаимодействует с Игрой в жизнь, создавая начальную конфигурацию и наблюдая, как она развивается. Она является полной по Тьюрингу и может имитировать универсальный конструктор или любую другую машину Тьюринга .

Правила

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

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

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

Происхождение

Станислав Улам , работая в Национальной лаборатории Лос-Аламоса в 1940-х годах, изучал рост кристаллов, используя простую решетчатую сеть в качестве своей модели. [7] В то же время Джон фон Нейман , коллега Улама в Лос-Аламосе, работал над проблемой самовоспроизводящихся систем . [8] : 1  Первоначальный проект фон Неймана был основан на идее того, что один робот строит другого робота. Этот проект известен как кинематическая модель. [9] [10] Разрабатывая этот проект, фон Нейман пришел к пониманию большой сложности создания самовоспроизводящегося робота и больших затрат на обеспечение робота «морем деталей», из которых можно построить его репликанта. Нейман написал статью под названием «Общая и логическая теория автоматов» для симпозиума Хиксона в 1948 году. [11] Улам был тем, кто предложил использовать дискретную систему для создания редукционистской модели самовоспроизводства. [8] : 3  [12] : xxix  Улам и фон Нейман создали метод расчета движения жидкости в конце 1950-х годов. Движущей идеей метода было рассматривать жидкость как группу дискретных единиц и вычислять движение каждой на основе поведения ее соседей. [13] : 8  Так родилась первая система клеточных автоматов. Подобно решетчатой ​​сети Улама, клеточные автоматы фон Неймана являются двумерными, а его саморепликатор реализован алгоритмически. Результатом стал универсальный копировщик и конструктор, работающий в клеточном автомате с небольшим соседством (только те ячейки, которые соприкасаются, являются соседями; для клеточных автоматов фон Неймана только ортогональные ячейки) и с 29 состояниями на ячейку. Фон Нейман дал доказательство существования того, что определенный шаблон будет создавать бесконечные копии себя в пределах данной клеточной вселенной, спроектировав конфигурацию из 200 000 ячеек, которая могла бы это делать. Эта конструкция известна как модель тесселяции и называется универсальным конструктором фон Неймана . [14]

Мотивированный вопросами математической логики и отчасти работой над имитационными играми Улама, среди прочих, Джон Конвей начал проводить эксперименты в 1968 году с различными правилами двумерного клеточного автомата. Первоначальной целью Конвея было определить интересный и непредсказуемый клеточный автомат. [3] По словам Мартина Гарднера , Конвей экспериментировал с различными правилами, стремясь к правилам, которые позволили бы шаблонам «очевидно» расти без ограничений, в то же время затрудняя доказательство того, что любой заданный шаблон будет делать это. Более того, некоторые «простые начальные шаблоны» должны «расти и изменяться в течение значительного периода времени», прежде чем прийти к статической конфигурации или повторяющемуся циклу. [1] Позже Конвей писал, что основной мотивацией для Жизни было создание «универсального» клеточного автомата. [15] [ нужен лучший источник ]

Игра впервые появилась на публике в выпуске Scientific American за октябрь 1970 года в колонке Мартина Гарднера « Математические игры », которая была основана на личных беседах с Конвеем. Теоретически Игра Жизни обладает мощью универсальной машины Тьюринга : все, что может быть вычислено алгоритмически, может быть вычислено в Игре Жизни. [16] [2] Гарднер писал: «Из-за аналогий Жизни с подъемом, падением и изменениями общества живых организмов, она принадлежит к растущему классу так называемых «игр-симуляций» (игр, которые напоминают реальные процессы)». [1]

С момента публикации Игра Жизни привлекла большой интерес из-за удивительных способов, которыми могут развиваться модели. Она представляет собой пример возникновения и самоорганизации . [3] Версия Жизни, которая включает случайные флуктуации, использовалась в физике для изучения фазовых переходов и неравновесной динамики . [17] Игра также может служить дидактической аналогией , используемой для передачи несколько контринтуитивного представления о том, что дизайн и организация могут спонтанно возникать при отсутствии дизайнера. Например, философ Дэниел Деннетт широко использовал аналогию Игры Жизни «вселенная», чтобы проиллюстрировать возможную эволюцию сложных философских конструкций, таких как сознание и свободная воля , из относительно простого набора детерминированных физических законов, которые могут управлять нашей вселенной. [18] [19] [20]

Популярность Игры Жизни была обусловлена ​​тем, что она появилась в то же время, что и доступ к компьютерам становился все более дешевым. Игра могла работать часами на этих машинах, которые в противном случае оставались бы неиспользованными ночью. В этом отношении она предвещала более позднюю популярность фракталов , генерируемых компьютером . Для многих Игра Жизни была просто задачей программирования: забавным способом использовать иначе растрачиваемые впустую циклы ЦП . Для некоторых, однако, Игра Жизни имела более философские коннотации. Она стала культовой в 1970-х годах и позже; современные разработки зашли так далеко, что создали теоретические эмуляции компьютерных систем в пределах доски Игры Жизни. [21] [22]

Примеры узоров

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

Самые ранние интересные закономерности в Игре Жизни были обнаружены без использования компьютеров. Простейшие натюрморты и осцилляторы были обнаружены при отслеживании судеб различных небольших начальных конфигураций с использованием миллиметровой бумаги , школьных досок и физических игровых досок, таких как те, что используются в Го . Во время этого раннего исследования Конвей обнаружил, что R- пентамино не удалось стабилизироваться за небольшое количество поколений. Фактически, для стабилизации требуется 1103 поколения, к этому времени его популяция составляет 116, и он сгенерировал шесть спасающихся планеров ; [23] это были первые когда-либо обнаруженные космические корабли. [24]

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

Пульсар [27] является наиболее распространенным осциллятором с периодом 3. Подавляющее большинство встречающихся в природе осцилляторов имеют период 2, как мигалка и жаба, но известно, что существуют осцилляторы всех периодов, [ 28] [29] [30] и осцилляторы с периодами 4, 8, 14, 15, 30 и несколькими другими, как было замечено, возникают из случайных начальных условий. [31] Модели, которые развиваются в течение длительных периодов перед стабилизацией, называются Мафусаилами , первым обнаруженным из которых был R-пентамино. Diehard — это модель, которая исчезает через долгое время. Начальные модели из восьми или более клеток можно заставить умереть через произвольно долгое время. [32] Acorn требуется 5206 поколений, чтобы создать 633 клетки, включая 13 сбежавших планеров. [33]

Первоначально Конвей предположил, что ни один шаблон не может расти бесконечно, то есть для любой начальной конфигурации с конечным числом живых клеток популяция не может вырасти выше некоторого конечного верхнего предела. В первоначальном появлении игры в «Математических играх» Конвей предложил приз в пятьдесят долларов (эквивалент 390 долларов в 2023 году) первому человеку, который сможет доказать или опровергнуть гипотезу до конца 1970 года. Приз был выигран в ноябре командой из Массачусетского технологического института во главе с Биллом Госпером ; «планерная пушка Госпера» производит свой первый планер на 15-м поколении, а затем еще один планер в каждом 30-м поколении. В течение многих лет эта планерная пушка была самой маленькой из известных. [34] В 2015 году было обнаружено ружье под названием «планирующее ружье Симкина», которое выпускает планер каждые 120 поколений, в котором меньше живых клеток, но которое распределено по более крупной ограничивающей области на своих концах. [35]

Позже были обнаружены более мелкие узоры, которые также демонстрируют бесконечный рост. Все три узора, показанные ниже, растут бесконечно. Первые два создают единый механизм переключения блоков : конфигурацию, которая оставляет после себя блоки неподвижной жизни размером два на два, поскольку она перемещается по вселенной игры. [36] Третья конфигурация создает два таких узора. Первый имеет только десять живых ячеек, что, как было доказано, является минимальным. [37] Второй вписывается в квадрат пять на пять, а третий имеет высоту всего одну ячейку.

Более поздние открытия включали другие пушки , которые являются стационарными и производят планеры или другие космические корабли; паровозы , которые движутся, оставляя за собой след из мусора; и грабли , которые движутся и выпускают космические корабли. [38] Госпер также построил первую модель с асимптотически оптимальной квадратичной скоростью роста , называемую селекционером или лобстером , которая работала, оставляя за собой след из пушек.

Глайдеры могут взаимодействовать с другими объектами интересными способами. Например, если два глайдера выстрелить в блок в определенном положении, блок переместится ближе к источнику глайдеров. Если три глайдера выстрелить в правильном направлении, блок переместится дальше. Эту скользящую память блока можно использовать для имитации счетчика . Можно построить логические вентили, такие как И , ИЛИ и НЕ , используя глайдеры. Можно построить шаблон, который действует как конечный автомат, подключенный к двум счетчикам. Он имеет ту же вычислительную мощность, что и универсальная машина Тьюринга , поэтому Игра Жизни теоретически так же мощна, как любой компьютер с неограниченной памятью и без ограничений по времени; она является полной по Тьюрингу . [16] [2] Фактически, в Игре Жизни было реализовано несколько различных архитектур программируемых компьютеров [39] [40] , включая шаблон, который имитирует Тетрис . [41]

Более того, шаблон может содержать набор пушек, которые стреляют планерами таким образом, чтобы создавать новые объекты, включая копии исходного шаблона. Можно построить универсальный конструктор , который содержит полный по Тьюрингу компьютер и который может создавать множество типов сложных объектов, включая больше копий самого себя. [2]

В 2018 году Адам П. Гучер открыл первый по-настоящему элементарный рыцарский корабль, сэр Робин. [42] Рыцарский корабль — это космический корабль, который перемещается на две клетки влево за каждую клетку, на которую он перемещается вниз (как конь в шахматах ), в отличие от движения ортогонально или по диагонали в 45°. Это первая новая модель движения космического корабля для элементарного космического корабля, обнаруженная за сорок восемь лет. «Элементарная» означает, что ее нельзя разложить на более мелкие взаимодействующие модели, такие как планеры и натюрморты. [43]

Неразрешимость

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

Игра «Жизнь» неразрешима , что означает, что при наличии начального шаблона и более позднего шаблона не существует алгоритма, который может сказать, появится ли когда-нибудь более поздний шаблон. Учитывая, что Игра «Жизнь» является полной по Тьюрингу, это следствие проблемы остановки : проблемы определения того, завершит ли данная программа выполнение или продолжит выполняться вечно с начального ввода. [2]

Косые космические корабли

До 2010-х годов все известные космические корабли могли двигаться только ортогонально или диагонально, тогда как существование движущихся моделей, которые движутся как рыцари, было предсказано Элвином Берлекампом еще в 1982 году. Космические корабли, которые не движутся ни ортогонально, ни диагонально, обычно называют косыми космическими кораблями [44] [45] . 18 мая 2010 года Эндрю Дж. Уэйд объявил о первом косом космическом корабле, названном «Gemini», который создает копию себя на (5,1) дальше, уничтожая своего родителя. [46] [45] Эта модель воспроизводится в 34 миллионах поколений и использует ленту инструкций, сделанную из планеров, колеблющихся между двумя стабильными конфигурациями, сделанными из конструкционных рычагов Чепмена–Грина. Они, в свою очередь, создают новые копии модели и уничтожают предыдущую копию. В декабре 2015 года были построены диагональные версии Gemini. [47]

Самовоспроизведение

23 ноября 2013 года Дэйв Грин построил первый репликатор в Игре Жизни, который создает полную копию самого себя, включая ленту инструкций. [48] В октябре 2018 года Адам П. Гушер завершил строительство метаклетки 0E0P, метаклетки, способной к саморепликации. Это отличалось от предыдущих метаклеток, таких как метапиксель OTCA Брайса Дью, который работал только с уже построенными копиями рядом с ними. Метаклетка 0E0P работает, используя конструкторские рычаги для создания копий, которые имитируют запрограммированное правило. [49] Фактическое моделирование Игры Жизни или других правил соседства Мура выполняется путем моделирования эквивалентного правила с использованием соседства фон Неймана с большим количеством состояний. [50] Название 0E0P является сокращением от «Zero Encoded by Zero Population» («Ноль, кодируемый нулевой популяцией»), что указывает на то, что вместо того, чтобы метаячейка находилась в состоянии «выключено», имитирующем пустое пространство, метаячейка 0E0P удаляет себя, когда клетка входит в это состояние, оставляя пустое пространство. [51]

Итерация

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

Алгоритмы

Ранние модели с неизвестным будущим, такие как R-пентамино, побудили программистов писать программы для отслеживания эволюции моделей в Игре Жизни. Большинство ранних алгоритмов были похожи: они представляли модели как двумерные массивы в памяти компьютера. Обычно используются два массива: один для хранения текущего поколения и один для вычисления его преемника. Часто 0 и 1 представляют мертвые и живые клетки соответственно. Вложенный цикл for рассматривает каждый элемент текущего массива по очереди, подсчитывая живых соседей каждой клетки, чтобы решить, должен ли соответствующий элемент массива преемника быть 0 или 1. Массив преемника отображается. Для следующей итерации массивы могут поменяться ролями, так что массив преемника в последней итерации станет текущим массивом в следующей итерации, или можно скопировать значения второго массива в первый массив, а затем снова обновить второй массив из первого массива.

Возможны различные незначительные улучшения этой базовой схемы, и есть много способов сэкономить ненужные вычисления. Ячейка, которая не изменилась на последнем временном шаге, и ни один из соседей которой не изменился, гарантированно не изменится и на текущем временном шаге, поэтому программа, которая отслеживает, какие области активны, может сэкономить время, не обновляя неактивные зоны. [54]

Игра жизни на поверхности трилистника
Игра жизни на поверхности тороидального трилистника

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

Для экономии памяти хранилище можно сократить до одного массива плюс два буфера строк. Один буфер строк используется для вычисления состояния-последователя для строки, затем буфер второй строки используется для вычисления состояния-последователя для следующей строки. Затем первый буфер записывается в свою строку и освобождается для хранения состояния-последователя для третьей строки. Если используется тороидальный массив, необходим третий буфер, чтобы можно было сохранить исходное состояние первой строки в массиве до тех пор, пока не будет вычислена последняя строка.

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

В принципе, поле Игры Жизни бесконечно, но компьютеры имеют конечную память. Это приводит к проблемам, когда активная область вторгается на границу массива. Программисты использовали несколько стратегий для решения этих проблем. Самая простая стратегия — предположить, что каждая клетка за пределами массива мертва. Это легко программировать, но приводит к неточным результатам, когда активная область пересекает границу. Более сложный трюк — считать, что левый и правый края поля сшиты вместе, а также верхний и нижний края, что дает тороидальный массив. Результатом является то, что активные области, которые перемещаются по краю поля, снова появляются на противоположном краю. Неточность все еще может возникнуть, если узор становится слишком большим, но патологических краевых эффектов нет. Также могут использоваться методы динамического распределения памяти, создавая все большие массивы для хранения растущих узоров. Игра Жизни на конечном поле иногда явно изучается; некоторые реализации, такие как Golly , поддерживают выбор стандартного бесконечного поля, поля, бесконечного только в одном измерении, или конечного поля с выбором топологий, таких как цилиндр, тор или лента Мёбиуса .

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

Для исследования больших шаблонов на большой временной глубине могут быть полезны сложные алгоритмы, такие как Hashlife . Существует также метод реализации Игры Жизни и других клеточных автоматов с использованием произвольных асинхронных обновлений, при этом точно эмулируя поведение синхронной игры. [55] Примеры исходного кода , реализующие базовый сценарий Игры Жизни на различных языках программирования, включая C , C++ , Java и Python, можно найти на Rosetta Code . [56]

Вариации

С момента создания Игры Жизни были разработаны новые, похожие клеточные автоматы. Стандартная Игра Жизни обозначается в нотации строк правил как B3/S23. Клетка рождается, если у нее ровно три соседа, выживает, если у нее два или три живых соседа, и умирает в противном случае. Первое число или список чисел — это то, что требуется для рождения мертвой клетки. Второй набор — это требование для того, чтобы живая клетка дожила до следующего поколения. Следовательно, B6/S16 означает «клетка рождается, если есть шесть соседей, и продолжает жить, если есть один или шесть соседей». Клеточные автоматы на двумерной сетке, которые можно описать таким образом, известны как клеточные автоматы, подобные жизни . Другой распространенный автомат, похожий на жизнь, Highlife , описывается правилом B36/S23, потому что наличие шести соседей, в дополнение к правилу B3/S23 оригинальной игры, вызывает рождение. HighLife больше всего известна своими часто встречающимися репликаторами. [57] [58]

Существуют дополнительные клеточные автоматы, подобные Life. Подавляющее большинство из этих 2 18 различных правил [59] создают вселенные, которые либо слишком хаотичны, либо слишком пустынны, чтобы представлять интерес, но большое подмножество действительно демонстрирует интересное поведение. Дальнейшее обобщение создает изотропное пространство правил с 2 102 возможными правилами клеточного автомата [60] (Игра Жизни снова является одним из них). Это правила, которые используют ту же квадратную сетку, что и правила Life, и то же восьмиклеточное соседство, и также инвариантны относительно вращения и отражения. Однако в изотропных правилах положения соседних ячеек относительно друг друга могут учитываться при определении будущего состояния ячейки, а не только общее число этих соседей.

Пример 48-шагового осциллятора вместе с 2-шаговым осциллятором и 4-шаговым осциллятором из двумерной гексагональной игры «Жизнь» (правило H:B2/S34)

Некоторые вариации Игры Жизни изменяют геометрию вселенной, а также правила. Вышеуказанные вариации можно рассматривать как двумерный квадрат, поскольку мир двумерен и выложен в квадратной сетке. Были разработаны одномерные квадратные вариации, известные как элементарные клеточные автоматы , [61] и трехмерные квадратные вариации, а также двумерные шестиугольные и треугольные вариации. Также был создан вариант с использованием апериодических мозаичных сеток. [62]

Правила Конвея также могут быть обобщены таким образом, что вместо двух состояний, живого и мертвого , будет три или более. Переходы состояний затем определяются либо системой весов, либо таблицей, определяющей отдельные правила перехода для каждого состояния; например, разноцветная таблица правил Cellebration's Mirek's и семейства правил Weighted Life включают в себя примеры правил, эквивалентные Игре Жизни.

Модели, относящиеся к фракталам и фрактальным системам, также могут наблюдаться в некоторых вариациях, подобных жизни. Например, автомат B1/S12 генерирует четыре очень близких приближения к треугольнику Серпинского при применении к одной живой клетке. Треугольник Серпинского также можно наблюдать в Игре жизни, исследуя долгосрочный рост бесконечно длинной линии живых клеток толщиной в одну клетку, [63], а также в Highlife, Seeds (B2/S) и правиле Вольфрама 90. [64]

Иммиграция — это вариация, которая очень похожа на Игру Жизни, за исключением того, что есть два состояния «включено », часто выражаемых двумя разными цветами. Всякий раз, когда рождается новая клетка, она принимает состояние «включено», которое является большинством в трех клетках, которые ее породили. Эту функцию можно использовать для изучения взаимодействия между космическими кораблями и другими объектами в игре. [65] Другая похожая вариация, называемая QuadLife, включает четыре различных состояния «включено». Когда новая клетка рождается от трех разных соседей «включено», она принимает четвертое значение, а в противном случае, как и в случае Иммиграции, она принимает значение большинства. [66] За исключением вариации между клетками «включено», обе эти вариации действуют идентично Игре Жизни.

Музыка

Различные музыкальные методы композиции используют Игру Жизни, особенно в MIDI- секвенировании. [67] Существует множество программ для создания звука из шаблонов, созданных в Игре Жизни. [68] [69] [70]

Известные программы

The6 366 548 773 467 669 985 195 496 000 -й (6 × 10 27 ) поколение машины Тьюринга , созданное в игре Жизнь, вычислено менее чем за 30 секунд на процессоре Intel Core Duo 2 ГГц с использованием Golly в режиме Hashlife

Компьютеры использовались для отслеживания и моделирования Игры Жизни с тех пор, как она была впервые опубликована. Когда Джон Конвей впервые исследовал, как развивались различные начальные конфигурации, он отслеживал их вручную, используя доску го с ее черными и белыми камнями. Это было утомительно и подвержено ошибкам. Первая интерактивная программа Игры Жизни была написана на ранней версии ALGOL 68C для PDP-7 MJT Guy и SR Bourne . Результаты были опубликованы в выпуске Scientific American за октябрь 1970 года вместе с заявлением: «Без ее помощи некоторые открытия об игре было бы трудно сделать». [1]

Цветная версия Игры Жизни была написана Эдом Холлом в 1976 году для микрокомпьютеров Cromemco , и изображение этой программы заполнило обложку выпуска Byte за июнь 1976 года . [71] Появление цветной графики на основе микрокомпьютеров от Cromemco было приписано возрождению интереса к игре. [72]

Две ранние реализации Игры Жизни на домашних компьютерах были написаны Малкольмом Банторпом на BBC BASIC . Первая была в выпуске журнала Acorn User за январь 1984 года , а Банторп последовал за ней с трехмерной версией в выпуске за май 1984 года. [73] Сьюзан Степни, профессор компьютерных наук в Университете Йорка , продолжила это в 1988 году с программой Life on the Line, которая генерировала одномерные клеточные автоматы. [74]

Сейчас в сети есть тысячи программ Game of Life, поэтому полный список здесь не приводится. Ниже приведен небольшой выбор программ, которые претендуют на особую известность, например, популярность или необычные функции. Большинство этих программ включают графический пользовательский интерфейс для редактирования и моделирования шаблонов, возможность моделирования нескольких правил, включая Game of Life, и большую библиотеку интересных шаблонов в Game of Life и других правилах клеточного автомата.

Google реализовал пасхальное яйцо Игры Жизни в 2012 году. Пользователям, которые ищут этот термин, на странице результатов поиска показывается реализация игры. [77]

Визуальный роман Anonymous;Code включает в себя базовую реализацию Игры Жизни, которая связана с сюжетом романа. Ближе к концу Anonymous;Code определенный узор, который появляется на протяжении всей игры в виде татуировки на героине Момо Айзаки, должен быть введен в Игру Жизни, чтобы завершить игру (галактика Кока, тот же узор, который используется в качестве логотипа для программы Game of Life с открытым исходным кодом Golly).

Смотрите также

Примечания

  1. ^ Одновременность означает, что когда каждая клетка подсчитывает количество живых соседей вокруг себя, она использует старые состояния своих соседей до обновления, а не их новые состояния после обновления. Если клетки вместо этого обновляются в порядке чтения, так что каждая клетка использует старые состояния клеток справа и ниже себя, но новые состояния клеток слева и выше себя, получается другой клеточный автомат, который известен как NaiveLife [4] [5], потому что это распространенная ошибка новичков среди людей, пытающихся запрограммировать игру Конвея «Жизнь». [6]

Ссылки

  1. ^ abcd Гарднер, Мартин (октябрь 1970 г.). «Фантастические комбинации новой игры-пасьянса Джона Конвея „жизнь“» (PDF) . Математические игры. Scientific American . Том 223, № 4. стр. 120–123. doi :10.1038/scientificamerican1070-120. JSTOR  24927642. Архивировано (PDF) из оригинала 2022-10-09.
  2. ^ abcde Берлекамп, Э.Р .; Конвей, Джон Хортон ; Гай, Р.К. (2001–2004). Выигрышные пути для ваших математических игр (2-е изд.). AK Peters Ltd.
  3. ^ abc Ижикевич, Евгений М.; Конвей, Джон Х .; Сет, Анил (2015-06-21). «Игра жизни». Scholarpedia . 10 (6): 1816. Bibcode : 2015SchpJ..10.1816I. doi : 10.4249/scholarpedia.1816 . ISSN  1941-6016.
  4. ^ "NaiveLife Emulated: Моделирование жизни в порядке чтения". ConwayLife.com . 24 мая 2020 г. Получено 29 ноября 2021 г.
  5. ^ Goucher, Adam. "Re: Thread For Your Accidental Discoveries". ConwayLife.com . Получено 29 ноября 2021 г. .
  6. ^ Ian07. "Re: Странный космический корабль, который, как предполагается, невозможен, и бесконечное распространение клеток". ConwayLife.com . Получено 29 ноября 2021 г. Я почти уверен, что это потому, что вы случайно создали реализацию того, что иногда называют NaiveLife (так как это распространенная ошибка, которую совершают многие люди, впервые кодирующие CGoL):{{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка )
  7. ^ Пиковер, Клиффорд А. (2009). Книга по математике: от Пифагора до 57-го измерения, 250 вех в истории математики . Sterling Publishing Company, Inc. стр. 406. ISBN 978-1402757969.
  8. ^ ab Шифф, Джоэл Л. (2011). Клеточные автоматы: дискретный взгляд на мир. Wiley & Sons, Inc. ISBN 9781118030639.
  9. ↑ Джон фон Нейман, «Общая и логическая теория автоматов», в книге Л. А. Джеффресса «Церебральные механизмы в поведении – Симпозиум Хиксона», John Wiley & Sons, Нью-Йорк, 1951, стр. 1–31.
  10. ^ Кемени, Джон Г. (1955). «Человек рассматривается как машина». Sci. Am . 192 (4): 58–67. Bibcode : 1955SciAm.192d..58K. doi : 10.1038/scientificamerican0455-58.; наук. Являюсь. 1955 год; 192:6 (ошибка).
  11. ^ Фон Нейман, Джон (1976). Собрание сочинений. 4: Непрерывная геометрия и другие темы (Повторное издание). Оксфорд [ua] Франкфурт: Pergamon Press. ISBN 978-0-08-009566-0.
  12. ^ Илачински, Эндрю (2001). Клеточные автоматы: Дискретная Вселенная. World Scientific. ISBN 978-981-238-183-5.
  13. ^ Бялиницки-Бирула, Иво; Бялиницка-Бирула, Ивона (2004). Моделирование реальности: как компьютеры отражают жизнь . Oxford University Press . ISBN 978-0198531005.
  14. ^ фон Нейман, Джон; Беркс, Артур У. (1966). Теория самовоспроизводящихся автоматов. Издательство Иллинойсского университета .
  15. ↑ Конвей, личное сообщение «Life list», 14 апреля 1999 г.
  16. ^ ab Это модель и симуляция, за которыми интересно наблюдать, и которые могут показать, что простые вещи могут стать сложными проблемами. Пол Чепмен (11 ноября 2002 г.). «Life Universal Computer». Архивировано из оригинала 6 сентября 2009 г. Получено 12 июля 2009 г.
  17. ^ Альстрём, Пребен; Леан, Жуан (1994-04-01). «Самоорганизованная критичность в игре Жизни». Physical Review E. 49 ( 4): R2507–R2508. Bibcode : 1994PhRvE..49.2507A. doi : 10.1103/PhysRevE.49.R2507. PMID  9961636.
  18. ^ Деннетт, Д.К. (1991). Объяснение сознания . Бостон: Back Bay Books. ISBN 978-0-316-18066-5.
  19. ^ Деннетт, Д.К. (1995). Опасная идея Дарвина: Эволюция и смысл жизни . Нью-Йорк: Simon & Schuster. ISBN 978-0-684-82471-0.
  20. ^ Деннетт, DC (2003). Свобода эволюционирует . Нью-Йорк: Penguin Books. ISBN 978-0-14-200384-8.
  21. ↑ Пол Ренделл (12 января 2005 г.). «Машина Тьюринга в игре «Жизнь» Конвея» . Получено 12 июля 2009 г.
  22. ^ Адам П. Гушер. "Спартанский универсальный компьютер-конструктор". LifeWiki . Получено 5 декабря 2021 г. .
  23. ^ "R-пентамино". ЖизньВики. 1983. С. 219, 223 . Проверено 5 декабря 2021 г.
  24. ^ Стивен А. Сильвер. «Планер». The Life Lexicon . Получено 4 марта 2019 г.
  25. ^ "Результаты переписи в игре Конвея "Жизнь"". Онлайн-поиск супа "Жизнь как в Калифорнии". Архивировано из оригинала 2009-09-10 . Получено 12 июля 2009 .
  26. ^ "Спонтанно возникшие космические корабли из случайной пыли". Ахим Фламменкамп (1995-12-09) . Получено 10 июля 2012 г.
  27. ^ Стивен А. Сильвер. «Пульсар». The Life Lexicon . Получено 4 марта 2019 г.
  28. ^ Браун, Нико; Ченг, Карсон; Якоби, Таннер; Карпович, Майя; Мерцених, Маттиас; Рауччи, Дэвид; Райли, Митчелл (5 декабря 2023 г.). «Конвеевская игра жизни омнипериодична». arXiv : 2312.02799 [math.CO].
  29. ^ "LifeWiki:Страница статуса игры "Жизнь" - LifeWiki". conwaylife.com . Получено 16.12.2023 .
  30. ^ Стоун, Алекс (18.01.2024). «Математическая «игра жизни» раскрывает давно искомые повторяющиеся закономерности». Журнал Quanta . Получено 18.01.2024 .
  31. ^ Ахим Фламменкамп (2004-09-07). "Наиболее часто встречающиеся природные объекты из пепла в Игре Жизни" . Получено 2008-09-16 .
  32. ^ Стивен А. Сильвер. «Diehard». The Life Lexicon . Получено 4 марта 2019 г.
  33. ^ Koenig, H. (21 февраля 2005 г.). "New Methuselah Records". Архивировано из оригинала 10 сентября 2019 г. Получено 24 января 2009 г.
  34. ^ Стивен А. Сильвер. "Gosper glider gun". The Life Lexicon . Получено 4 марта 2019 г.
  35. ↑ Охота за новыми каналами Гершеля, форумы ConwayLife, 28 апреля 2015 г., сообщения Майкла Симкина («simsim314») и Донгука Ли («Scorbie»).
  36. ^ "Блокировочный стрелочный двигатель". LifeWiki . Получено 5 декабря 2021 г. .
  37. ^ Стивен А. Сильвер. «Бесконечный рост». The Life Lexicon . Получено 4 марта 2019 г.
  38. ^ Стивен А. Сильвер. «Rake». The Life Lexicon . Получено 4 марта 2019 г.
  39. ^ "Программируемый компьютер". Форумы conwaylife.com . Получено 23 августа 2018 г.
  40. ^ "Машина Тьюринга в игре Конвея "Жизнь", расширяемая до универсальной машины Тьюринга". Пол Ренделл . Получено 23 августа 2018 г.
  41. ^ "Создайте рабочую игру Тетрис в игре Конвея "Жизнь"". StackExchange . Получено 23 августа 2018 г.
  42. ^ "Элементарное рыцарство" . Получено 9 марта 2018 г.
  43. ^ "Элементарно", LifeWiki. Получено 21.11.2018
  44. ^ Арон, Джейкоб (16 июня 2010 г.). «Первое воспроизводящееся существо, созданное в симуляторе жизни». New Scientist . Получено 12 октября 2013 г.
  45. ^ ab "Gemini – LifeWiki". Conwaylife.com . Получено 2013-10-16 .
  46. ^ "Универсальный конструктор на основе космического корабля". Conwaylife.com . Получено 24.06.2012 .
  47. ^ "Demonoid". LifeWiki . Получено 18 июня 2016 .
  48. ^ "Geminoid Challenge". Conwaylife.com . Получено 25.06.2015 .
  49. ^ Passe-Science (2019-05-29). "Automate Cellulaire - Passe-science #27". Архивировано из оригинала 2021-12-11 . Получено 2019-06-25 – через YouTube .
  50. ^ apgoucher (2018-11-12). "Полностью самоуправляемая репликация". Комплексное проективное 4-пространство . Получено 2019-06-25 .
  51. ^ "0E0P metacell - LifeWiki". conwaylife.com . Получено 24.06.2019 .
  52. ^ Анджей Окрасинский. "Статистика объектов игры "Жизнь"". Архивировано из оригинала 2009-07-27 . Получено 12 июля 2009 .
  53. ^ Натаниэль Джонстон. "Онлайн-поиск супа CA Life-Like". Архивировано из оригинала 2009-09-10 . Получено 12 июля 2009 .
  54. ^ Алан Хенсел. "О моем апплете игры жизни Конвея" . Получено 12 июля 2009 г.
  55. ^ Nehaniv, Chrystopher L. (15–18 июля 2002 г.). Self-Reproduction in Asynchronous Cellular Automata . Конференция NASA/DoD 2002 года по развивающемуся оборудованию. Александрия, Вирджиния, США: IEEE Computer Society Press. стр. 201–209. doi : 10.1109/EH.2002.1029886. hdl : 2299/6834 . ISBN 0-7695-1718-8.
  56. ^ «Конвеевская игра жизни». Rosetta Code . 7 июня 2024 г.
  57. ^ HighLife – Интересный вариант жизни Дэвида Белла (файл .zip)
  58. ^ Стивен А. Сильвер. «Репликатор». The Life Lexicon . Получено 4 марта 2019 г.
  59. ^ "Жизнеподобные клеточные автоматы - LifeWiki". Conwaylife.com . Получено 4 марта 2019 г. .
  60. ^ "Изотропный - LifeWiki". Conwaylife.com . Получено 4 марта 2019 г. .
  61. ^ "Элементарный клеточный автомат". Wolfram Mathworld . Получено 12 июля 2009 г.
  62. ^ «Первые планеры бороздят вечно меняющуюся вселенную Пенроуза». New Scientist .
  63. ^ Стивен Вольфрам , Новый вид науки онлайн, Примечание (f) для структур в системах класса 4: Структуры в игре жизни: «Более простой вид неограниченного роста происходит, если начать с бесконечной линии черных ячеек. В этом случае эволюция фактически одномерна и, как оказывается, следует элементарному правилу 22»
  64. ^ "Жизнь подражает Серпинскому". Форумы ConwayLife.com . Получено 12 июля 2009 г.
  65. ^ Стивен А. Сильвер. «Иммиграция». The Life Lexicon . Получено 4 марта 2019 г.
  66. ^ Стивен А. Сильвер. "QuadLife". The Life Lexicon . Получено 4 марта 2019 г.
  67. ^ Беррастон, Дэйв; Эдмондс, Эрнест; Ливингстон, Дэн; Миранда, Эдуардо Рек (2004). «Клеточные автоматы в компьютерной музыке на основе MIDI». Труды Международной конференции по компьютерной музыке 2004 года . CiteSeerX 10.1.1.6.3882 . hdl :10453/1425. ISBN  9780971319226.
  68. ^ "glitchDS – Cellular Automaton Sequencer For The Nintendo DS". Synthtopia.com. 2008-05-29 . Получено 2012-06-24 .
  69. ^ "Game Of Life Music Sequencer". Synthtopia.com. 2009-04-29 . Получено 2012-06-24 .
  70. ^ "Game Of Life Music Sequencer для iOS, Runxt Life". Synthtopia.com. 2011-01-12 . Получено 2012-06-24 .
  71. ↑ Helmers, Carl (июнь 1976). «About the Cover». Byte . No. 10. pp. 6–7 . Получено 18 февраля 2013 г.
  72. ^ Макинтош, Гарольд (2008). «Введение» (PDF) . Журнал клеточных автоматов . 13 : 181–186. Архивировано (PDF) из оригинала 2022-10-09 . Получено 3 ноября 2021 . С появлением микрокомпьютеров и графической платы Cromemco Life стала любимой программой отображения для видеомониторов и привела к возрождению интереса к игре.
  73. ^ "Сканирование журнала пользователей Acorn". Библиотека общественного достояния BBC и Master Computer . Получено 29 декабря 2018 г.
  74. ^ Степни, Сьюзен. "Статьи AcornUser". www-users.cs.york.ac.uk . AcornUser . Получено 29.12.2018 .
  75. ^ "Xlife - LifeWiki" . conwaylife.com .
  76. ^ «Организм доктора Блоба — это бесплатно!». digital-eel.com .
  77. ^ Вассерман, Тодд (12 июля 2012 г.). «Введите «Conway's Game of Life» в Google и посмотрите, что произойдет». Mashable . Получено 1 мая 2020 г. .

Внешние ссылки

На Викискладе есть медиафайлы по теме «Игра в жизнь».