Черви Патерсона

Черви Па́терсона (англ. Paterson's worms) — семейство клеточных автоматов типа тьюрмитов, придуманное в 1971 году британским учёным Майком Патерсоном (англ. Mike Paterson) для моделирования поведения и кормёжки некоторых доисторических червей. Несмотря на простой набор правил, поведение автоматов может быть очень сложным, и для одного из наборов правил его судьба неизвестна.

Предыстория

Ископаемые пути червей.

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

В 1969 году Дэвид Рауп (англ. David Raup) и Адольф Зейлахер создали компьютерную симуляцию ископаемых следов червей, что вдохновило Патерсона и Джона Конвея на поиск простых моделей клеточных автоматов для исследования идеализированных червей на решётке. Конвей предлагал исследовать червей на квадратной решётке, однако там были всего три вида червей с довольно скучным поведением, а Патерсон предложил использовать треугольную решётку.

Описание

В этой модели червь ползает по треугольной решётке, грани которой изображают еду, и при прохождении грани она закрашивается («съедается»). В каждой вершине червь выбирает, вдоль какой грани направиться, исходя из того, какие из шести граней, примыкающих к вершине, закрашены. Направления отсчитываются с точки зрения червя. Червь умирает, если в вершине нет незакрашенных («несъеденных») граней, что, впрочем, возможно только в начальном состоянии из соображений чётности.

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

Нумерация правил

Нумерация направлений — червь движется от левого края к центру.

Червь Патерсона с правилом { 2, 2, 0 }

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

Например, правило {2, 2, 0}, задающее червя, изображённого справа, говорит, что при первых двух выборах (все 5 направлений незакрашены) червь поворачивает направо-назад, а при третьем (закрашено направление направо-назад и закрашены направления налево-вперёд, налево-назад и направо назад соответственно) выбирает движение прямо. Дальшейшие выборы не указаны, поскольку червь третий раз возвращается в начало и умирает. Если ограничиться случаями, в которых червь делает первый поворот направо, то потенциально существует 1296 возможных правил. Однако с учётом того, что червь часто умирает, не успев осуществить все возможные выборы, а потому нет смысла отличать эти правила, их остаётся всего 412. Среди них 336 конечны, 73 бесконечны и циклически повторяются со сдвигом, для двух бесконечность не доказана, но предполагается (это правила {1,0,4,2,0,2,0} и {1,0,4,2,0,1,5}), а поведение ещё одного неизвестно (правило {1,0,4,2,0,1,5}).