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

Перейти к навигацииПерейти к поиску
Запрос «R-пентамино» перенаправляется сюда; см. также другие значения.
Фигура R пентамино
R-пентамино из игры «Жизнь» стабилизируется через 1103 поколения

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

Более точно Мартин Гарднер определяет их как конфигурации из 10 или меньшего числа клеток, которым необходимо не менее 50 поколений для стабилизации[2]. Англоязычное название Мафусаи́л (англ. Methuselah) происходит от имени библейского персонажа Мафусаила, прожившего 969 лет.

Примеры в игре «Жизнь»

Самым простым долгожителем игры «Жизнь» является R-пентамино, эволюция которого изображена справа[3]. Это конфигурация из пяти ячеек, открытая создателем игры «Жизнь» Джоном Конвеем, которая стабилизируется спустя 1103 поколения[4].

В результате на поле остаётся 116 живых ячеек, образующих 25 объектов: 8 блоков, 6 планеров, 4 улья, 4 мигалки, 1 лодку, 1 каравай и 1 корабль[5]. Первый из шести планеров образуется спустя 69 поколений. Он был замечен в 1970 году Ричардом Гаем и стал первым зарегистрированным планером[6].

Другим примером долгожителя является конфигурация жёлудь (англ. acorn), которая состоит из 7 ячеек в начальном состоянии и стабилизируется спустя 5206 поколений, оставляя на поле 633 ячейки, образующие конфигурацию дуб (англ. oak)[7].

Примечания

  1. ↑ Белюченко, Николай Словарь игры «Жизнь» (2 февраля 2006). Дата обращения: 27 сентября 2017. Архивировано 22 сентября 2017 года.
  2. ↑ Gardner, M. (1983). "The Game of Life, Part III". Wheels, Life and Other Mathematical Amusements. p. 246.
  3. ↑ Silver, Stephen R-pentomino. Life Lexicon (28 февраля 2006). Дата обращения: 24 декабря 2008. Архивировано 21 декабря 2008 года.
  4. ↑ Gardner, M. (1983). "The Game of Life, Part III". Wheels, Life and Other Mathematical Amusements. pp. 219, 223.
  5. ↑ Poundstone, William. The Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge. — 1985. — С. 33—36. — 256 с. — ISBN 978-0809252022.
  6. ↑ Клумова И. Н. Игра «Жизнь» // Квант. — 1974. — № 9. — С. 26—30. Архивировано 4 марта 2016 года.
  7. ↑ Silver, Stephen Acorn. Life Lexicon (28 февраля 2006). Дата обращения: 24 декабря 2008. Архивировано из оригинала 19 апреля 2009 года.