Ружьё (конфигурация клеточного автомата)

Ружьё (от англ. Gun) — класс конфигураций клеточного автомата (в частности, игры «Жизнь» Конвея), у которых основная часть циклически повторяется, как у осцилляторов, а также периодически создаёт космические корабли, которые удаляются от ружья. У ружья есть два периода: период создания космических кораблей и период повторения состояний ружья. Если период ружья больше периода создания космических кораблей, то ружьё называется псевдопериодическим (англ. pseudo-period).

Ружьё и «антиружьё» из «Дня и ночи», модификации игры «Жизнь». В «Дне и ночи» живые и мёртвые клетки играют симметричную роль, поэтому «антиружьём» называется ружьё из мёртвых клеток, создающее мёртвые космические корабли, двигающиеся среди поля живых клеток.
Одно из состояний планерного ружья Госпера — первого найденного ружья игры «Жизнь»
Планерное ружьё Госпера из игры «Жизнь» стреляет планерами

В игре «Жизнь» можно построить ружьё, которое создаёт планеры с любым периодом, большим или равным 14[1]. Поскольку ружья увеличивают число заполненных клеток, они являются примером конечных конфигураций, которые с течением времени достигают сколь угодно большого числа клеток. Конвей считал это невозможным и предложил премию в $50 за доказательство существования или несуществования подобной конфигурации[2].

Планерное ружьё Госпера

Первое ружьё было построено Биллом Госпером в 1970 году, за что он получил премию от Конвея. Это ружьё создаёт планеры с периодом 14 и часто называется планерным ружьём Госпера (англ. Gosper glider gun). Открытие этого ружья привело Конвея к доказательству, что «Жизнь» полна по Тьюрингу[3].

На протяжении многих лет это ружьё оставалось наименьшим в игре «Жизнь» по числу клеток, хотя для других наборов правил известны меньшие ружья[4]. Однако в 2015 году было найдено ружьё, создающее космические 120-ти периодные корабли имеющее меньшее число клеток, но больший радиус, чем планерное ружьё Госпера[5].

Примечания
  1. Summers, Jason Game of Life Status page. Entropymine.com. Дата обращения: 5 февраля 2011.
  2. Does John Conway hate his Game of Life?. Дата обращения: 16 апреля 2015.
  3. Gardner, Martin. The Colossal Book of Mathematics (англ.). — New York: W. W. Norton, 2001. — ISBN 0-393-02023-1.
  4. Stephen A. Silver. Gosper glider gun. The Life Lexicon. Дата обращения: 12 июля 2009. Архивировано 18 апреля 2009 года.
  5. The Hunting of the New Herschel Conduits, Conway Life forums. See in particular message by Scorbie, April 28th, 2015, 2:42 pm
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.