Космические корабли в клеточных автоматах: периодически перемещающиеся паттерны. Определение, период, скорость (с) и примеры – планер и лёгкий корабль.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Тип узора, периодически меняющий своё положение.
Type of pattern that periodically changes position
В клеточном автомате конечный узор называется космическим кораблём, если он повторно появляется через определённое число поколений в той же ориентации, но в другом месте. Наименьшее такое число поколений называется периодом космического корабля.
In a cellular automaton, a finite pattern is called a spaceship if it reappears after a certain number of generations in the same orientation but in a different position. The smallest such number of generations is called the period of the spaceship.
Описание
Скорость космического корабля часто выражается в терминах *c*, метафорической скорости света (одна клетка за поколение), которая во многих клеточных автоматах является максимальной скоростью распространения эффекта. Например, глайдер в игре Конвея "Жизнь" имеет скорость , так как для смещения данного состояния на одну клетку требуется четыре поколения. Аналогично, лёгкий космический корабль имеет скорость , поскольку для смещения данного состояния на две клетки требуется четыре поколения. В более общем случае, если космический корабль в 2D-автомате с районом Мура смещается на после поколений, то скорость определяется как:
The speed of a spaceship is often expressed in terms of c, the metaphorical speed of light (one cell per generation) which in many cellular automata is the fastest that an effect can spread. For example, a glider in Conway's Game of Life is said to have a speed of , as it takes four generations for a given state to be translated by one cell. Similarly, the lightweight spaceship is said to have a speed of , as it takes four generations for a given state to be translated by two cells. More generally, if a spaceship in a 2D automaton with the Moore neighborhood is translated by after generations, then the speed is defined as:
Это обозначение легко обобщается на клеточные автоматы с размерностью, отличной от двух. Пуллалонг – это паттерн, который сам по себе не является космическим кораблём, но может быть прикреплён к задней части космического корабля для формирования более крупного корабля. Аналогично, пушалонг помещается впереди. Термин тагалонг может относиться к любому из этих паттернов или к паттерну, который можно поместить сбоку от космического корабля для формирования более крупного корабля. Паттерн, который при вводе космического корабля выдаёт копию этого корабля, движущуюся в другом направлении, называется отражателем. Если на выходе вместо этого получается другой космический корабль, паттерн известен как преобразователь. Космические корабли важны, поскольку их иногда можно модифицировать для создания пуфферов. Космические корабли также могут использоваться для передачи информации. Например, в игре Конвея "Жизнь" способность глайдера (самого простого космического корабля в "Жизни") передавать информацию является частью доказательства того, что "Жизнь" является Тьюринг-полной. В марте 2016 года неожиданное открытие небольшого, но высокопериодического космического корабля взволновало сообщество "Игры Жизни". Его назвали "медноголовым". Похожий пример, "лоафер", был найден за несколько лет до этого. В марте 2018 года был обнаружен первый элементарный космический корабль со смещением (2,1) (коньковым ходом) и назван Сэром Робином.
This notation can be readily generalised to cellular automata with dimensionality other than two. A pullalong is a pattern that is not a spaceship in itself but that can be attached to the back of a spaceship to form a larger spaceship. Similarly, a pushalong is placed at the front. The term tagalong can refer to either of these patterns or a pattern that can be placed at the side of a spaceship to form a larger spaceship. A pattern that, when a spaceship is input, outputs a copy of the spaceship travelling in a different direction is called a reflector. If the output is instead a different spaceship, the pattern is known as a converter. Spaceships are important because they can sometimes be modified to produce puffers. Spaceships can also be used to transmit information. For example, in Conway's Game of Life, the ability of the glider (Life's simplest spaceship) to transmit information is part of a proof that Life is Turing complete. In March 2016, the unexpected discovery of a small but high period spaceship enthused the Game of Life community. It was named "copperhead". A similar example, called "loafer", was found a few years earlier. In March 2018, the first elementary spaceship with displacement (2,1) (knightwise) was discovered and named Sir Robin.