Косми́ческий кора́бль ( англ. 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 поколений, его скорость равна

${\displaystyle v={\frac {\max \left(|x|,|y|\right)}{n}}\,c}$

Примеры

B3/S35

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

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

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

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

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

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

Значение

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

Примечания

Ссылки

• Николай Белюченко. (неопр.) . 10 октября 2012 года.
• Stephen A. Silver. (неопр.) . 26 мая 2013 года.
• Николай Белюченко. (неопр.) . 3 октября 2012 года.
• David I. Bell. (неопр.) .
• David Eppstein. (неопр.) .
• Achim Flammenkamp. (неопр.) . — корабли, появляющиеся в случайных конфигурациях.
• (неопр.) . Game of Life News.