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

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

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

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

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

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

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

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