Космический корабль (клеточный автомат)

Поколение 0 Население 38

Ортогональные космические корабли в «Игре жизни Конвея» с разной скоростью (все они были известны по состоянию на 2009 год, за исключением «гусеницы» 17c/45). Обратите внимание, что некоторые космические корабли «обгоняют» другие из-за разницы в скорости.

В клеточном автомате конечный шаблон называется космическим кораблем , если он появляется через определенное количество поколений в той же ориентации, но в другом положении. Наименьшее такое число поколений называется периодом космического корабля.

Описание

Скорость космического корабля часто выражают через c , метафорическую скорость света (одна клетка на поколение), которая во многих клеточных автоматах является самой быстрой скоростью распространения эффекта. Например, говорится, что планер в «Игре жизни» Конвея имеет скорость $c/4$, поскольку для перевода данного состояния в одну ячейку требуется четыре поколения. Точно так же говорят, что легкий космический корабль имеет скорость $c/2$, поскольку для перевода данного состояния двумя ячейками требуется четыре поколения. В более общем смысле, если космический корабль в двумерном автомате с окрестностью Мура переводится как $(x,y)$ после $n$ поколений, то скорость $v$ определяется как:

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

Эти обозначения можно легко обобщить на клеточные автоматы с размерностью, отличной от двух.

Вытягивание — это узор, который сам по себе не является космическим кораблем, но его можно прикрепить к задней части космического корабля, чтобы сформировать космический корабль большего размера. Точно так же толкатель впереди размещается . Термин «тагалонг» может относиться как к любому из этих узоров, так и к узору, который можно разместить на борту космического корабля, чтобы сформировать более крупный космический корабль.

Шаблон, который при вводе космического корабля выводит копию космического корабля, движущегося в другом направлении, называется отражателем . Если вместо этого на выходе получается другой космический корабль, шаблон известен как конвертер.

Космические корабли важны, потому что иногда их можно модифицировать для производства пуховиков . Космические корабли также могут использоваться для передачи информации . Например, в «Игре жизни » Конвея способность планера ( простейшего космического корабля Жизни) передавать информацию является частью доказательства того, что Жизнь полна по Тьюрингу .

В марте 2016 года неожиданное открытие небольшого, но высокопериодического космического корабля привело в восторг сообщество Game of Life. Его назвали «медноголовым». Похожий пример, под названием «бездельник», был найден несколькими годами ранее.

В марте 2018 года был обнаружен первый элементарный космический корабль водоизмещением (2,1) ( рыцарское ) и назван Сэр Робин.

Внешние ссылки

• Космические корабли в «Игре жизни Конвея» Дэвида И. Белла
• Планеры в «Жизнеподобных клеточных автоматах» Дэвида Эппштейна