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

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

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

Более точно Мартин Гарднер определяет их как конфигурации из 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.
  2. Gardner, M. (1983). «The Game of Life, Part III». Wheels, Life and Other Mathematical Amusements: 246.
  3. Silver, Stephen R-pentomino. Life Lexicon (28 February 2006). Дата обращения: 24 декабря 2008. Архивировано 21 декабря 2008 года.
  4. Gardner, M. (1983). «The Game of Life, Part III». Wheels, Life and Other Mathematical Amusements: 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.
  7. Silver, Stephen Acorn (недоступная ссылка). Life Lexicon (28 February 2006). Дата обращения: 24 декабря 2008. Архивировано 19 апреля 2009 года.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.