Просмотр кода страницы Элементарный клеточный автомат

[[Файл:Rule30rand.png|right|thumb|[[Правило 30]] на случайной конфигурации]]
'''Элементарный клеточный автомат''' — это [[клеточный автомат]] с одномерным массивом ячеек в форме бесконечной в обе стороны ленты, который имеет два возможных состояния ячеек (0 и 1, «мёртвые» и «живые», «пустые» и «заполненные») и правило для определения состояния ячейки на следующем шаге, использующее только состояние ячейки и её двух соседей на текущем шаге. В целом такие автоматы являются одними из наиболее простых возможных клеточных автоматов, однако при некоторых правилах они показывают сложное поведение; так, использование [[Правило 110|правила 110]] приводит к [[Полнота по Тьюрингу|полному по Тьюрингу]] автомату.

== Код Вольфрама ==
[[Файл:Rule110rand.png|right|thumb|[[Правило 110]] на случайной конфигурации]]
Всего существует <math>8=2^3</math> возможных комбинаций состояния ячейки и состояний её двух соседей. Правило, определяющее элементарный клеточный автомат, должно указывать следующее состояние (0 или 1) для каждого из этих возможных случаев, поэтому всего правил <math>256 = 2^8</math>. [[Вольфрам, Стивен|Стивен Вольфрам]] предложил схему нумерации этих правил, известную как '''код Вольфрама''' ({{lang-en|Wolfram code}}), которая сопоставляет каждому правилу число от 1 до 255. Эта система была впервые опубликована Вольфрамом в статье 1983 года<ref>{{статья |заглавие=Statistical Mechanics of Cellular Automata |издание=[[Reviews of Modern Physics]] |том=55 |страницы=601—644 |doi=10.1103/RevModPhys.55.601 |bibcode=1983RvMP...55..601W |язык=en |автор=Wolfram, Stephen |месяц=7 |год=1983 |тип=journal}}</ref> и позднее использовалась в его книге «[[A New Kind of Science]]» ({{lang-en|Наука нового типа}}).<ref>Wolfram, Stephen, ''[[A New Kind of Science]]''. Wolfram Media, Inc., May 14, 2002. {{ISBN|1-57955-008-8}}</ref>

Для получения кода Вольфрама нужно записать в убывающем порядке возможные конфигурации (111, 110, …, 001, 000), выписать под ними соответствующие состояния и интерпретировать получившуюся последовательность нулей и единиц как число в [[Двоичная система счисления|двоичной системе счисления]]. Например, следующая схема приводит к коду <math>110_{10}=01101110_2</math>, соответствующему [[Правило 110|правилу 110]]:

{| class="wikitable" style="text-align: center"
|-
! текущие состояния
| 111
| 110
| 101
| 100
| 011
| 010
| 001
| 000
|-
! будущее состояние
| 0
| 1
| 1
| 0
| 1
| 1
| 1
| 0
|}

== Отражения и дополнения ==
Некоторые из 256 правил тривиальным образом эквивалентны друг другу благодаря наличию двух видов преобразований. Первый — это отражение относительно вертикальной оси, при котором левый и правый соседи меняются местами и получается '''зеркальное правило''' ({{lang-en|mirrored rule}}). Например, правило 110 становится правилом 124:
{| class="wikitable" style="text-align: center"
|-
! текущие состояния
| 111
| 110
| 101
| 100
| 011
| 010
| 001
| 000
|-
! будущее состояние
| 0
| 1
| 1
| 1
| 1
| 1
| 0
| 0
|}

Среди 256 правил есть 64 '''зеркально-симметричных''' ({{lang-en|amphichiral}}).

Второй вид преобразований — это замена ролей 0 и 1 в определении, дающее '''дополнительное правило''' ({{lang-en|complementary rule}}). Например, правило 118 становится правилом 137:
{| class="wikitable" style="text-align: center"
|-
! текущие состояния
| 111
| 110
| 101
| 100
| 011
| 010
| 001
| 000
|-
! будущее состояние
| 1
| 0
| 0
| 0
| 1
| 0
| 0
| 1
|}

Всего 16 правил из 256 совпадают со своими дополнениями. С точностью до этой пары преобразований (в том числе применённой одновременно — порядок не важен), существует 88 неэквивалентных элементарных клеточных автоматов.<ref>[http://atlas.wolfram.com/01/01/views/10/TableView.html Elementary Cellular Automata. Rule properties:Equivalent rules] {{Wayback|url=http://atlas.wolfram.com/01/01/views/10/TableView.html |date=20170816051705 }} в «Wolfram Atlas of Simple Programs»</ref>

== Методы исследования ==

=== Простейшая конфигурация ===
[[Файл:R090 pulse wide.png|right|thumb|[[Правило 90]] на простейшей конфигурации]]
Один из методов исследования элементарных клеточных автоматов — рассмотреть эволюцию простейшей начальной конфигурации, то есть состоящей всего из одной живой (содержащей 1) клетки. Если правило имеет чётный код Вольфрама, то не происходит самопроизвольного зарождения жизни (комбинация 000 не даёт посередине 1 в следующем поколении), а потому каждое состояние простейшей конфигурации имеет конечное число ненулевых ячеек и может быть проинтерпретировано как число в двоичной записи.{{как?}} Последовательность этих чисел задаёт [[Метод производящих функций|производящую функцию]], которая является [[Рациональная функция|рациональной]], то есть отношением двух [[многочлен]]ов, и часто имеет относительно простой вид.

=== Случайные конфигурации ===
Также полезно рассмотреть эволюцию случайных начальных конфигураций. Для этого существует разделение на следующие неформальные [[классы клеточных автоматов]], придуманное Вольфрамом:<ref>Stephan Wolfram, ''[[A New Kind of Science]]'', p. 223.</ref>
* Класс 1: Быстро сходится к состоянию из одних нулей или единиц. Вольфрам приводит как примеры правила 0, 32, 160, 232.
* Класс 2: Быстро сходится к [[Осциллятор (конфигурация клеточного автомата)|циклическому]] или [[Натюрморт (конфигурация клеточного автомата)|стабильному]] состоянию. Например, правила 4, 108, 218, 250.
* Класс 3: Сохраняется в случайном состоянии. Например, правила 22, [[Правило 30|30]], 126, 150, 182.
* Класс 4: Образуются как области с циклическими или стабильными состояниями, так и структуры, которые взаимодействуют друг с другом сложными способами. Примером является [[правило 110]], являющееся [[Полнота по Тьюрингу|полным по Тьюрингу]].

==== Неоднозначные случаи ====
{{Кратное изображение
 |зона           = right
 |направление    = horizontal
 |заголовок      = Примеры со случайной конфигурацией

 |изобр1         = Rule62rand.png|
 |ширина1        = 100
 |подпись1       = Правило 62

 |изобр2         = Rule73rand.png
 |ширина2        = 100
 |подпись2       = Правило 73

 |изобр3         = Rule54rand.png
 |ширина3        = 100
 |подпись3       = Правило 54
}}
Некоторые правила нельзя однозначно отнести к одному из классов, например:

* 62: случайные структуры взаимодействуют сложным образом, однако склонны уничтожать друг друга; в результате, если начинать со случайной конфигурации, то первое время будет проявляться поведение, свойственное классу 4, но в конце с большой вероятностью окажется циклическое или стабильное состояние, как у автоматов класса 2.
* 73: комбинация 0110 сохраняется в следующих поколениях, что создаёт стены, блокирующие передвижение информации; это приводит к повторению комбинаций между стенами, то есть как поведению класса 2; однако запрет начальных комбинаций с блоками из чётного числа подряд идущих нулей и единиц приводит к поведению, типичному для автоматов класса 3.
* 54: класс 4, но полнота по Тьюрингу неизвестна.

== Примечания ==
{{примечания}}

== Ссылки ==
{{Навигация}}
* [http://atlas.wolfram.com/01/01 Элементарные клеточные автоматы] в «Wolfram Atlas of Simple Programs»

{{Conway's Game of Life}}
{{Нет источников |дата=2024-10-21}}

[[Категория:Элементарные клеточные автоматы| ]]
[[Категория:Клеточные автоматы]]