Interested Article - Космический корабль (конфигурация клеточного автомата)
- 2020-02-14
- 1
Косми́ческий кора́бль ( англ. spaceship ) — класс конфигураций в «Жизни» — созданной Конвеем модели клеточного автомата .
Описание
Конфигурация «Жизни» или другого клеточного автомата называется космическим кораблём , если через определённое количество поколений она вновь появляется без дополнений или потерь, но со смещением относительно исходного положения. Наименьшее такое число поколений — период космического корабля .
Первым обнаруженным космическим кораблём стал планер . Планер был найден во время отслеживания эволюции R-пентамино в 1970 году Ричардом Гаем .
Космический корабль периода p , который перемещается на ( m , n ) в течение его периода, где m ≥ n , имеет тип ( m , n ) / p . Как было доказано Конуэем в 1970 году, p ≥ 2 m + 2 n .
Космические корабли, движущиеся по горизонтали или вертикали, называются ортогональными кораблями . Если движение космического корабля происходит по диагонали под углом 45°, такой корабль называется диагональным . Космические корабли, движущиеся под другими углами, называются косыми или наклонными ( англ. oblique ). В 2010 году был сконструирован первый наклонный космический корабль типа (5120, 1024) / 33699586 .
Скорость
Скоростью света в заданном клеточном автомате называют наибольшую скорость распространения информации. Скорость света в «Жизни» равна скорости перемещения шахматного короля — скорости в одну клетку за поколение по горизонтали, вертикали или диагонали. Обычно скорость света обозначается буквой c .
Скорость космического корабля определяется отношением расстояния смещения к периоду. Часто скорость выражается через c . Так, скорость планера в «Жизни» равна c / 4, так как он перемещается на одну клетку по диагонали за четыре поколения . Простейший ортогональный космический корабль, ЛКК, движется со скоростью c / 2 .
В общем случае, если космический корабль в двумерном клеточном автомате на квадратной сетке перемещается на вектор ( x , y ) через n поколений, его скорость равна
Примеры
B3/S35
Следующие конфигурации являются ортогональными космическими кораблями в варианте «Жизни» — клеточном автомате с правилами B3/S35 (клетка рождается, если у неё три соседа, и выживает, если у неё три или пять соседей).
Связанные конфигурации
Тагалонг ( англ. tagalong «тянучка») — конфигурация, которая не является сама по себе космическим кораблём, но может быть присоединена к космическому кораблю, чтобы сформировать новый космический корабль . Другими словами, тагалонг — это часть космического корабля, которую можно удалить без разрушения корабля .
Тагалонг, расположенный перед космическим кораблём, называют пушалонгом ( англ. pushalong «толкушка») .
Конфигурация, способная изменять направление движения космического корабля, не разрушаясь при этом, называется отражателем ( англ. ).
Ружьё ( англ. ) — неподвижная конфигурация, периодически выпускающая космический корабль .
Значение
Космические корабли могут использоваться для передачи информации. Способность планера переносить информацию стала частью доказательства, что «Жизнь» является тьюринг-полной .
Примечания
- ↑ Клумова И. Н. // Квант . — 1974. — № 9 . — С. 26—30 . 4 марта 2016 года.
- ↑ . Словарь Жизни. Дата обращения: 10 августа 2013. 11 октября 2012 года.
- . Словарь Жизни. Дата обращения: 10 августа 2013. 10 октября 2012 года.
- . Словарь Жизни. Дата обращения: 10 августа 2013. 10 февраля 2013 года.
- Не путать с от 9 февраля 2013 на Wayback Machine (ship) — устойчивой конфигурацией.
- ↑ . Словарь Жизни. Дата обращения: 10 августа 2013. 9 февраля 2013 года.
- ↑ . Словарь Жизни. Дата обращения: 10 августа 2013. 8 февраля 2013 года.
- . ConwayLife.com. Дата обращения: 10 августа 2013. 24 августа 2013 года.
- . Game of Life News (19 мая 2010). Дата обращения: 10 августа 2013. 1 июня 2013 года.
- . Словарь Жизни. Дата обращения: 10 августа 2013. 10 октября 2012 года.
- ↑ . ConwayLife.com. Дата обращения: 10 августа 2013. 30 июля 2013 года.
- . Словарь Жизни. Дата обращения: 10 августа 2013. 10 февраля 2013 года.
- . Eric Weisstein's Treasure Trove of Life C.A.. Дата обращения: 10 августа 2013. 22 апреля 2015 года.
- . Словарь Жизни. Дата обращения: 10 августа 2013. 6 мая 2019 года.
- . Словарь Жизни. Дата обращения: 10 августа 2013. 9 февраля 2013 года.
- Paul Chapman. (11 ноября 2002). Дата обращения: 12 июля 2009. 6 сентября 2009 года.
- Berlekamp, E. R. ; Conway, John Horton ; Guy, R.K. (2001–2004), Winning Ways for your Mathematical Plays (англ.) (2nd ed.), A K Peters Ltd, ISBN 978-1-56881-130-7
Ссылки
- Николай Белюченко. . 10 октября 2012 года.
- Stephen A. Silver. . 26 мая 2013 года.
- Николай Белюченко. . 3 октября 2012 года.
- David I. Bell. .
- David Eppstein. .
- Achim Flammenkamp. . — корабли, появляющиеся в случайных конфигурациях .
- . Game of Life News.
- 2020-02-14
- 1