Натюрморт (конфигурация клеточного автомата)
Натюрмо́рт — класс конфигураций в «Жизни» — созданной Конвеем модели клеточного автомата.
Содержание
Описание
Натюрморты — конфигурации «Жизни» или другого клеточного автомата, которые не изменяются в процессе эволюции[1]. Иными словами, натюрморт является осциллятором периода 1[2][3][4].
Терминология: натюрморты и псевдонатюрморты
Существует несколько близких по смыслу терминов, обозначающих не изменяющиеся в процессе эволюции конфигурации (конфигурации, являющиеся собственными родителями). Различия между ними связаны с ответом на следующие вопросы:
- Считается ли натюрмортом конфигурация, состоящая из двух независимых натюрмтортов (например, двух блоков на достаточно большом расстоянии друг от друга)?[5]
- Считается ли натюрмортом конфигурация, состоящая из двух частей, любую из которых можно удалить так, что вторая часть останется родителем себя?
В существующих словарях и онлайн-энциклопедиях[6][7][4][8] приводятся следующие определения:
- Устойчивый образец (англ. stable pattern) — объект, который является собственным родителем[2][3];
- Натюрморт (англ. still life, strict still life) — устойчивый объект, являющийся конечным и непустым, который не может быть разделён на две устойчивые части[9][10][8];
- Псевдонатюрморт (англ. pseudo still life) — устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из составляющих объект натюрмортов[11][12][8].
Точное определение «устойчивости» представляет интерес в контексте перечисления натюрмортов: например, согласно приведённым определениям, количество устойчивых конфигураций размера 8 (т.е. состоящих из 8 живых клеток) в «Жизни» бесконечно, так как пара блоков на любом расстоянии друг от друга является устойчивой; тем не менее, количество натюрмортов ограниченного размера считается конечным[6][7][8].
![]() |
Псевдонатюрморт в «Жизни». Удаление одного из островов не влияет на стабильность второго острова. |
![]() |
«Строгий» натюрморт. Стабильность каждого из островов зависит от наличия другого острова. |
Известно число натюрмортов и псевдонатюрмортов размера не выше 24 клеток[11][12][8].
Задача определения типа устойчивой конфигурации (натюрморт, псевдонатюрморт) решается за полиномиальное время путём поиска циклов в связанном кососимметричном графе (англ.)[13].
Натюрморты в «Жизни»
В «Жизни» существует множество естественных[14] натюрмортов.
Простые примеры
Блок
Наиболее распространённый натюрморт — блок[15][16][17] — конфигурация в форме квадрата 2 × 2. Два блока, размещённые в прямоугольнике 2 × 5, образуют би-блок — простейший псевдонатюрморт. Блоки используются в качестве составных частей во множестве сложных устройств, например, в планерном ружье Госпера[17].
|
![]() |
Улей
Второй по распространённости натюрморт — улей (англ. hive, beehive). Ульи часто возникают четвёрками в конфигурации, называемой па́секой (англ. honey farm)[15][16][17].
![]() |
![]() |
Каравай
Третий по распространённости натюрморт — каравай (англ. loaf). Караваи нередко появляются парами (англ. bi-loaf)[15][16][17]. В свою очередь, двойные караваи также появляются в парах, называемых пека́рнями (англ. bakery)[18].
|
![]() |
![]() |
Ящики, баржи, лодки, корабли
Ящик (англ. tub) состоит из четырёх живых клеток в окрестности фон Неймана центральной мёртвой клетки. Добавление одной живой клетки по диагонали к центральной клетке превращает ящик в лодку (англ. boat), а добавление симметрично ещё одной клетки — в корабль (англ. ship)[19]. Естественное удлинение этих трёх конфигураций даёт баржу (англ. barge), длинную лодку (англ. long-boat) и длинный корабль (англ. long-ship) соответственно. Удлинение можно продолжать сколь угодно долго[16][6][7][17].
![]() |
![]() |
![]() |
Из двух лодок можно составить ещё один натюрморт — лодочный бант (англ. boat tie), а из двух кораблей — корабельный бант (англ. ship tie)[6][7].
![]() |
![]() |
Другие натюрморты
|
Пожиратели и отражатели
Натюрморты можно использовать для модификации или разрушения других объектов. Пожиратель (англ. eater) способен уничтожить космический корабль и восстановиться после реакции. Отражатель (англ. reflector) вместо уничтожения космического корабля изменяет направление его полёта.
Отражатели и пожиратели не обязательно должны являться натюрмортами.
Максимальная плотность
Задача размещения в области n × n натюрморта с максимальным числом клеток привлекала к себе внимание программистов как задача программирования в ограничениях[20][21][22][23][24]. При стремлении размера области к бесконечности, живыми могут быть не более 50% клеток[25]. На конечных квадратных областях можно достичь больших плотностей. Так, максимальная плотность натюрморта в квадрате 8 × 8 равна 36/64 = 0.5625 — эту плотность обеспечивает образец, состоящий из девяти блоков[20] Для квадратов до 20 × 20 известны оптимальные решения[26][27].
Число натюрмортов
Число натюрмортов и псевдонатюрмортов в «Жизни» известно до размера в 24 клетки[28][29][30].
Число живых клеток | Число натюрмортов | Примеры |
---|---|---|
1 | 0 | |
2 | 0 | |
3 | 0 | |
4 | 2 | блок, ящик |
5 | 1 | лодка |
6 | 5 | баржа, авианосец, улей, корабль, змея |
7 | 4 | рыболовный крючок, каравай, длинная лодка |
8 | 9 | каноэ, манго, длинная баржа, пруд |
9 | 10 | знак интеграла |
10 | 25 | лодочный бант |
11 | 46 | |
12 | 121 | корабельный бант |
13 | 240 | |
14 | 619 | двойной каравай |
15 | 1353 | |
16 | 3286 | |
17 | 7773 | |
18 | 19044 | |
19 | 45759 | пожиратель 2 |
20 | 112243 | |
21 | 273188 | |
22 | 672172 | |
23 | 1646147 | |
24 | 4051711 |
Напишите отзыв о статье "Натюрморт (конфигурация клеточного автомата)"
Примечания
- ↑ Более строгие определения см. в разделе «Терминология».
- ↑ 1 2 [beluch.ru/life/lifelex/lexr_u.htm#stable Устойчивый]. Словарь Жизни.
- ↑ 1 2 [www.argentum.freeserve.co.uk/lex_s.htm#stable Stable]. Life Lexicon.
- ↑ 1 2 Eric Weisstein. [www.ericweisstein.com/encyclopedias/life/StillLife.html Still Life]. Treasure Trove of Life C.A.. Проверено 11 августа 2013.
- ↑ Если ответ на этот вопрос положительный, то количество натюрмортов с ограниченным числом клеток бесконечно.
- ↑ 1 2 3 4 Николай Белюченко. [beluch.ru/life/lifelex/lexr.htm Словарь Жизни] (рус.). [web.archive.org/web/20121010232359/beluch.ru/life/lifelex/lexr.htm Архивировано из первоисточника 10 октября 2012].
- ↑ 1 2 3 4 Stephen A. Silver. [www.argentum.freeserve.co.uk/lex.htm Life Lexicon] (англ.). [web.archive.org/web/20130526120520/www.argentum.freeserve.co.uk/lex.htm Архивировано из первоисточника 26 мая 2013].
- ↑ 1 2 3 4 5 [www.conwaylife.com/wiki/Still_life Still life]. ConwayLife.com. Проверено 11 августа 2013.
- ↑ [beluch.ru/life/lifelex/lexr_n.htm#stilllife Натюрморт]. Словарь Жизни.
- ↑ [www.argentum.freeserve.co.uk/lex_s.htm#stilllife Still life]. Life Lexicon.
- ↑ 1 2 [beluch.ru/life/lifelex/lexr_p.htm#pseudostilllife Псевдонатюрморт]. Словарь Жизни.
- ↑ 1 2 [www.argentum.freeserve.co.uk/lex_p.htm#pseudostilllife Pseudo still life]. Life Lexicon.
- ↑ Cook, Matthew (2003). "Still life theory". New Constructions in Cellular Automata: 93–118, Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press.
- ↑ Естественный образец — объект, относительно часто возникающий в процессе развития случайной конфигурации.
- ↑ 1 2 3 Achim Flammenkamp. [wwwhomes.uni-bielefeld.de/achim/freq_top_life.html Top 100 of Game-of-Life Ash Objects]. Проверено 5 ноября 2008.
- ↑ 1 2 3 4 [life.written.ru/game_of_life_review_by_gardner Игра Жизнь (обзор Гарднера)]. Проверено 11 августа 2013. [web.archive.org/web/20121018225222/life.written.ru/game_of_life_review_by_gardner Архивировано из первоисточника 18 октября 2012].
- ↑ 1 2 3 4 5 Клумова И. Н. [kvant.mccme.ru/1974/09/igra_zhizn.htm Игра «Жизнь»] // Квант. — 1974. — № 9. — С. 26—30.
- ↑ [beluch.ru/life/lifelex/lexr_p.htm#bakery Пекарня]. Словарь Жизни.
- ↑ Не путать с космическим кораблём.
- ↑ 1 2 Bosch, R. A. (1999). «Integer programming and Conway’s game of Life». SIAM Review 41 (3): 594–604. DOI:10.1137/S0036144598338252..
- ↑ Bosch, R. A. (2000). «Maximum density stable patterns in variants of Conway’s game of Life». Operations Research Letters 27 (1): 7–11. DOI:10.1016/S0167-6377(00)00016-X..
- ↑ Smith, Barbara M. (2002), [dx.doi.org/10.1007%2F3-540-46135-3_27 "A dual graph translation of a problem in ‘Life’"], Principles and Practice of Constraint Programming - CP 2002, vol. 2470, Lecture Notes in Computer Science, Springer-Verlag, pp. 89–94, DOI 10.1007/3-540-46135-3_27 .
- ↑ (2004) «Constraint programming and hybrid formulations for three Life designs». Annals of Operations Research 130 (1–4): 41–56. DOI:10.1023/B:ANOR.0000032569.86938.2f..
- ↑ (2006) «Applying ad-hoc global constraints with the case constraint to still-life». Constraints 11 (2–3): 91–114. DOI:10.1007/s10601-006-8058-9..
- ↑ Elkies, Noam D. (1998). "The still life density problem and its generalizations". Voronoi's Impact on Modern Science, Book I: 228–253, Proc. Inst. Math. Nat. Acad. Sci. Ukraine, vol. 21.
- ↑ J. Larrosa, E. Morancho and D. Niso (2005). «[www.jair.org/papers/paper1541.html On the Practical use of Variable Elimination in Constraint Optimization Problems: 'Still-life' as a Case Study]». Journal of Artificial Intelligence Research 23: 421–440.
- ↑ Neil Yorke-Smith. [www.ai.sri.com/~nysmith/life/index.html Maximum Density Still Life]. Artificial Intelligence Center. SRI International.
- ↑ Number of stable n-celled patterns («still lifes») in Conway's game of Life
- ↑ Number of n-celled pseudo-still-lifes in Conway's game of Life
- ↑ Niemiec, Mark D. [web.archive.org/web/20130121155106/home.interserv.com/~mniemiec/still.htm Life Still-Lifes].
Внешние ссылки
- Николай Белюченко. [beluch.ru/life/lifelex/lexr.htm Словарь Жизни]. [web.archive.org/web/20121010232359/beluch.ru/life/lifelex/lexr.htm Архивировано из первоисточника 10 октября 2012].
- Stephen A. Silver. [www.argentum.freeserve.co.uk/lex.htm Life Lexicon]. [web.archive.org/web/20130526120520/www.argentum.freeserve.co.uk/lex.htm Архивировано из первоисточника 26 мая 2013].
|
Отрывок, характеризующий Натюрморт (конфигурация клеточного автомата)
Маленькому сыну князя Андрея было семь лет. Он едва умел читать, он ничего не знал. Он многое пережил после этого дня, приобретая знания, наблюдательность, опытность; но ежели бы он владел тогда всеми этими после приобретенными способностями, он не мог бы лучше, глубже понять все значение той сцены, которую он видел между отцом, княжной Марьей и Наташей, чем он ее понял теперь. Он все понял и, не плача, вышел из комнаты, молча подошел к Наташе, вышедшей за ним, застенчиво взглянул на нее задумчивыми прекрасными глазами; приподнятая румяная верхняя губа его дрогнула, он прислонился к ней головой и заплакал.С этого дня он избегал Десаля, избегал ласкавшую его графиню и либо сидел один, либо робко подходил к княжне Марье и к Наташе, которую он, казалось, полюбил еще больше своей тетки, и тихо и застенчиво ласкался к ним.
Княжна Марья, выйдя от князя Андрея, поняла вполне все то, что сказало ей лицо Наташи. Она не говорила больше с Наташей о надежде на спасение его жизни. Она чередовалась с нею у его дивана и не плакала больше, но беспрестанно молилась, обращаясь душою к тому вечному, непостижимому, которого присутствие так ощутительно было теперь над умиравшим человеком.
Князь Андрей не только знал, что он умрет, но он чувствовал, что он умирает, что он уже умер наполовину. Он испытывал сознание отчужденности от всего земного и радостной и странной легкости бытия. Он, не торопясь и не тревожась, ожидал того, что предстояло ему. То грозное, вечное, неведомое и далекое, присутствие которого он не переставал ощущать в продолжение всей своей жизни, теперь для него было близкое и – по той странной легкости бытия, которую он испытывал, – почти понятное и ощущаемое.
Прежде он боялся конца. Он два раза испытал это страшное мучительное чувство страха смерти, конца, и теперь уже не понимал его.
Первый раз он испытал это чувство тогда, когда граната волчком вертелась перед ним и он смотрел на жнивье, на кусты, на небо и знал, что перед ним была смерть. Когда он очнулся после раны и в душе его, мгновенно, как бы освобожденный от удерживавшего его гнета жизни, распустился этот цветок любви, вечной, свободной, не зависящей от этой жизни, он уже не боялся смерти и не думал о ней.
Чем больше он, в те часы страдальческого уединения и полубреда, которые он провел после своей раны, вдумывался в новое, открытое ему начало вечной любви, тем более он, сам не чувствуя того, отрекался от земной жизни. Всё, всех любить, всегда жертвовать собой для любви, значило никого не любить, значило не жить этою земною жизнию. И чем больше он проникался этим началом любви, тем больше он отрекался от жизни и тем совершеннее уничтожал ту страшную преграду, которая без любви стоит между жизнью и смертью. Когда он, это первое время, вспоминал о том, что ему надо было умереть, он говорил себе: ну что ж, тем лучше.
Но после той ночи в Мытищах, когда в полубреду перед ним явилась та, которую он желал, и когда он, прижав к своим губам ее руку, заплакал тихими, радостными слезами, любовь к одной женщине незаметно закралась в его сердце и опять привязала его к жизни. И радостные и тревожные мысли стали приходить ему. Вспоминая ту минуту на перевязочном пункте, когда он увидал Курагина, он теперь не мог возвратиться к тому чувству: его мучил вопрос о том, жив ли он? И он не смел спросить этого.
Болезнь его шла своим физическим порядком, но то, что Наташа называла: это сделалось с ним, случилось с ним два дня перед приездом княжны Марьи. Это была та последняя нравственная борьба между жизнью и смертью, в которой смерть одержала победу. Это было неожиданное сознание того, что он еще дорожил жизнью, представлявшейся ему в любви к Наташе, и последний, покоренный припадок ужаса перед неведомым.
Это было вечером. Он был, как обыкновенно после обеда, в легком лихорадочном состоянии, и мысли его были чрезвычайно ясны. Соня сидела у стола. Он задремал. Вдруг ощущение счастья охватило его.
«А, это она вошла!» – подумал он.
Действительно, на месте Сони сидела только что неслышными шагами вошедшая Наташа.
С тех пор как она стала ходить за ним, он всегда испытывал это физическое ощущение ее близости. Она сидела на кресле, боком к нему, заслоняя собой от него свет свечи, и вязала чулок. (Она выучилась вязать чулки с тех пор, как раз князь Андрей сказал ей, что никто так не умеет ходить за больными, как старые няни, которые вяжут чулки, и что в вязании чулка есть что то успокоительное.) Тонкие пальцы ее быстро перебирали изредка сталкивающиеся спицы, и задумчивый профиль ее опущенного лица был ясно виден ему. Она сделала движенье – клубок скатился с ее колен. Она вздрогнула, оглянулась на него и, заслоняя свечу рукой, осторожным, гибким и точным движением изогнулась, подняла клубок и села в прежнее положение.
Он смотрел на нее, не шевелясь, и видел, что ей нужно было после своего движения вздохнуть во всю грудь, но она не решалась этого сделать и осторожно переводила дыханье.
В Троицкой лавре они говорили о прошедшем, и он сказал ей, что, ежели бы он был жив, он бы благодарил вечно бога за свою рану, которая свела его опять с нею; но с тех пор они никогда не говорили о будущем.
«Могло или не могло это быть? – думал он теперь, глядя на нее и прислушиваясь к легкому стальному звуку спиц. – Неужели только затем так странно свела меня с нею судьба, чтобы мне умереть?.. Неужели мне открылась истина жизни только для того, чтобы я жил во лжи? Я люблю ее больше всего в мире. Но что же делать мне, ежели я люблю ее?» – сказал он, и он вдруг невольно застонал, по привычке, которую он приобрел во время своих страданий.
Услыхав этот звук, Наташа положила чулок, перегнулась ближе к нему и вдруг, заметив его светящиеся глаза, подошла к нему легким шагом и нагнулась.
– Вы не спите?
– Нет, я давно смотрю на вас; я почувствовал, когда вы вошли. Никто, как вы, но дает мне той мягкой тишины… того света. Мне так и хочется плакать от радости.
Наташа ближе придвинулась к нему. Лицо ее сияло восторженною радостью.
– Наташа, я слишком люблю вас. Больше всего на свете.
– А я? – Она отвернулась на мгновение. – Отчего же слишком? – сказала она.
– Отчего слишком?.. Ну, как вы думаете, как вы чувствуете по душе, по всей душе, буду я жив? Как вам кажется?
– Я уверена, я уверена! – почти вскрикнула Наташа, страстным движением взяв его за обе руки.
Он помолчал.
– Как бы хорошо! – И, взяв ее руку, он поцеловал ее.
Наташа была счастлива и взволнована; и тотчас же она вспомнила, что этого нельзя, что ему нужно спокойствие.
– Однако вы не спали, – сказала она, подавляя свою радость. – Постарайтесь заснуть… пожалуйста.
Он выпустил, пожав ее, ее руку, она перешла к свече и опять села в прежнее положение. Два раза она оглянулась на него, глаза его светились ей навстречу. Она задала себе урок на чулке и сказала себе, что до тех пор она не оглянется, пока не кончит его.
Действительно, скоро после этого он закрыл глаза и заснул. Он спал недолго и вдруг в холодном поту тревожно проснулся.
Засыпая, он думал все о том же, о чем он думал все ото время, – о жизни и смерти. И больше о смерти. Он чувствовал себя ближе к ней.
«Любовь? Что такое любовь? – думал он. – Любовь мешает смерти. Любовь есть жизнь. Все, все, что я понимаю, я понимаю только потому, что люблю. Все есть, все существует только потому, что я люблю. Все связано одною ею. Любовь есть бог, и умереть – значит мне, частице любви, вернуться к общему и вечному источнику». Мысли эти показались ему утешительны. Но это были только мысли. Чего то недоставало в них, что то было односторонне личное, умственное – не было очевидности. И было то же беспокойство и неясность. Он заснул.
Он видел во сне, что он лежит в той же комнате, в которой он лежал в действительности, но что он не ранен, а здоров. Много разных лиц, ничтожных, равнодушных, являются перед князем Андреем. Он говорит с ними, спорит о чем то ненужном. Они сбираются ехать куда то. Князь Андрей смутно припоминает, что все это ничтожно и что у него есть другие, важнейшие заботы, но продолжает говорить, удивляя их, какие то пустые, остроумные слова. Понемногу, незаметно все эти лица начинают исчезать, и все заменяется одним вопросом о затворенной двери. Он встает и идет к двери, чтобы задвинуть задвижку и запереть ее. Оттого, что он успеет или не успеет запереть ее, зависит все. Он идет, спешит, ноги его не двигаются, и он знает, что не успеет запереть дверь, но все таки болезненно напрягает все свои силы. И мучительный страх охватывает его. И этот страх есть страх смерти: за дверью стоит оно. Но в то же время как он бессильно неловко подползает к двери, это что то ужасное, с другой стороны уже, надавливая, ломится в нее. Что то не человеческое – смерть – ломится в дверь, и надо удержать ее. Он ухватывается за дверь, напрягает последние усилия – запереть уже нельзя – хоть удержать ее; но силы его слабы, неловки, и, надавливаемая ужасным, дверь отворяется и опять затворяется.
Еще раз оно надавило оттуда. Последние, сверхъестественные усилия тщетны, и обе половинки отворились беззвучно. Оно вошло, и оно есть смерть. И князь Андрей умер.
Но в то же мгновение, как он умер, князь Андрей вспомнил, что он спит, и в то же мгновение, как он умер, он, сделав над собою усилие, проснулся.
«Да, это была смерть. Я умер – я проснулся. Да, смерть – пробуждение!» – вдруг просветлело в его душе, и завеса, скрывавшая до сих пор неведомое, была приподнята перед его душевным взором. Он почувствовал как бы освобождение прежде связанной в нем силы и ту странную легкость, которая с тех пор не оставляла его.
Когда он, очнувшись в холодном поту, зашевелился на диване, Наташа подошла к нему и спросила, что с ним. Он не ответил ей и, не понимая ее, посмотрел на нее странным взглядом.
Это то было то, что случилось с ним за два дня до приезда княжны Марьи. С этого же дня, как говорил доктор, изнурительная лихорадка приняла дурной характер, но Наташа не интересовалась тем, что говорил доктор: она видела эти страшные, более для нее несомненные, нравственные признаки.
С этого дня началось для князя Андрея вместе с пробуждением от сна – пробуждение от жизни. И относительно продолжительности жизни оно не казалось ему более медленно, чем пробуждение от сна относительно продолжительности сновидения.
Ничего не было страшного и резкого в этом, относительно медленном, пробуждении.
Последние дни и часы его прошли обыкновенно и просто. И княжна Марья и Наташа, не отходившие от него, чувствовали это. Они не плакали, не содрогались и последнее время, сами чувствуя это, ходили уже не за ним (его уже не было, он ушел от них), а за самым близким воспоминанием о нем – за его телом. Чувства обеих были так сильны, что на них не действовала внешняя, страшная сторона смерти, и они не находили нужным растравлять свое горе. Они не плакали ни при нем, ни без него, но и никогда не говорили про него между собой. Они чувствовали, что не могли выразить словами того, что они понимали.