Космический корабль (конфигурация клеточного автомата)

Поделись знанием:
Перейти к: навигация, поиск

Косми́ческий кора́бль[5] (англ. spaceship) — класс конфигураций в «Жизни» — созданной Конвеем модели клеточного автомата.





Описание

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

Первым обнаруженным космическим кораблём стал планер. Планер был найден во время отслеживания эволюции R-пентамино в 1970 году Ричардом Гаем[1][7][8].

Космический корабль периода p, который перемещается на (m,n) в течение его периода, где m ≥ n, имеет тип (mn) / p. Как было доказано Конуэем в 1970 году, p ≥ 2m + 2n[6].

Космические корабли, движущиеся по горизонтали или вертикали, называются ортогональными кораблями. Если движение космического корабля происходит по диагонали под углом 45°, такой корабль называется диагональным. Космические корабли, движущиеся под другими углами, называются косыми или наклонными (англ. oblique). В 2010 году был сконструирован первый наклонный космический корабль типа (5120, 1024) / 33699586[9].

Скорость

Скоростью света в заданном клеточном автомате называют наибольшую скорость распространения информации. Скорость света в «Жизни» равна скорости перемещения шахматного короля — скорости в одну клетку за поколение по горизонтали, вертикали или диагонали. Обычно скорость света обозначается буквой c[1][6][10][11].

Скорость космического корабля определяется отношением расстояния смещения к периоду. Часто скорость выражается через c. Так, скорость планера в «Жизни» равна c / 4, так как он перемещается на одну клетку по диагонали за четыре поколения[7]. Простейший ортогональный космический корабль, ЛКК, движется со скоростью c / 2[2].

В общем случае, если космический корабль в двумерном клеточном автомате на квадратной сетке перемещается на вектор (xy) через n поколений, его скорость равна[11]

<math>v=\frac{\max\left(|x|,|y|\right)}{n}\,c</math>

Примеры

B3/S35

Следующие конфигурации являются ортогональными космическими кораблями в варианте «Жизни» — клеточном автомате с правилами B3/S35 (клетка рождается, если у неё три соседа, и выживает, если у неё три или пять соседей).

Связанные конфигурации

Тагалонг (англ. tagalong) — конфигурация, которая не является сама по себе космическим кораблём, но может быть присоединена к космическому кораблю, чтобы сформировать новый космический корабль[12]. Другими словами, тагалонг — это часть космического корабля, которую можно удалить без разрушения корабля[13].

Тагалонг, расположенный перед космическим кораблём, называют пушалонгом (англ. pushalong)[14].

Конфигурация, способная изменять направление движения космического корабля, не разрушаясь при этом, называется отражателем (англ. reflector).

Ружьё (англ. gun) — неподвижная конфигурация, периодически выпускающая космический корабль[15].

Значение

Космические корабли могут использоваться для передачи информации. Способность планера переносить информацию стала частью доказательства, что «Жизнь» является тьюринг-полной[16][17].

Напишите отзыв о статье "Космический корабль (конфигурация клеточного автомата)"

Примечания

  1. 1 2 3 Клумова И. Н. [kvant.mccme.ru/1974/09/igra_zhizn.htm Игра «Жизнь»] // Квант. — 1974. — № 9. — С. 26—30.
  2. 1 2 [beluch.ru/life/lifelex/lexr_l.htm#lwss ЛКК (лёгкий космический корабль)]. Словарь Жизни.
  3. [beluch.ru/life/lifelex/lexr_s.htm#mwss СКК (средний космический корабль)]. Словарь Жизни.
  4. [beluch.ru/life/lifelex/lexr_t.htm#hwss ТКК (тяжёлый космический корабль)]. Словарь Жизни.
  5. Не путать с [beluch.ru/life/lifelex/lexr_k.htm#ship кораблём] (ship) — устойчивой конфигурацией.
  6. 1 2 3 [beluch.ru/life/lifelex/lexr_k.htm#spaceship Космический корабль]. Словарь Жизни.
  7. 1 2 [beluch.ru/life/lifelex/lexr_g.htm#glider Глайдер]. Словарь Жизни.
  8. [www.conwaylife.com/wiki/Spaceship Spaceship]. ConwayLife.com.
  9. [pentadecathlon.com/lifeNews/2010/05/oblique_life_spaceship_created.html Oblique Life spaceship created]. Game of Life News (19 мая 2010). Проверено 10 августа 2013.
  10. [beluch.ru/life/lifelex/lexr_s.htm#speedoflight Скорость света]. Словарь Жизни.
  11. 1 2 [www.conwaylife.com/wiki/Speed Speed]. ConwayLife.com.
  12. [beluch.ru/life/lifelex/lexr_t.htm#tagalong Тагалонг]. Словарь Жизни.
  13. [www.ericweisstein.com/encyclopedias/life/Tagalong.html Tagalong]. Eric Weisstein's Treasure Trove of Life C.A..
  14. [beluch.ru/life/lifelex/lexr_p.htm#pushalong Пушалонг]. Словарь Жизни.
  15. [beluch.ru/life/lifelex/lexr_r.htm#gun Ружьё]. Словарь Жизни.
  16. Paul Chapman. [www.igblan.free-online.co.uk/igblan/ca/ Life Universal Computer] (November 11, 2002). Проверено 12 июля 2009.
  17. Berlekamp, E. R.; Conway, John Horton & Guy, R.K. (2004), Winning Ways for your Mathematical Plays (2nd ed.), A K Peters Ltd, ISBN 978-1-56881-130-7; ISBN 1-56881-142-X; ISBN 1-56881-143-8; ISBN 1-56881-144-6 

Ссылки

  • Николай Белюченко. [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].
  • Николай Белюченко. [beluch.ru/life/ships.htm Космические корабли в Жизни Конуэя]. [web.archive.org/web/20121003064954/beluch.ru/life/ships.htm Архивировано из первоисточника 3 октября 2012].
  • David I. Bell. [www.j-paine.org/dobbs/life.html Spaceships in Conway's Game of Life].
  • David Eppstein. [www.ics.uci.edu/~eppstein/ca/ Gliders in "Life"-Like Cellular Automata].
  • Achim Flammenkamp. [wwwhomes.uni-bielefeld.de/achim/moving.html Natural Spaceships in Game of Life]. — корабли, появляющиеся в случайных конфигурациях.
  • [pentadecathlon.com/lifeNews/spaceships/ Spaceships Archives]. Game of Life News.

Отрывок, характеризующий Космический корабль (конфигурация клеточного автомата)

– Так помни же: это не шутка.
– Какая шутка!
– Да, да, – как бы сама с собою говоря, сказала губернаторша. – А вот что еще, mon cher, entre autres. Vous etes trop assidu aupres de l'autre, la blonde. [мой друг. Ты слишком ухаживаешь за той, за белокурой.] Муж уж жалок, право…
– Ах нет, мы с ним друзья, – в простоте душевной сказал Николай: ему и в голову не приходило, чтобы такое веселое для него препровождение времени могло бы быть для кого нибудь не весело.
«Что я за глупость сказал, однако, губернаторше! – вдруг за ужином вспомнилось Николаю. – Она точно сватать начнет, а Соня?..» И, прощаясь с губернаторшей, когда она, улыбаясь, еще раз сказала ему: «Ну, так помни же», – он отвел ее в сторону:
– Но вот что, по правде вам сказать, ma tante…
– Что, что, мой друг; пойдем вот тут сядем.
Николай вдруг почувствовал желание и необходимость рассказать все свои задушевные мысли (такие, которые и не рассказал бы матери, сестре, другу) этой почти чужой женщине. Николаю потом, когда он вспоминал об этом порыве ничем не вызванной, необъяснимой откровенности, которая имела, однако, для него очень важные последствия, казалось (как это и кажется всегда людям), что так, глупый стих нашел; а между тем этот порыв откровенности, вместе с другими мелкими событиями, имел для него и для всей семьи огромные последствия.
– Вот что, ma tante. Maman меня давно женить хочет на богатой, но мне мысль одна эта противна, жениться из за денег.
– О да, понимаю, – сказала губернаторша.
– Но княжна Болконская, это другое дело; во первых, я вам правду скажу, она мне очень нравится, она по сердцу мне, и потом, после того как я ее встретил в таком положении, так странно, мне часто в голову приходило что это судьба. Особенно подумайте: maman давно об этом думала, но прежде мне ее не случалось встречать, как то все так случалось: не встречались. И во время, когда Наташа была невестой ее брата, ведь тогда мне бы нельзя было думать жениться на ней. Надо же, чтобы я ее встретил именно тогда, когда Наташина свадьба расстроилась, ну и потом всё… Да, вот что. Я никому не говорил этого и не скажу. А вам только.
Губернаторша пожала его благодарно за локоть.
– Вы знаете Софи, кузину? Я люблю ее, я обещал жениться и женюсь на ней… Поэтому вы видите, что про это не может быть и речи, – нескладно и краснея говорил Николай.
– Mon cher, mon cher, как же ты судишь? Да ведь у Софи ничего нет, а ты сам говорил, что дела твоего папа очень плохи. А твоя maman? Это убьет ее, раз. Потом Софи, ежели она девушка с сердцем, какая жизнь для нее будет? Мать в отчаянии, дела расстроены… Нет, mon cher, ты и Софи должны понять это.
Николай молчал. Ему приятно было слышать эти выводы.
– Все таки, ma tante, этого не может быть, – со вздохом сказал он, помолчав немного. – Да пойдет ли еще за меня княжна? и опять, она теперь в трауре. Разве можно об этом думать?
– Да разве ты думаешь, что я тебя сейчас и женю. Il y a maniere et maniere, [На все есть манера.] – сказала губернаторша.
– Какая вы сваха, ma tante… – сказал Nicolas, целуя ее пухлую ручку.


Приехав в Москву после своей встречи с Ростовым, княжна Марья нашла там своего племянника с гувернером и письмо от князя Андрея, который предписывал им их маршрут в Воронеж, к тетушке Мальвинцевой. Заботы о переезде, беспокойство о брате, устройство жизни в новом доме, новые лица, воспитание племянника – все это заглушило в душе княжны Марьи то чувство как будто искушения, которое мучило ее во время болезни и после кончины ее отца и в особенности после встречи с Ростовым. Она была печальна. Впечатление потери отца, соединявшееся в ее душе с погибелью России, теперь, после месяца, прошедшего с тех пор в условиях покойной жизни, все сильнее и сильнее чувствовалось ей. Она была тревожна: мысль об опасностях, которым подвергался ее брат – единственный близкий человек, оставшийся у нее, мучила ее беспрестанно. Она была озабочена воспитанием племянника, для которого она чувствовала себя постоянно неспособной; но в глубине души ее было согласие с самой собою, вытекавшее из сознания того, что она задавила в себе поднявшиеся было, связанные с появлением Ростова, личные мечтания и надежды.
Когда на другой день после своего вечера губернаторша приехала к Мальвинцевой и, переговорив с теткой о своих планах (сделав оговорку о том, что, хотя при теперешних обстоятельствах нельзя и думать о формальном сватовстве, все таки можно свести молодых людей, дать им узнать друг друга), и когда, получив одобрение тетки, губернаторша при княжне Марье заговорила о Ростове, хваля его и рассказывая, как он покраснел при упоминании о княжне, – княжна Марья испытала не радостное, но болезненное чувство: внутреннее согласие ее не существовало более, и опять поднялись желания, сомнения, упреки и надежды.
В те два дня, которые прошли со времени этого известия и до посещения Ростова, княжна Марья не переставая думала о том, как ей должно держать себя в отношении Ростова. То она решала, что она не выйдет в гостиную, когда он приедет к тетке, что ей, в ее глубоком трауре, неприлично принимать гостей; то она думала, что это будет грубо после того, что он сделал для нее; то ей приходило в голову, что ее тетка и губернаторша имеют какие то виды на нее и Ростова (их взгляды и слова иногда, казалось, подтверждали это предположение); то она говорила себе, что только она с своей порочностью могла думать это про них: не могли они не помнить, что в ее положении, когда еще она не сняла плерезы, такое сватовство было бы оскорбительно и ей, и памяти ее отца. Предполагая, что она выйдет к нему, княжна Марья придумывала те слова, которые он скажет ей и которые она скажет ему; и то слова эти казались ей незаслуженно холодными, то имеющими слишком большое значение. Больше же всего она при свидании с ним боялась за смущение, которое, она чувствовала, должно было овладеть ею и выдать ее, как скоро она его увидит.
Но когда, в воскресенье после обедни, лакей доложил в гостиной, что приехал граф Ростов, княжна не выказала смущения; только легкий румянец выступил ей на щеки, и глаза осветились новым, лучистым светом.
– Вы его видели, тетушка? – сказала княжна Марья спокойным голосом, сама не зная, как это она могла быть так наружно спокойна и естественна.
Когда Ростов вошел в комнату, княжна опустила на мгновенье голову, как бы предоставляя время гостю поздороваться с теткой, и потом, в самое то время, как Николай обратился к ней, она подняла голову и блестящими глазами встретила его взгляд. Полным достоинства и грации движением она с радостной улыбкой приподнялась, протянула ему свою тонкую, нежную руку и заговорила голосом, в котором в первый раз звучали новые, женские грудные звуки. M lle Bourienne, бывшая в гостиной, с недоумевающим удивлением смотрела на княжну Марью. Самая искусная кокетка, она сама не могла бы лучше маневрировать при встрече с человеком, которому надо было понравиться.