Loading AI tools
Из Википедии, свободной энциклопедии
Элементарный клеточный автомат — это клеточный автомат с одномерным массивом ячеек в форме бесконечной в обе стороны ленты, который имеет два возможных состояния ячеек (0 и 1, «мёртвые» и «живые», «пустые» и «заполненные») и правило для определения состояния ячейки на следующем шаге, использующее только состояние ячейки и её двух соседей на текущем шаге. В целом такие автоматы являются одними из наиболее простых возможных клеточных автоматов, однако при некоторых правилах они показывают сложное поведение; так, использование правила 110 приводит к полному по Тьюрингу автомату.
Всего существует возможных комбинаций состояния ячейки и состояний её двух соседей. Правило, определяющее элементарный клеточный автомат, должно указывать следующее состояние (0 или 1) для каждого из этих возможных случаев, поэтому всего правил . Стивен Вольфрам предложил схему нумерации этих правил, известную как код Вольфрама (англ. Wolfram code), которая сопоставляет каждому правилу число от 1 до 255. Эта система была впервые опубликована Вольфрамом в статье 1983 года[1] и позднее использовалась в его книге «A New Kind of Science» (англ. Наука нового типа).[2]
Для получения кода Вольфрама нужно записать в убывающем порядке возможные конфигурации (111, 110, …, 001, 000), выписать под ними соответствующие состояния и интерпретировать получившуюся последовательность нулей и единиц как число в двоичной системе счисления. Например, следующая схема приводит к коду , соответствующему правилу 110:
текущие состояния | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
будущее состояние | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Некоторые из 256 правил тривиальным образом эквивалентны друг другу благодаря наличию двух видов преобразований. Первый — это отражение относительно вертикальной оси, при котором левый и правый соседи меняются местами и получается зеркальное правило (англ. mirrored rule). Например, правило 110 становится правилом 118:
текущие состояния | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
будущее состояние | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
Среди 256 правил есть 64 зеркально-симметричных (англ. amphichiral).
Второй вид преобразований — это замена ролей 0 и 1 в определении, дающее дополнительное правило (англ. complementary rule). Например, правило 118 становится правилом 137:
текущие состояния | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
будущее состояние | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
Всего 16 правил из 256 совпадают со своими дополнениями. С точностью до этой пары преобразований (в том числе применённой одновременно — порядок не важен), существует 88 неэквивалентных элементарных клеточных автоматов.[3]
Один из методов исследования элементарных клеточных автоматов — рассмотреть эволюцию простейшей начальной конфигурации, то есть состоящей всего из одной живой (содержащей 1) клетки. Если правило имеет чётный код Вольфрама, то не происходит самопроизвольного зарождения жизни (комбинация 000 не даёт посередине 1 в следующем поколении), а потому каждое состояние простейшей конфигурации имеет конечное число ненулевых ячеек и может быть проинтерпретировано как число в двоичной записи.[как?] Последовательность этих чисел задаёт производящую функцию, которая является рациональной, то есть отношением двух многочленов, и часто имеет относительно простой вид.
Также полезно рассмотреть эволюцию случайных начальных конфигураций. Для этого существует разделение на следующие неформальные классы клеточных автоматов, придуманное Вольфрамом:[4]
Некоторые правила нельзя однозначно отнести к одному из классов, например:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.