Текущая версия на 19:13, 4 сентября 2022

Содержание

1 Базовые определения
2 Классификация клеточных автоматов
- 2.1 Классификация Вольфрама
- 2.2 Классификация Эпштейна
3 Одномерные клеточные автоматы
- 3.1 Коды Вольфрама
4 Клеточные автоматы на двумерной решетке
- 4.1 Игра «Жизнь»
  - 4.1.1 Состояния и правила переходов
  - 4.1.2 Основные элементы
- 4.2 Wireworld
5 Самовоспроизводящиеся клеточные автоматы
- 5.1 Автомат фон Неймана
- 5.2 Автомат Лэнгтона
  - 5.2.1 Состояния
    - 5.2.1.1 Сигнальные состояния
    - 5.2.1.2 Служебные состояния
  - 5.2.2 Принцип работы
6 Тьюрмиты
7 См.также
8 Литература

Базовые определения

Определение:

Клеточный автомат^[1] представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии.

Множество состояний $Q$, обозначим состояние ячейки $i$ как $s[i]$.
Изначально все ячейки находятся в состоянии $B \in Q$, кроме ячеек с номерами от $1$ до $n$. Ячейка с номером $i$, где $1 \le i \le n$ находится в состоянии $x_i$, где $x$ - входное слово (будем считать, что $\Sigma \subset Q$, $B \notin \Sigma$).

Правила работы клеточного автомата такие: задано число $d$ и функция $f : Q^{2d+1} \to Q$. За один шаг все клетки меняют состояние по следующему правилу: новое состояние клетки $i$ равно $f(s[i - d], s[i - d + 1], \ldots, s[i + d - 1], s[i + d])$. Если клетка с номером $0$ переходит в состояние $Y$, то автомат допускает слово $x$.

Определение и основные свойства линейного клеточного автомата содержатся в статье "линейный клеточный автомат, эквивалентность МТ".

Определение:

Окрестность Мура^[2] ячейки — совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой.
Окрестность Мура порядка в двумерном случае представляет собой квадрат со стороной ^[3].

Определение:

Окрестность фон Неймана^[4] ячейки — совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону (грань) с данной ячейкой.

Классификация клеточных автоматов

Классификация Вольфрама

Определение:

Классы Вольфрама^[5] — классификация клеточных автоматов, основанная на их поведении.

Классы, предложенные С. Вольфрамом^[6]

Классификация Эпштейна

На ряд серьезных недостатков классификации С. Вольфрама указывал^[7] Д. Эпштейн.
Один из них состоял в невозможности за разумное время проверить принадлежность клеточного автомата к какому-либо классу для большого числа клеточных автоматов.
В свою очередь он предложил систему классификации двухмерных двоичных клеточных автоматов, призванную выделять кандидатов в универсальные клеточные автоматы.

Классы, предложенные Д. Эпштейном^[6]

Однако, данная классификация так же имела серьезные проблемы, и, в конечном счете, не удовлетворяла своему назначению. Более подробные описания данных классификаций, а также других наиболее распространенных, можно найти в работе П.С. Скакова^[6]. В ней, в том числе, были выделены основные достоинства и недостатки различных классификаций, и предложена новая, являющаяся уточнением и модификацией существующих и решающая многие их проблемы.

Одномерные клеточные автоматы

Коды Вольфрама

Определение:

Код Вольфрама — система именования клеточных автоматов (как правило, ЛКА), предложенная С. Вольфрамом в 1983 году^[8].
Данная система основана на наблюдении, что таблица, определяющая новое состояние каждой ячейки в автомате, как функция состояний в его окрестности, может интерпретироваться как число из -цифр в -арной позиционной системе счисления, где — число состояний, которое может иметь каждая ячейка в автомате, — число конфигураций окрестности, а — радиус окрестности.

В соответствии с определением, код может быть вычислен следующим образом:

Определить все возможные конфигурации окрестности данной ячейки;
Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию;
Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с правилами переходов на следующей итерации;
Интерпретируя полученный список состояний как [math]S[/math]-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама.

Далее в статье будут приведены наиболее известные правила.
Во всех случаях рассматриваются ЛКА с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге.

Правило 30

Определение:

Правило 30 — ЛКА с двумя состояниями (0 и 1).

Эволюция клеточного автомата по Правилу 30

Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние:

Текущее состояние трёх соседних клеток	111	110	101	100	011	010	001	000
Новое состояние центральной клетки	0	0	0	1	1	1	1	0

Так как [math]11110_2 = {30}_{10}[/math], данное правило называется Правилом 30.

Правило 90

Определение:

Правило 90 — ЛКА с двумя состояниями (0 и 1).
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.

Эволюция клеточного автомата по Правилу 90

Правила перехода для Правила 90:

Текущее состояние трёх соседних клеток	111	110	101	100	011	010	001	000
Новое состояние центральной клетки	0	1	0	1	1	0	1	0

Так как [math]1011010_2 = {90}_{10}[/math], данное правило называется Правилом 90.

Правило 110

Определение:

Правило 110 — ЛКА с двумя состояниями (0 и 1).
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.

Эволюция клеточного автомата по Правилу 110

Правила перехода для Правила 110:

Текущее состояние трёх соседних клеток	111	110	101	100	011	010	001	000
Новое состояние центральной клетки	0	1	1	0	1	1	1	0

Так как [math]1101110_2 = {110}_{10}[/math], данное правило называется Правилом 110.

Правило 184

Определение:

Правило 184 — ЛКА с двумя состояниями (0 и 1).

Эволюция клеточного автомата по Правилу 184

Правила перехода для Правила 184:

Текущее состояние трёх соседних клеток	111	110	101	100	011	010	001	000
Новое состояние центральной клетки	1	0	1	1	1	0	0	0

Так как [math]110111000_2 = {184}_{10}[/math], данное правило называется Правилом 184.

Клеточные автоматы на двумерной решетке

Игра «Жизнь»

Некоторые из приведенных далее определений были взяты с этого^[9] сайта, а также со смежных с нем страниц.

Определение:

«Жизнь» — клеточный автомат, представляющий из себя бесконечное клетчатое поле, каждая клетка может быть белой или черной. Состояние, в которое перейдет клетка на следующем шаге, зависит от состояний ее соседей в окрестности Мура.

Основную информацию по игре вы можете найти в статье "игра «Жизнь»". В данном разделе будут рассмотрены лишь основные типы и примеры конфигураций данной игры.

Состояния и правила переходов

Название состояния	Цвет	Переходит в cостояние
«Живая клетка»	Белый	«мертвая клетка», если имеет ровно меньше двух или больше трех соседей в состоянии «живая клетка».
«Мертвая клетка»	Черный	«живая клетка», если имеет ровно трех соседей в состоянии «живая клетка».

Основные элементы

В данном разделе используются термины из «Словаря Жизни»^[10].

TODO: ADD PICTURES

Устойчивые фигуры

Определение:

Устойчивый образец — объект, который является собственным родителем.

Определение:

Натюрморт^[11] — устойчивый объект, являющийся конечным и непустым, из которого нельзя выделить непустую устойчивую часть.

Определение:

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

Долгожители

Определение:

Долгожитель — конфигурация из 10 или меньшего числа клеток, которым необходимо не менее 50 поколений для стабилизации^[12].

Осцилляторы

Определение:

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

Определение:

Период осциллятора — минимальное число поколений, через которое осциллятор возвращается в исходное состояние.

Двигающиеся фигуры

Определение:

Космический корабль — конфигурация, которая через определённое количество поколений вновь появляется без дополнений или потерь, но со смещением относительно исходного положения.

Определение:

Период космического корабля — минимальное число поколений, за которое космический корабль смещается.

Ружья

Определение:

Ружье — класс конфигураций, у которых основная часть циклически повторяется, как у осцилляторов, а также периодически создаёт космические корабли, которые удаляются от ружья. Данная конфигурация имеет два периода: период создания космических кораблей и период повторения состояний ружья.

Паровозы

Определение:

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

Определение:

Грабли — паровозы, оставляющие за собой след исключительно из космических кораблей.

Пожиратели

Определение:

Пожиратель — конфигурация, способная уничтожить космический корабль и восстановиться после контакта.

Отражатели

Определение:

Отражатель — натюрморт или периодическая конфигурация, способная изменить направление движения другой фигуры определенного типа на 90° или 180°, восстанавливая свою структуру после отражения.

Определение:

Время восстановления отражателя — минимальное число поколений, которое должно проходить между столкновением с другими фигурами, чтобы отражатель успевал восстановиться.

Размножители

Определение:

Размножитель — конфигурация, растущая квадратично, производя множество копий вторичной конфигурации, каждая из которых производит множество копий третичной конфигурации.

Существует несколько видов^[13] размножителей, отличающихся между собой относительной подвижностью полученных конфигураций. Виды кодируются при сочетаниями трех букв, описывающие, соответственно, первичную, вторичную и третичную конфигурации: Д — движущаяся, Н — неподвижная:

НДД — ружьё, вырабатывающее грабли;
ДНД — паровоз, вырабатывающий ружья;
ДДН — грабли, вырабатывающий паровозы;
ДДД — грабли, вырабатывающий грабли.

Wireworld

Определение:

Клеточный автомат Wireworld^[14] представляет собой синхронный автомат с двумерной решеткой из квадратов, каждая клетка которой может находиться в одном из четырех состояний.

Состояния и правила переходов

Название состояния	Цвет	Переходит в состояние
Пустая клетка	Черный
Проводник	Желтый	«голова электрона», если имеет ровно одного или двух соседей в состоянии «голова электрона»
Голова электрона	Красный	«хвост электрона»
Хвост электрона	Синий	«проводник»

Общие закономерности

Движение "электрона" в "цепи" происходит со следующими закономерностями:

При прохождении электроном разветвления "цепи", в каждое из новых направлений уходит по "электрону";
При одновременном столкновении трёх и более "электронов", они исчезают.
При толщине "провода" больше $2$, "электроны" начинают двигаться хаотично.

Основные элементы

В данной статье приведены лишь основные простейшие элементы, которые можно составить в Wireworld.
Большое количество примеров приведено в Mirek's Cellebration^[15] и Zillions of Games^[16], WireWorld^[17]; с помощью элементов Wireworld также был построен^[18] компьютер.

Тактовый генератор

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

Тактовый генератор

Диод

Данный элемент действует точно так же, как одноименный элемент^[19] электрической цепи.

Диод

Логические элементы OR, XOR и NAND

Данный элемент действует точно так же, как и одноименные логические элементы^[20]^[21]^[22].

OR
XOR
NAND

Самовоспроизводящиеся клеточные автоматы

В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов, которые подробно описаны в книге "Физика процессов эволюции"^[23]:
«

Логическая универсальность.
1. При каких условиях определенный класс автоматов логически универсален?
2. Существует ли логически универсальный автомат?
Конструируемость.
1. Может ли один автомат быть построен другим автоматом?
2. Какой класс автоматов может быть построен каким-то автоматом?
Конструктивная универсальность.
1. Существует ли конструктивно универсальный автомат? (т. е. автомат, способный построить любой автомат)
Самовоспроизведение.
1. Существует ли самовоспроизводящийся автомат?
2. Существует ли автомат, который, помимо самовоспроизведения, может решать и другие задачи?
Эволюция.
1. Может ли при конструировании автомата автоматом происходить усложнение типа автомата?
2. Может ли такая эволюция происходить в направлении от менее эффективного к более эффективному автомату? (при надлежащем определении понятия эффективности)

».

В то время, как Тьюринг доказал, что машина Тьюринга является логически универсальной, Дж. фон Нейман построил автомат^[24], удовлетворяющий всем пяти свойствам. Одна из таких моделей будет описана далее.

Автомат фон Неймана

Определение:

Автомат фон Неймана (клеточная модель самовоспроизведения^[25]) — объект, представляющий собой поле, в каждой клетке которого находится конечный автомат с 29 состояниями.

Состояния

Определим соседей клетки с помощью векторов, установив в координат рассматриваемую клетку:

Окрестность фон Неймана: ;
Клетки, дополняющие окрестность фон Неймана до окрестности Мура:

Состояние клетки $\vartheta$ на $t$-ом шаге: — функция переходов.

Состояния клеток рассматриваемого автомата делятся на $4$ различных класса:
1. Основное состояние [math]U[/math] (невозбужденное).
2. Транзитивные состояния [math]T_{u\alpha\varepsilon}[/math], где:

— выходное направление (вправо, вверх, влево, вниз);

3. Конфлюэнтные состояния , где:

4. Чувствительные состояния $S, \; S_0 \;, S_{00} \;, S_{01} \;, S_{000} \;, S_1 \;, S_{10} \;, S_{11}$.

Далее объясним природу вышеперечисленных состояний. Для достижения поставленных целей, Дж. фон Нейман проводит^[25] аналогию с системой нейронных связей, аналогичным образом строя автомат.

Для передачи информации между клетками по цепочке из клеток же вводятся состояния $T$, причем наличие нейронного импульса регулируется параметром $\varepsilon$. Так как передача должна быть направленным процессом, вводится параметр $\alpha$, обозначающий, с какого направления клетка в данном состоянии будет принимать импульс.

Работу самих нейронов представляют состояния $С$: каждый нейрон имеет один "выход" и два "входа" (стороны клетки), которые для возбуждения необходимо раздражать одновременно, то есть у "нейрона" должно быть не менее двух соседей в окрестности фон Неймана в состоянии $T_1$, выходные направления которых ориентированы на "нейрон". Для экономии количества состояний вводится условность, что каждая сторона клетки может быть как "входом", так и "выходом" нейрона.

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

Состояния $S_{\Sigma0}$ и $S_{\Sigma1}$ используются для совершения прямого (возбуждение невозбужденных клеток) и обратного (приведение к покою возбужденных клеток) процессов.

Правила переходов

Функция переходов $F$ определяется следующими соотношениями:

Клетка в состоянии $T_{u\alpha\varepsilon}$ перейдет в состояние:
1. $U$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u'{\alpha}'{\vartheta}'}$;
2. $T_{u{\alpha}1}$, если пункт $1.1$ не выполнен, и среди ее соседей найдется клетка, удовлетворяющая одному из условий:
  1. ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'} \neq -v^\alpha$ в состоянии $T_{u{\alpha}'1}$;
  2. ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{\beta} \neq -v^\alpha, \; \beta = 0,\dots, 3$ в состоянии $C_1$;
3. $T_{u{\alpha}0}$ во всех остальных случаях.
Клетка в состоянии $C_{\varepsilon\varepsilon'}$ перейдет в состояние:
1. $U$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{1{\alpha}'1}$;
2. $C_{\varepsilon'1}$, если пункт $2.1$ не выполнен, и среди ее соседей найдется клетка ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{0{\alpha}'1}$, а все остальные такие клетки не будут находиться в состоянии $T_{0{\alpha}'0}$;
3. $n_{\vartheta}^{t} = C_{\varepsilon'0}$, иначе.
Клетка в состоянии $U$ перейдет в состояние:
1. $S_0$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1}$;
2. $U$ во всех остальных случаях.
Клетка в состоянии $S_\Sigma, \; \Sigma=0,\dots,000$ перейдет в состояние:
1. $S_{\Sigma1}$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1}$;
2. $S_{\Sigma0}$, во всех остальных случаях.

Принцип работы

Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана. Более детальное описание механизма работы автомата можно найти в главе 2 книги "Теория самовоспроизводящихся автоматов"^[25].

Автомат Лэнгтона

Примером более простого самовоспроизводящегося клеточного автомата является автомат Лэнгтона^[24].

Также интерес представляет Муравей Лэнгтона^[26], разработанный в 1986 году Крисом Лэнгтоном и являющимся, по сути, двумерной машиной Тьюринга с 2 символами и 4 состояниями^[27].

Определение:

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

В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.

Сигнальная лента несет информацию, необходимую для создания копии автомата.

Состояния

Сигнальные состояния

Состояния $3-7$ относят к классу сигнальных:

$3$ используется при повороте;
$5$ и $6$ используются для самовоспроизведения.

Служебные состояния

Состояния $0-2$ относят к классу служебных:

$0$, идущее вслед за сигнальным задает направление распространения сигнала;
$1$ является «несущей лентой» сигнала;
Из клеток в состоянии $2$ строятся «стенки» автомата.

Принцип работы

Начальная конфигурация
Порожденная копия после 151 такта

Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$;
Поворот ленты влево достигается путем передачи на ее конец сигнала $40$;
Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.

Тьюрмиты

Определение:

Тьюрмит^[24] — это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.

Результат работы муравья Лэнгтона после 27731 итераций

Каждая строка программы записывается в следующем виде:

<текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние>

Игра «Жизнь» эмулируется^[24] с помощью одного тьюрмита: он по очереди обходит все клетки поля и рисует новую конфигурацию в соответствии с правилами игры.
В области исследований модели ДНК при моделировании активно используются взаимодействующие и плиточные тьюрмиты^[24] .

См.также

Линейный клеточный автомат, эквивалентность МТ
Машина Тьюринга
Линейный ограниченный автомат
Автомат фон Неймана
Муравей Лэнгтона
Лобанов А.И. Модели клеточных автоматов^[28]

Литература

↑ Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title=Список_заданий_по_ДМ_2к_2020_весна
↑ Окрестность Мура. URL: https://ru.wikipedia.org/wiki/Окрестность_Мура
↑ Weisstein, Eric W. Moore Neighborhood. URL: https://mathworld.wolfram.com/MooreNeighborhood.html
↑ Окрестность фон Неймана. URL: https://ru.wikipedia.org/wiki/Окрестность_фон_Неймана
↑ Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8
↑ ^6,0 ^6,1 ^6,2 Скаков П.С. Классификация поведения одномерных клеточных автоматов. СПб., 2007 — URL: http://is.ifmo.ru/diploma-theses/_skakov_master.pdf
↑ Eppstein D. Classification of Cellular Automata. http://www.ics.uci.edu/~eppstein/ca/wolfram.html
↑ Wolfram, Stephen (July 1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55: 601–644
↑ Игра "Жизнь". URL: https://ru.wikipedia.org/wiki/Игра_«Жизнь»
↑ «Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm
↑ Eric Weisstein. Still Life
↑ Gardner, M. (1983). "The Game of Life, Part III". Wheels, Life and Other Mathematical Amusements: 246
↑ Breeder – from Eric Weisstein's Treasure Trove of Life
↑ Трофимов Д., Наумов Л. Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизация, 2007. URL: http://is.ifmo.ru/works/wireworld/
↑ "Mirek's Cellebration". URL:http://mirekw.com/ca/index.html
↑ "Zillions of Games". URL:http://zillionsofgames.com
↑ "WireWorld". URL:http://karl.kiwi.gen.nz/CA-Wireworld.html.
↑ "The Wireworld computer". URL:http://www.quinapalus.com/wi-index.html
↑ Диод. URL: https://ru.wikipedia.org/wiki/Диод
↑ Дизъюнкция. URL: https://ru.wikipedia.org/wiki/Дизъюнкция
↑ Исключающее «или». URL: https://ru.wikipedia.org/wiki/Исключающее_«или»
↑ NAND (логический элемент). URL: https://ru.wikipedia.org/wiki/Штрих_Шеффера
↑ Эбелинг Вернер, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.: Эдиториал УРСС, 2001. - 328 с.
↑ ^24,0 ^24,1 ^24,2 ^24,3 ^24,4 Г. Г. Малинецкий, Н. А. Митин, С. А. Науменко, “Нанобиология и синергетика. Проблемы и идеи (Часть 2)”, Препринты ИПМ им. М. В. Келдыша, 2005, 081. URL: http://spkurdyumov.ru/uploads/2013/09/miittin.pdf
↑ ^25,0 ^25,1 ^25,2 Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971
↑ Langton, Chris G. (1986). "Studying artificial life with cellular automata", 120–149
↑ Mária Bieliková, Gerhard Friedrich, Georg Gottlob. SOFSEM 2012: Theory and Practice of Computer Science: 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012, Proceedings. — Springer, 2012. — P. 394. — ISBN 978-3-642-27660-6.
↑ Лобанов А.И. Модели клеточных автоматов // Компьютерные исследования и моделирование, 2010, т. 2, № 3, с. 273-293. URL: http://vst.ics.org.ru/uploads/crmissues/kim_2010_2_3/crm10304.pdf

[1] Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title=Список_заданий_по_ДМ_2к_2020_весна

[2] Окрестность Мура. URL: https://ru.wikipedia.org/wiki/Окрестность_Мура

[3] Weisstein, Eric W. Moore Neighborhood. URL: https://mathworld.wolfram.com/MooreNeighborhood.html

[4] Окрестность фон Неймана. URL: https://ru.wikipedia.org/wiki/Окрестность_фон_Неймана

[5] Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8

[skakov-6] 6,0 ^6,1 ^6,2 Скаков П.С. Классификация поведения одномерных клеточных автоматов. СПб., 2007 — URL: http://is.ifmo.ru/diploma-theses/_skakov_master.pdf

[eppstein-7] Eppstein D. Classification of Cellular Automata. http://www.ics.uci.edu/~eppstein/ca/wolfram.html

[8] Wolfram, Stephen (July 1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55: 601–644

[9] Игра "Жизнь". URL: https://ru.wikipedia.org/wiki/Игра_«Жизнь»

[10] «Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm

[11] Eric Weisstein. Still Life

[12] Gardner, M. (1983). "The Game of Life, Part III". Wheels, Life and Other Mathematical Amusements: 246

[13] Breeder – from Eric Weisstein's Treasure Trove of Life

[14] Трофимов Д., Наумов Л. Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизация, 2007. URL: http://is.ifmo.ru/works/wireworld/

[15] "Mirek's Cellebration". URL:http://mirekw.com/ca/index.html

[16] "Zillions of Games". URL:http://zillionsofgames.com

[17] "WireWorld". URL:http://karl.kiwi.gen.nz/CA-Wireworld.html.

[18] "The Wireworld computer". URL:http://www.quinapalus.com/wi-index.html

[19] Диод. URL: https://ru.wikipedia.org/wiki/Диод

[20] Дизъюнкция. URL: https://ru.wikipedia.org/wiki/Дизъюнкция

[21] Исключающее «или». URL: https://ru.wikipedia.org/wiki/Исключающее_«или»

[22] NAND (логический элемент). URL: https://ru.wikipedia.org/wiki/Штрих_Шеффера

[physics-23] Эбелинг Вернер, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.: Эдиториал УРСС, 2001. - 328 с.

[mitin-24] 24,0 ^24,1 ^24,2 ^24,3 ^24,4 Г. Г. Малинецкий, Н. А. Митин, С. А. Науменко, “Нанобиология и синергетика. Проблемы и идеи (Часть 2)”, Препринты ИПМ им. М. В. Келдыша, 2005, 081. URL: http://spkurdyumov.ru/uploads/2013/09/miittin.pdf

[neuman_automata-25] 25,0 ^25,1 ^25,2 Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971

[26] Langton, Chris G. (1986). "Studying artificial life with cellular automata", 120–149

[27] Mária Bieliková, Gerhard Friedrich, Georg Gottlob. SOFSEM 2012: Theory and Practice of Computer Science: 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012, Proceedings. — Springer, 2012. — P. 394. — ISBN 978-3-642-27660-6.

[28] Лобанов А.И. Модели клеточных автоматов // Компьютерные исследования и моделирование, 2010, т. 2, № 3, с. 273-293. URL: http://vst.ics.org.ru/uploads/crmissues/kim_2010_2_3/crm10304.pdf

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

@@ Строка 1: / Строка 1: @@
-{{В разработке}}
 = Базовые определения =
 {{Определение
 |definition=
-'''Клеточный автомат''' представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии.<br><br>
+'''Клеточный автомат'''<ref>Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title=Список_заданий_по_ДМ_2к_2020_весна</ref> представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии.<br><br>
 Множество состояний $Q$, обозначим состояние ячейки $i$ как $s[i]$.<br>
 Изначально все ячейки находятся в состоянии $B \in Q$, кроме ячеек с номерами от $1$ до $n$. Ячейка с номером $i$, где $1 \le i \le n$ находится в состоянии $x_i$, где $x$ - входное слово (будем считать, что $\Sigma \subset Q$, $B \notin \Sigma$). <br><br>
@@ Строка 14: / Строка 12: @@
 |id=moore_neighborhood
 |definition=
-'''Окрестность Мура''' ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой.<br>
+'''Окрестность Мура'''<ref>Окрестность Мура. URL: https://ru.wikipedia.org/wiki/Окрестность_Мура</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой.<br>
 Окрестность Мура порядка <tex>r</tex> в двумерном случае представляет собой квадрат со стороной <tex>2r + 1</tex><ref>Weisstein, Eric W. Moore Neighborhood. URL: https://mathworld.wolfram.com/MooreNeighborhood.html</ref>.
 }}
@@ Строка 20: / Строка 18: @@
 |id=neiman_neighborhood
 |definition=
-'''Окрестность фон Неймана''' ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону (грань) с данной ячейкой.
+'''Окрестность фон Неймана'''<ref>Окрестность фон Неймана. URL: https://ru.wikipedia.org/wiki/Окрестность_фон_Неймана</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону (грань) с данной ячейкой.
-}}
-{{Определение
-|id=edem_def
-|definition=
-'''Райский сад''' {{---}} конфигурация КА, которая не может появиться в результате «эволюции», потому что не имеет предшественников.
-}}
-{{Теорема
-|id=edem_theorem
-|about=сада Эдема
-|statement=
-Клеточный автомат в евклидовой вселенной является локально инъективным тогда и только тогда, когда он сюръективен.
-Другими словами, теорема утверждает, что сады Эдема существуют только в тех автоматах, в которых существуют близнецы.
-|proof=
-Данная теорема была выдвинута и доказана Эдвардом Муром<ref>Moore, E. F. (1962), Machine models of self-reproduction, Proc. Symp. Applied Mathematics Т. 14: 17–33</ref>.
 }}
@@ Строка 42: / Строка 25: @@
 {{Определение
 |definition=
-'''Классы Вольфрама'''<ref>Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8</ref> {{---}} система классификации клеточных автоматов, основанная на их поведении.
+'''Классы Вольфрама'''<ref>Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8</ref> {{---}} классификация клеточных автоматов, основанная на их поведении.
 }}
-Классы, предложенные С. Вольфрамом<ref name="skakov">Скаков П.С. Классификация поведения одномерных клеточных автоматов. СПб., 2007 — URL: http://is.ifmo.ru/diploma-theses/_skakov_master.pdf</ref>:
-# Эволюция системы заканчивается переходом всех клеток поля в одинаковое состояние;
+<gallery mode="packed-hover" widths=3000px heights=400px>
-# Существует много конечных состояний, но все они состоят из набора простых структур, которые остаются неизменными или повторяются через некоторое небольшое число шагов;
+Image:Wolfram_classes.jpg|400px|300px|''Классы, предложенные С. Вольфрамом<ref name="skakov">Скаков П.С. Классификация поведения одномерных клеточных автоматов. СПб., 2007 — URL: http://is.ifmo.ru/diploma-theses/_skakov_master.pdf</ref>''
-# Поведение сложное, во многих отношениях выглядит хаотическим;
+</gallery>
-# Смесь хаоса и порядка: порождаются локальные структуры, которые перемещаются и взаимодействуют друг с другом очень сложным образом.
 == Классификация Эпштейна ==
-Д. Эпштейн резко критиковал<ref name="eppstein">Eppstein D. Classification of Cellular Automata. http://www.ics.uci.edu/~eppstein/ca/wolfram.html</ref> классификацию С. Вольфрама, в частности, назвал её совершенно несостоятельной из-за невозможности за разумное время проверить принадлежность клеточного автомата к какому-либо классу для большого числа клеточных автоматов.<br>
+На ряд серьезных недостатков классификации С. Вольфрама указывал<ref name="eppstein">Eppstein D. Classification of Cellular Automata. http://www.ics.uci.edu/~eppstein/ca/wolfram.html</ref> Д. Эпштейн.<br>
-Для решения проблемы он предложил свою классификацию двухмерных двоичных клеточных автоматов на основе возможностей порождаемых клеточным автоматом объектов к расширению и уменьшению.
+Один из них состоял в невозможности за разумное время проверить принадлежность клеточного автомата к какому-либо классу для большого числа клеточных автоматов.<br>
+В свою очередь он предложил систему классификации двухмерных двоичных клеточных автоматов, призванную выделять кандидатов в универсальные клеточные автоматы.
-Классы, предложенные Д. Эпштейном<ref name="skakov" />:
-# Все объекты расширяются: в наборе правил есть правило B1 (клетка переходит в состояние 1, если она имеет ровно одного соседа в состоянии 1);
-# Нет расширяющихся объектов: в наборе правил нет правил B2 или B3 (клетка переходит в состояние 1, если она имеет ровно двух / трёх соседей в состоянии 1).
-# Уменьшение невозможно: в наборе правил есть правила S01234 или B23/S0 (клетка сохраняет состояние 1, если у неё есть от нуля до четырех соседей в состоянии 1/клетка переходит в состояние 1 при наличии у неё ровно двух или трёх соседей в состоянии 1 и сохраняет это состояние, если у неё нет соседей в состоянии 1).
-# Возможны и расширение и уменьшение объектов: все остальные случаи.
-<br>
-Однако, данная классификация так же не лишена недостатков, в частности не удовлетворяет поставленным перед ней же требованиям: целью данной классификации является выделение кандидатов в универсальные клеточные автоматы. Эпштейн утверждал, что универсальные клеточные автоматы могут принадлежать только к классу 4, однако, существует<ref name="skakov" /> универсальный клеточный автомат, относящийся к классу 3 по данной классификации.
+<gallery mode="packed-hover" widths=500px heights=250px>
+Image:Eppstein_classes.jpg|250px|500px|''Классы, предложенные Д. Эпштейном<ref name="skakov" />''
+</gallery>
+Однако, данная классификация так же имела серьезные проблемы, и, в конечном счете, не удовлетворяла своему назначению.
 Более подробные описания данных классификаций, а также других наиболее распространенных, можно найти в работе П.С. Скакова<ref name="skakov" />. В ней, в том числе, были выделены основные достоинства и недостатки различных классификаций, и предложена новая, являющаяся уточнением и модификацией существующих и решающая многие их проблемы.
@@ Строка 72: / Строка 51: @@
 }}
 В соответствии с определением, код может быть вычислен следующим образом:
-# Определить все возможные конфигурации состояний окрестности данной ячейки;
+# Определить все возможные конфигурации окрестности данной ячейки;
 # Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию;
-# Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с этим правилом на следующей итерации;
+# Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с правилами переходов на следующей итерации;
 # Интерпретируя полученный список состояний как <tex>S</tex>-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама.
+<br>
-Далее в статье будут приведены наиболее известные правила. Рассматривается бесконечный одномерный массив ячеек клеточного автомата с двумя возможными состояниями. Каждая из клеток имеет начальное состояние. В дискретные моменты времени каждая клетка изменяет своё состояние, причем оно зависит от предыдущего состояния этой ячейки и предыдущего состояния двух соседних ячеек.
+Далее в статье будут приведены наиболее известные правила.<br>
+Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге.
-'''TODO: ADD PICTIRES'''
 === Правило 30 ===
@@ Строка 86: / Строка 64: @@
 '''Правило 30''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).
 }}
+[[Файл:Rule30.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 30]]
+<br>
 Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние:<br>
 {| class="wikitable"  align="center" style="text-align:center"
@@ Строка 102: / Строка 82: @@
 Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.
 }}
+[[Файл:Rule90.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 90]]
+<br>
 Правила перехода для Правила 90:
 {| class="wikitable" style="text-align: center"
@@ Строка 119: / Строка 101: @@
 Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.
 }}
+[[Файл:Rule110.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 110]]
+<br>
 Правила перехода для Правила 110:
 {| class="wikitable" style="text-align: center"
@@ Строка 129: / Строка 113: @@
 |}
 Так как <tex>1101110_2 = {110}_{10}</tex>, данное правило называется Правилом 110.
+<br>
+<br>
+<br>
+<br>
+<br>
+<br>
+<br>
+<br>
 === Правило 184 ===
@@ Строка 135: / Строка 128: @@
 '''Правило 184''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br>
 }}
+[[Файл:Rule184.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 184]]
+<br>
 Правила перехода для Правила 184:
 {| class="wikitable" style="text-align:center;"
@@ Строка 148: / Строка 143: @@
 = Клеточные автоматы на двумерной решетке =
 == Игра «Жизнь» ==
+Некоторые из приведенных далее определений были взяты с этого<ref>Игра "Жизнь". URL: https://ru.wikipedia.org/wiki/Игра_«Жизнь»</ref> сайта, а также со смежных с нем страниц.
 {{Определение
 |definition=
-'''«Жизнь»''' {{---}} клеточный автомат, представляющий из себя бесконечное клетчатое поле, каждая клетка может быть белой или черной. За один ход клетки перекрашиваются по определенным правилам, в зависимости от их соседей в [[#moore_neighborhood | окрестности Мура]].
+'''«Жизнь»''' {{---}} клеточный автомат, представляющий из себя бесконечное клетчатое поле, каждая клетка может быть белой или черной. Состояние, в которое перейдет клетка на следующем шаге, зависит от состояний ее соседей в [[#moore_neighborhood | окрестности Мура]].
 }}
-Дополнительную информацию по игре вы можете найти в статье [[Игра «Жизнь» | "игра «Жизнь»"]].
+Основную информацию по игре вы можете найти в статье [[Игра «Жизнь» | "игра «Жизнь»"]]. В данном разделе будут рассмотрены лишь основные типы и примеры конфигураций данной игры.
-=== Состояния ===
+=== Состояния и правила переходов ===
-Каждая клетка поля может быть либо белого, либо черного цвета. Белые клетки называются «живыми», черные {{---}} «мертвыми».
+{| class="wikitable"
-=== Правила ===
+|-
-На каждом шаге автомата ко всем клеткам применяются следующие правила:
+! scope="col"| Название состояния
-* В черная клетка, имеющая ровно три белые соседние клетки, становится белой («зарождается жизнь»);
+! scope="col"| Цвет
-* Если у белой клетки есть две или три белые соседние клетки, то эта клетка сохраняет свой цвет;
+! scope="col"| Переходит в cостояние
-* Если у белой клетки соседей белого цвета меньше двух или больше трёх, клетка становится черной («умирает от одиночества» или «от перенаселённости»).
+|-
+| «Живая клетка»
+| Белый
+| «мертвая клетка», если имеет ровно меньше двух или больше трех соседей в состоянии «живая клетка».
+|-
+| «Мертвая клетка»
+| Черный
+| «живая клетка», если имеет ровно трех соседей в состоянии «живая клетка».
+|}
 === Основные элементы ===
 В данном разделе используются термины из «Словаря Жизни»<ref>«Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm</ref>.
-В зависимости от начального состояния поля, клетки могут образовывать фигуры, обладающие различными свойствами. По этим свойствам принято делить фигуры на следующие классы:
+''' TODO: ADD PICTURES'''
-* '''Устойчивые фигуры''' {{---}} фигуры, которые остаются неизменными
-* '''Долгожители''' {{---}} фигуры, которые долго меняются, прежде чем стабилизироваться;
-* '''Осцилляторы''' {{---}} фигуры, у которых состояние повторяется через некоторое число поколений, большее 1;
-* '''Двигающиеся фигуры (космические корабли)''' {{---}} фигуры, у которых состояние повторяется, но с некоторым смещением;
-* '''Ружья''' {{---}} фигуры с повторяющимися состояниями, дополнительно создающие движущиеся фигуры;
-* '''Паровозы''' {{---}} двигающиеся фигуры с повторяющимися состояниями, которые оставляют за собой другие фигуры в качестве следов;
-* '''Пожиратели''' {{---}} устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами, уничтожив их;
-* '''Отражатели''' {{---}} устойчивые или периодические фигуры, способные при столкновении с ними движущихся фигур поменять их направление;
-* '''Размножители''' {{---}} конфигурации, количество живых клеток в которых растёт как квадрат количества шагов;
-Наиболее известные представители данных классов будут рассмотрены далее в статье.
-''' TODO: ADD PICTIRES'''
 ==== Устойчивые фигуры ====
-Устойчивые фигуры или «натюрморты», делятся на несколько классов<ref>Eric Weisstein. Still Life</ref>:
+{{Определение
-* '''Устойчивый образец''' {{---}} объект, который является собственным родителем;
+|definition=
-* '''Натюрморт''' {{---}} устойчивый объект, являющийся конечным и непустым, из которого нельзя выделить непустую устойчивую часть;
+'''Устойчивый образец''' {{---}} объект, который является собственным родителем.
-* '''Псевдонатюрморт''' {{---}} устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортов.
+}}
+{{Определение
+|definition=
+'''Натюрморт'''<ref>Eric Weisstein. Still Life</ref> {{---}} устойчивый объект, являющийся конечным и непустым, из которого нельзя выделить непустую устойчивую часть.
+}}
+{{Определение
+|definition=
+'''Псевдонатюрморт''' {{---}} устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортов.
+}}
 ==== Долгожители ====
@@ Строка 214: / Строка 214: @@
 {{Определение
 |definition=
-'''Ружье''' {{---}} класс конфигураций, у которых основная часть циклически повторяется, как у осцилляторов, а также периодически создаёт космические корабли, которые удаляются от ружья.
+'''Ружье''' {{---}} класс конфигураций, у которых основная часть циклически повторяется, как у осцилляторов, а также периодически создаёт космические корабли, которые удаляются от ружья. Данная конфигурация имеет два периода: '''период создания космических кораблей''' и '''период повторения состояний ружья'''.
 }}
-У ружья есть два периода: '''период создания космических кораблей''' и '''период повторения состояний ружья'''.
 ==== Паровозы ====
@@ Строка 225: / Строка 224: @@
 {{Определение
 |definition=
-'''Грабли''' {{---}} паровозы, оставляющие за собой след исключительно из космических кораблей.
+'''Грабли''' {{---}} паровозы, оставляющие за собой след исключительно из космических кораблей.<br>
 }}
-Паровозы условно делят на чистые и грязные:
-* Чистый паровоз оставляет след, обладающей легко уловимой на глаз периодичностью;
-* Грязный — сложный, хаотически выглядящий след.
 ==== Пожиратели ====
@@ Строка 253: / Строка 249: @@
 }}
-Размножители классифицируются<ref>Breeder – from Eric Weisstein's Treasure Trove of Life</ref> по относительной подвижности полученных конфигураций. Типы обозначаются кодами из трёх букв, которые обозначают, являются ли первичная, вторичная и третичная конфигурации соответственно движущимися (Д) или неподвижными (Н).
+Существует несколько видов<ref>Breeder – from Eric Weisstein's Treasure Trove of Life</ref> размножителей, отличающихся между собой относительной подвижностью полученных конфигураций. Виды кодируются при сочетаниями трех букв, описывающие, соответственно, первичную, вторичную и третичную конфигурации: Д {{---}} движущаяся, Н {{---}} неподвижная:<br>
-<br>
-Четыре основных типа:
 * НДД {{---}} ружьё, вырабатывающее грабли;
-* ДНД {{---}} паровоз, оставляющий ружья на своем пути;
+* ДНД {{---}} паровоз, вырабатывающий ружья;
-* ДДН {{---}} грабли, оставляющие паровозы;
+* ДДН {{---}} грабли, вырабатывающий паровозы;
-* ДДД {{---}} Грабли, оставляющие грабли, так что нет никаких неподвижных элементов.
+* ДДД {{---}} грабли, вырабатывающий грабли.
-==== Райский сад ====
-[[#edem_theorem | Теорема сада Эдема]] применима к «Жизни», поскольку легко найти две различные конфигурации, которые эволюционируют в следующем поколении в одну и ту же конфигурацию.
-«Мёртвая вселенная» и одинокая живая клетка в «мёртвой вселенной» эволюционируют в одну и ту же конфигурацию, все клетки которой мёртвые.
-Следовательно, в «Жизни» существуют сады Эдема.
 == Wireworld ==
@@ Строка 271: / Строка 260: @@
 Клеточный автомат '''Wireworld'''<ref>Трофимов Д., Наумов Л. Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизация, 2007. URL: http://is.ifmo.ru/works/wireworld/</ref> представляет собой синхронный автомат с двумерной решеткой из квадратов, каждая клетка которой может находиться в одном из четырех состояний.
 }}
-=== Состояния ===
+=== Состояния и правила переходов ===
 {| class="wikitable"
 |-
 ! scope="col"| Название состояния
 ! scope="col"| Цвет
-! scope="col"| Значение
+! scope="col"| Переходит в состояние
 |-
 | Пустая клетка
 | Черный
-| Клетка, не занятая проводником
+|
 |-
 | Проводник
 | Желтый
-| По проводнику могут распространяться электроны
+| «голова электрона», если имеет ровно одного или двух [[#moore_neighborhood | соседей]] в состоянии «голова электрона»
 |-
 | Голова электрона
 | Красный
-| Проводник, занятый электроном: вместе с «хвостом электрона» задает направление движения электрона.
+| «хвост электрона»
 |-
 | Хвост электрона
 | Синий
-| Проводник, занятый электроном: вместе с «головой электрона» задает направление движения электрона.
+| «проводник»
 |}
-=== Правила ===
-На каждом шаге автомата ко всем клеткам применяются следующие правила:
-# Пустая клетка остается пустой.
-# Клетка, находящаяся в состоянии «голова электрона» переходит в состояние «хвост электрона».
-# Клетка, находящаяся в состоянии «хвост электрона» переходит в состояние «проводник».
-# Клетка, находящаяся в состоянии «проводник» переходит в состояние «голова электрона», в том случае, если среди соседних клеток ровно одна или две находятся в состоянии «голова электрона». Во всех остальных случаях «проводник» остается «проводником».<br>
-При применении данных правил используется [[#moore_neighborhood | окрестность Мура]] – считается, что с данной
-клеткой соседствуют все восемь ее непосредственных соседей.
 === Общие закономерности ===
-Электрон передвигается со скоростью одна клетка за шаг. Если по проводу навстречу идут два электрона, при столкновении они исчезают. При достижении электроном разветвления проводов по каждому из направлений, кроме исходного, уходит по электрону. Если к разветвлению одновременно подходит <tex>2</tex> и более электронов, все они исчезают. При толщине провода в <tex>2</tex> клетки поведение электронов аналогично обычному, при большей толщине поведение становится хаотичным.
+Движение "электрона" в "цепи" происходит со следующими закономерностями:
+* При прохождении электроном разветвления "цепи", в каждое из новых направлений уходит по "электрону";
+* При одновременном столкновении трёх и более "электронов", они исчезают.
+* При толщине "провода" больше $2$, "электроны" начинают двигаться хаотично.
 === Основные элементы ===
-Большие коллекции функциональных элементов имеются в пакетах Mirek's Cellebration<ref>"Mirek's Cellebration". URL:http://mirekw.com/ca/index.html</ref> и Zillions of Games<ref>"Zillions of Games". URL:http://zillionsofgames.com</ref>, а также на сайте WireWorld<ref>"WireWorld". URL:http://karl.kiwi.gen.nz/CA-Wireworld.html. </ref>. Кроме того, на сайте The Wireworld computer<ref>"The Wireworld computer". URL:http://www.quinapalus.com/wi-index.html</ref> приводится пример построения в WireWorld компьютера с определенным набором инструкций и регистров, и реализация алгоритма перечисления простых чисел для этого компьютера.
+В данной статье приведены лишь основные простейшие элементы, которые можно составить в Wireworld.<br>
+Большое количество примеров приведено в Mirek's Cellebration<ref>"Mirek's Cellebration". URL:http://mirekw.com/ca/index.html</ref> и Zillions of Games<ref>"Zillions of Games". URL:http://zillionsofgames.com</ref>, WireWorld<ref>"WireWorld". URL:http://karl.kiwi.gen.nz/CA-Wireworld.html. </ref>; с помощью элементов Wireworld также был построен<ref>"The Wireworld computer". URL:http://www.quinapalus.com/wi-index.html</ref> компьютер.
 ==== Тактовый генератор ====
-Данный элемент представляет собой «петлю» из клеток проводника, к которой подсоединен провод – выход генератора, и изначально содержит один электрон. С периодом, равным длине петли, этот электрон достигает точки соединения петли с выходом, и дальше разветвляется на два электрона, один из которых идет по выходу, второй – дальше по петле. Таким образом, этот элемент можно использовать для получения в проводе бесконечного количества электронов, следующих один за другим на расстоянии, регулируемом длиной петли.<br>
+Данный элемент используется для получения электронов, так как при каждом прохождении разветвления электроном, движущимся по петле генератора, образуется новый электрон. Частота появления электронов регулируется длиной петли.
+<br>
 <gallery mode="packed-hover">
@@ Строка 318: / Строка 303: @@
 ==== Диод ====
-Этот функциональный элемент имеет две точки подсоединения к проводам – вход и выход, и его действие состоит в том, что электроны, пришедшие на вход, передаются на выход, а электроны, пришедшие на выход – исчезают. Таким образом, электроны могут перемещаться по проводу, в который включен диод, лишь в одном направлении.
+Данный элемент действует точно так же, как одноименный элемент<ref>Диод. URL: https://ru.wikipedia.org/wiki/Диод</ref> электрической цепи.
 <br>
 <gallery mode="packed-hover">
@@ Строка 325: / Строка 310: @@
 ==== Логические элементы OR, XOR и NAND ====
-Каждый из этих элементов имеет по 2 входа и выход. Наличие электрона на входе соответствует логическому значению «единица», отсутствие – логическому значению «ноль». Электрон на выходе появляется согласно таблице истинности соответствующей логической операции.<br>
+Данный элемент действует точно так же, как и одноименные логические элементы<ref>Дизъюнкция. URL: https://ru.wikipedia.org/wiki/Дизъюнкция</ref><ref>Исключающее «или». URL: https://ru.wikipedia.org/wiki/Исключающее_«или»</ref><ref>NAND (логический элемент). URL: https://ru.wikipedia.org/wiki/Штрих_Шеффера</ref>.<br>
-* Так, для элемента '''OR''' электрон на любом из входов, или электроны на обоих входах одновременно дают электрон на выходе.<br>
-* Для элемента '''XOR''' электрон на любом из входов дает электрон на выходе, но при одновременной подаче электронов на оба входа они исчезают, и электрон на выходе не создается.<br>
-* Элемент '''NAND''' работает как тактовый генератор, и посылает электроны на выход во всех случаях, за исключением случая, когда на оба входа одновременно подаются электроны.<br>
 <gallery mode="packed" widths=75px heights=200px>
@@ Строка 334: / Строка 316: @@
 Image:XOR_wireworld.jpg|''XOR''
 Image:NAND_wireworld.jpg|''NAND''
-</gallery>
-==== Двоичный сумматор ====
-Рассмотрим пример более сложной структуры, состоящей из множества простых элементов – двоичный сумматор. Его функция заключается в том, что при подаче на два входа закодированных особым образом чисел, через фиксированное количество шагов (в изображенном примере – 48) на выходе появится закодированное таким же образом число – сумма чисел на входах. Числа кодируются в двоичном виде, от младших битов к старшим, каждый бит кодируется наличием или отсутствием электрона на определенной позиции. На
-рисунке ниже эти позиции отмечены точками и изображениями чисел (значений каждого бита) из клеток в состоянии «проводник» по краям входов и выхода. Сами по себе эти отметки не несут никакой функциональной нагрузки, а служат лишь в пояснительных целях. Изображенный ниже сумматор имеет разрядность входов три бита, но можно получить сумматор с любой разрядностью, удлинив или укоротив провода на входах и выходе.
-<gallery mode="packed-hover" widths=200px heights=350px>
-Image:Binary_summator_wireworld.jpg|''Двоичный сумматор''
 </gallery>
 = Самовоспроизводящиеся клеточные автоматы =
-В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов:
+В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов, которые подробно описаны в книге "Физика процессов эволюции"<ref name="physics">Эбелинг Вернер, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.: Эдиториал УРСС, 2001. - 328 с.</ref>:<br>
+«
 # Логическая универсальность.
 ## При каких условиях определенный класс автоматов логически универсален?
@@ Строка 352: / Строка 328: @@
 ## Какой класс автоматов может быть построен каким-то автоматом?
 # Конструктивная универсальность.
-## Существует ли конструктивно универсальный автомат (т. е. автомат, способный построить любой автомат)?
+## Существует ли конструктивно универсальный автомат? (т. е. автомат, способный построить любой автомат)
 # Самовоспроизведение.
 ## Существует ли самовоспроизводящийся автомат?
-## Существует ли автомат, который помимо самовоспроизведения может решать и другие задачи?
+## Существует ли автомат, который, помимо самовоспроизведения, может решать и другие задачи?
 # Эволюция.
 ## Может ли при конструировании автомата автоматом происходить усложнение типа автомата?
-## Может ли такая эволюция происходить в направлении от менее эффективного к более эффективному автомату (при надлежащем определении понятия эффективности)?
+## Может ли такая эволюция происходить в направлении от менее эффективного к более эффективному автомату? (при надлежащем определении понятия эффективности)
+:::::::::::::::::::::::::::::::::::::::::::::::::::::::».
-Тьюринг показал, что предложенный им класс автоматов логически универсален, т. е. автоматы Тьюринга могут выполнить произвольный логический процесс (произвольное вычисление), если их снабдить конечным, но сколь угодно продолжаемым запоминающим механизмом (памятью). Тьюринг показал также, что существует универсальная машина Тьюринга, способная выполнять любые вычисления, тем самым дав утвердительный ответ на первый вопрос.
+В то время, как Тьюринг доказал, что [[Машина Тьюринга|машина Тьюринга]] является логически универсальной, Дж. фон Нейман построил автомат<ref name="mitin">Г. Г. Малинецкий, Н. А. Митин, С. А. Науменко, “Нанобиология и синергетика. Проблемы и идеи (Часть 2)”, Препринты ИПМ им. М. В. Келдыша, 2005, 081. URL: http://spkurdyumov.ru/uploads/2013/09/miittin.pdf</ref>, удовлетворяющий всем пяти свойствам. Одна из таких моделей будет описана далее.
-<br>
-Дж. фон Нейман доказал существование автомата, удовлетворяющего всем пяти свойствам, построив две<ref name="mitin">Г. Г. Малинецкий, Н. А. Митин, С. А. Науменко, “Нанобиология и синергетика. Проблемы и идеи (Часть 2)”, Препринты ИПМ им. М. В. Келдыша, 2005, 081. URL: http://spkurdyumov.ru/uploads/2013/09/miittin.pdf</ref> модели, одна из которых будет описана далее.
 == Автомат фон Неймана ==
@@ Строка 368: / Строка 343: @@
 |id=neiman_auto
 |definition=
-'''Автомат фон Неймана''' (клеточная модель самовоспроизведения<ref>Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} двумерный клеточный автомат, в каждой клетке поля которого находится конечный автомат с 29 состояниями, каждая клетка имеет 4 соседей, информация приходит с задержкой по крайней мере на 1 единицу времени.
+'''Автомат фон Неймана''' (клеточная модель самовоспроизведения<ref name="neuman_automata">Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} объект, представляющий собой поле, в каждой клетке которого находится конечный автомат с 29 состояниями.
 }}
-Из 29 состояний одно является невозбудимым, 20 относятся к возбудимым, 8 – к чувствительным.<br>
+=== Состояния ===
-На бесконечном поле задается исходный конечный набор клеток, имеющих не невозбудимое состояние, затем клеточная система начинает работать по правилам переходов.
+Определим соседей клетки с помощью векторов, установив в координат рассматриваемую клетку:
+* [[#neiman_neighborhood | Окрестность фон Неймана]]: <tex>v^0 = (1, 0) \;\;\; v^1 = (0, 1) \;\;\; v^2 = (-1, 0) \;\;\; v^3 = (0, -1)</tex>;
-Логическая структура бесконечного клеточного автомата такова, что через некоторый промежуток времени в некоторой области клеточного пространства, отличной от начального условия, появляется копия начального автомата. От дискретной клеточной модели самовоспроизведения фон Нейман собирался перейти к непрерывной модели, которая представляла бы систему дифференциальных уравнений в частных производных диффузионного типа. К сожалению, он не успел осуществить свой замысел.
+* Клетки, дополняющие окрестность фон Неймана до [[#moore_neighborhood | окрестности Мура]]: <tex>v^4 = (1, 1) \;\;\; v^5 = (-1, 1) \;\;\; v^6 = (-1, -1) \;\;\; v^7 = (1, -1)</tex><br><br>
+Состояние клетки $\vartheta$ на $t$-ом шаге: <tex>n_{t}^{\vartheta} = F(n_{t - 1}^\vartheta; n_{t - 1}^{\vartheta + v^\alpha} \; | \; \alpha = 0, \dots , 3), F</tex> {{---}} функция переходов.<br>
-=== Формальное описание ===
-Данное описание взято из §5.3 книги "Физика процессов эволюции"<ref name="physics">Эбелинг Вернер, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.: Эдиториал УРСС, 2001. - 328 с.</ref>.<br>
-Как было сказано выше, [[#neiman_auto | автомат фон Неймана]] представляет клеточный автомат, у которого каждая клетка может находиться в 29 состояниях. Клеточный автомат состоит из многих однотипных автоматов, расположенных в узлах решетки; выход каждого автомата служит входом для [[#neiman_neighborhood | соседних клеток]].<br>
-Нумерует клетки радиус-вектор <tex>\vartheta = (i, j), \; i,j = 0, \pm 1, \pm 2, \dots</tex>.
-<br>
 <br>
-{{Определение
+Состояния клеток рассматриваемого автомата делятся на $4$ различных класса:<br>
-|definition=
+. Основное состояние <tex>U</tex> (невозбужденное).<br>
-Назовем '''ближайшими соседями''' клетки те клетки, что лежат в ее [[#neiman_neighborhood | окрестности фон Неймана]]; клетки, дополняющие [[#neiman_neighborhood | окрестность фон Неймана]] до [[#moore_neighborhood | окрестность Мура]], назовем '''ближними соседями'''.
+. Транзитивные состояния <tex>T_{u\alpha\varepsilon}</tex>, где:
-}}
-'''TODO: ADD PICTURES'''
-<br>
-Определим восемь векторов расстояния:<br>
-<tex>v^0 = (1, 0) \;\;\; v^1 = (0, 1) \;\;\; v^2 = (-1, 0) \;\;\; v^3 = (0, -1) \;\;\; v^4 = (1, 1) \;\;\; v^5 = (-1, 1) \;\;\; v^6 = (-1, -1) \;\;\; v^7 = (1, -1)</tex><br>
-Тогда <tex>\vartheta + v^\alpha,\; \alpha = 0, \dots , 3</tex> {{---}} ближайшие соседи, а <tex>\vartheta + v^\alpha,\; \alpha = 7, \dots , 7</tex> {{---}} ближние.
-<br><br>
-Время дискретно, т.е. изменяется по тактам: <tex>t = 0, \pm 1, \pm 2, \dots</tex>, на каждом такте каждая клетка <tex>\vartheta</tex> находится в одном из <tex>n</tex> состояний <tex>n = 0, \dots , N - 1</tex>, т.е. состояние на такте <tex>t</tex> есть <tex>n_{t}^{\vartheta}</tex>.
-<br><br>
-Состояния изменяются по правилу перехода <tex>F</tex>, одинаковому для всех клеток (внутренняя однородность):<br>
-: <tex>n_{t}^{\vartheta} = F(n_{t - 1}^\vartheta; n_{t - 1}^{\vartheta + v^\alpha} \; | \; \alpha = 0, \dots , 3)</tex><br>
-В соотношении выше <tex>F</tex> зависит от <tex>5</tex> переменных, которые могут принимать <tex>N</tex> значений, а поскольку <tex>F</tex> также принимает <tex>N</tex> различных значений при каждом значении аргумента, всего существует <tex>m = N^{N^5}</tex> различных функций <tex>F</tex> (различных моделей).
-<br><br>
-Автомат фон Неймана имеет <tex>N = 29</tex> различных состояний:<br>
-. Транзитивные состояния (импульсы) <tex>T_{u\alpha\varepsilon}</tex>, где:
 ::: <tex>
 u =
 \begin{equation*}
   \begin{cases}
-&\text{—$\;$ обычное состояние,}\\
+&\text{—$\;$ обычное,}\\
-&\text{—$\;$ специальное состояние;}\\
+&\text{—$\;$ специальное;}\\
- \end{cases}
-\end{equation*}
-</tex><br>
-::: <tex>
-\alpha =
-\begin{equation*}
- \begin{cases}
-&\text{—$\;$ вправо,}\\
-&\text{—$\;$ вверх,}\\
-&\text{—$\;$ влево,}\\
-&\text{—$\;$ вниз;}\\
   \end{cases}
 \end{equation*}
 </tex><br>
+::: <tex> \alpha = 0, \dots, 3 </tex> {{---}} выходное направление (вправо, вверх, влево, вниз);
 ::: <tex>
 \varepsilon =
 \begin{equation*}
   \begin{cases}
-&\text{—$\;$ состояние покоя,}\\
+&\text{—$\;$ покой,}\\
-&\text{—$\;$ возбужденное состояние;}\\
+&\text{—$\;$ возбуждение;}\\
   \end{cases}
 \end{equation*}
 </tex><br>
 . Конфлюэнтные состояния <tex>C_{\varepsilon{\varepsilon}'}</tex>, где:
 ::: <tex>
 \varepsilon =
 \begin{equation*}
   \begin{cases}
-&\text{—$\;$ состояние покоя,}\\
+&\text{—$\;$ покой,}\\
-&\text{—$\;$ возбужденное состояние;}\\
+&\text{—$\;$ возбуждение;}\\
   \end{cases}
 \end{equation*}
@@ Строка 444: / Строка 388: @@
 \begin{equation*}
   \begin{cases}
-&\text{—$\;$ состояние покоя на следующем такте,}\\
+&\text{—$\;$ покой на следующем такте,}\\
-&\text{—$\;$ возбужденное состояние на следующем такте;}\\
+&\text{—$\;$ возбуждение на следующем такте;}\\
   \end{cases}
 \end{equation*}
 </tex><br>
-. Основное состояние <tex>U</tex> (невозбужденное).
+. Чувствительные состояния $S, \; S_0 \;, S_{00} \;, S_{01} \;, S_{000} \;, S_1 \;, S_{10} \;, S_{11}$.
-<br>
+<br><br>
-. Чувствительные (сенситивные) состояния <tex>S_{\Sigma}</tex>, где:
+Далее объясним природу вышеперечисленных состояний. Для достижения поставленных целей, Дж. фон Нейман проводит<ref name="neuman_automata"/> аналогию с системой нейронных связей, аналогичным образом строя автомат.<br><br>
-::: <tex>\Sigma = \Theta, 0, 1, 00, 01, 10, 11, 000</tex><br>
+Для передачи информации между клетками по цепочке из клеток же вводятся состояния $T$, причем наличие нейронного импульса регулируется параметром $\varepsilon$. Так как передача должна быть направленным процессом, вводится параметр $\alpha$, обозначающий, с какого направления клетка в данном состоянии будет принимать импульс.<br><br>
-и
+Работу самих нейронов представляют состояния $С$: каждый нейрон имеет один "выход" и два "входа" (стороны клетки), которые для возбуждения необходимо раздражать одновременно, то есть у "нейрона" должно быть не менее двух соседей в окрестности фон Неймана в состоянии $T_1$, выходные направления которых ориентированы на "нейрон". Для экономии количества состояний вводится условность, что каждая сторона клетки может быть как "входом", так и "выходом" нейрона.<br><br>
-::: <tex>S_{0000} = T_{000},</tex><br>
+По аналогии с нейронными сетями, автомат должен иметь возможность "расщеплять" передаваемый сигнал, т.е. обеспечить возможность передачи его нескольким клеткам сразу. Данную функцию выполняют конфлюэнтные состояния, по определению имея несколько "выходов" и один "вход".<br><br>
-::: <tex>S_{0001} = T_{010},</tex><br>
+Состояния $S_{\Sigma0}$ и $S_{\Sigma1}$ используются для совершения прямого (возбуждение невозбужденных клеток) и обратного (приведение к покою возбужденных клеток) процессов.
-::: <tex>S_{001} = T_{020},</tex><br>
-::: <tex>S_{010} = T_{030},</tex><br>
+=== Правила переходов ===
-::: <tex>S_{011} = T_{100},</tex><br>
+Функция переходов $F$ определяется следующими соотношениями:
-::: <tex>S_{100} = T_{110},</tex><br>
-::: <tex>S_{101} = T_{120},</tex><br>
-::: <tex>S_{110} = T_{130},</tex><br>
-::: <tex>S_{111} = C_{00},</tex><br>
-<br>
-Основное состояние $U$ может оставаться неизменным или, путем возбуждения, переходить в чувствительное состояние $S$. В последнем случае последнее автоматически пробегает определенную последовательность чувствительных состояний, которая неизбежно заканчивается конфлюэнтным состоянием $C$ или транзитивным состоянием $T$. Оба конечных состояния могут попеременно находиться в возбужденной и невозбужденной форме, оставаться неизменными или переходить снова в основное состояние.<br>
-<br>
-Более подробно $F$ определяется следующими соотношениями:
-# Пусть $n_{\vartheta}^{t - 1} = T_{u\alpha\varepsilon}$:
+# Клетка в состоянии $T_{u\alpha\varepsilon}$ перейдет в состояние:
-## $n_{\vartheta}^{t} = U \Leftrightarrow \forall \{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'}  \; \wedge \; u \neq u'\} \;\; n_{\vartheta'}^{t - 1} = T_{u'{\alpha}'{\vartheta}'}$;
+## $U$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u'{\alpha}'{\vartheta}'}$;
-## $n_{\vartheta}^{t} = T_{u{\alpha}1} \Leftrightarrow$ не выполнено $1.1$ и выполнено одно из следующих:
+## $T_{u{\alpha}1}$, если пункт $1.1$ не выполнен, и среди ее соседей найдется клетка, удовлетворяющая одному из условий:
-### $\forall\{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'} \neq -v^\alpha\} \;\; n_{{\vartheta}'}^{t - 1} = T_{u{\alpha}'1}$;
+### ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'} \neq -v^\alpha$ в состоянии $T_{u{\alpha}'1}$;
-### $\forall\{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{\beta} \neq -v^\alpha, \; \beta = 0,\dots, 3\} \;\; n_{\vartheta}^{t - 1} = C_1$;
+### ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{\beta} \neq -v^\alpha, \; \beta = 0,\dots, 3$ в состоянии $C_1$;
-## $n_{\vartheta}^{t} = T_{u{\alpha}0}$, иначе.
+## $T_{u{\alpha}0}$ во всех остальных случаях.
-# Пусть $n_{\vartheta}^{t - 1} = C_{\varepsilon\varepsilon'}$:
+# Клетка в состоянии $C_{\varepsilon\varepsilon'}$ перейдет в состояние:
-## $n_{\vartheta}^{t} = U \Leftrightarrow \forall \{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'}\} \;\; n_{\vartheta'}^{t - 1} = T_{1{\alpha}'1}$;
+## $U$, если среди ее соседей найдется  ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$  в состоянии $T_{1{\alpha}'1}$;
-## $n_{\vartheta}^{t} = C_{\varepsilon'1} \Leftrightarrow$ не выполнено $2.1$ и выполнены следующие условия:
+## $C_{\varepsilon'1}$, если пункт $2.1$ не выполнен, и среди ее соседей найдется клетка ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{0{\alpha}'1}$, а все остальные такие клетки не будут находиться в состоянии $T_{0{\alpha}'0}$;
-### $\forall\{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'} \} \;\; n_{{\vartheta}'}^{t - 1} = T_{0{\alpha}'1}$;
-### Для всех $\{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'} \} \;\; n_{{\vartheta}'}^{t - 1} = T_{0{\alpha}'0}$;
 ## $n_{\vartheta}^{t} = C_{\varepsilon'0}$, иначе.
-# Пусть $n_{\vartheta}^{t - 1} = U$:
+# Клетка в состоянии $U$ перейдет в состояние:
-## $n_{\vartheta}^{t} = S_0 \Leftrightarrow \forall \{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'}\} \;\; n_{\vartheta'}^{t - 1} = T_{u{\alpha}'1}$;
+## $S_0$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1}$;
-## $n_{\vartheta}^{t} = U$, иначе.
+## $U$ во всех остальных случаях.
-# Пусть $n_{\vartheta}^{t - 1} = S_\Sigma, \; \Sigma=0,\dots,000$:
+# Клетка в состоянии $S_\Sigma, \; \Sigma=0,\dots,000$ перейдет в состояние:
-## $n_{\vartheta}^{t} = S_{\Sigma1} \Leftrightarrow \forall \{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'}\} \;\; n_{\vartheta'}^{t - 1} = T_{u{\alpha}'1}$;
+## $S_{\Sigma1}$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1}$;
-## $n_{\vartheta}^{t} = S_{\Sigma0}$, иначе.
+## $S_{\Sigma0}$,  во всех остальных случаях.
 === Принцип работы ===
-''' TODO: ADD PICS'''<br>
+Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана.
-На бесконечном поле задается исходный конечный набор клеток, имеющих не невозбудимое состояние. Затем клеточная система начинает работать по правилам переходов. Логическая структура бесконечного клеточного автомата такова, что через некоторый промежуток времени в некоторой области клеточного пространства, отличной от начального условия, появляется копия начального автомата. От дискретной клеточной модели самовоспроизведения фон Нейман собирался перейти к непрерывной модели, которая представляла бы систему дифференциальных уравнений в частных производных диффузионного типа.
+Более детальное описание механизма работы автомата можно найти в главе 2 книги "Теория самовоспроизводящихся автоматов"<ref name="neuman_automata"/>.
 == Автомат Лэнгтона ==
-Одним из направлений развития работы фон Неймана стали попытки конструирования более простых самовоспроизводящихся клеточных автоматов. Примером эволюции простого самовоспроизводящегося автомата {{---}} автомат Лэнгтона<ref name="mitin" />.<br>
+Примером более простого самовоспроизводящегося клеточного автомата является автомат Лэнгтона<ref name="mitin" />.<br>
-В статье<ref>Byl John. Self-reproduction in small cellular automata. Physica D, v. 34 (1989),
+Также интерес представляет Муравей Лэнгтона<ref>Langton, Chris G. (1986). "Studying artificial life with cellular automata", 120–149</ref>, разработанный в 1986 году Крисом Лэнгтоном и являющимся, по сути, двумерной машиной Тьюринга с 2 символами и 4 состояниями<ref>Mária Bieliková, Gerhard Friedrich, Georg Gottlob. SOFSEM 2012: Theory and Practice of Computer Science: 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012, Proceedings. — Springer, 2012. — P. 394. — ISBN 978-3-642-27660-6.</ref>.
-p.295-299.</ref> приводятся самовоспроизводящиеся автоматы, которые еще проще автоматов Лэнгтона, показанных на '''изображениях выше'''. Оказалось, что можно сконструировать самовоспроизводящийся автомат всего лишь из 10 клеток, при этом каждая клетка автомата может находиться в одном из шести возможных состояний.<br>
-Также интерес представляет Муравей Лэнгтона<ref>Langton, Chris G. (1986). "Studying artificial life with cellular automata", 120–149</ref>, разработанный в 1986 году Крисом Лэнгтоном. Данный автомат является, по сути, двумерной машиной Тьюринга с 2 символами и 4 состояниями<ref>Mária Bieliková, Gerhard Friedrich, Georg Gottlob. SOFSEM 2012: Theory and Practice of Computer Science: 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012, Proceedings. — Springer, 2012. — P. 394. — ISBN 978-3-642-27660-6.</ref>.
 {{Определение
 |definition=
 '''Автомат Лэнгтона''' {{---}} двумерный клеточный самовоспроизводящийся автомат, представляющий собой сигнальную ленту, заключенную между двумя стенками.<br>
-В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.
+В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.<br>
+Сигнальная лента несет информацию, необходимую для создания копии автомата.
 }}
-Сигнальная лента несет информацию, необходимую для создания копии автомата.<br>
 === Состояния ===
-* $0,\;1,\;2$ {{---}} служебные состояния;
+==== Сигнальные состояния ====
-* $3,\;4,\;5,\;6,\;7$ {{---}} сигнальные состояния.
+Состояния $3-7$ относят к классу сигнальных:
+* $3$ используется при повороте;
+* $5$ и $6$ используются для самовоспроизведения.
-Из клеток в состоянии $2$ строятся «стенки» автомата.
+==== Служебные состояния ====
-Состояние $1$ является «несущей частотой», или, скорее, «несущей лентой» сигнала.
+Состояния $0-2$ относят к классу служебных:
-Вслед за сигнальным состоянием должно идти состояние $0$ {{---}} так задается направление распространения сигнала.
+* $0$, идущее вслед за сигнальным задает направление распространения сигнала;
-Состояние $3$ используется в качестве промежуточного состояния при повороте, состояния $5$ и $6$ используются при отделении дочернего автомата и для инициализации новой итерации самовоспроизведения.
+* $1$ является «несущей лентой» сигнала;
+* Из клеток в состоянии $2$ строятся «стенки» автомата.
 === Принцип работы ===
-''' TODO: ADD PICTURES'''<br>
+<gallery mode="packed" widths=75px heights=200px>
-Когда конца ленты достигает сигнал $70$, то длина ленты увеличивается на $1$. Когда в конец ленты приходят два сигнала $40$, то лента делает поворот налево. Копия исходного состояния получается через $151$ такт времени после запуска автомата.
+Image:langton_start.jpg|''Начальная конфигурация''
+Image:langton_copy.jpg|''Порожденная копия после 151 такта''
+</gallery>
-= Тюрьмиты =
+* Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$;
+* Поворот ленты влево достигается путем передачи на ее конец сигнала $40$;
+* Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.
+= Тьюрмиты =
 {{Определение
 |definition=
-'''Тьюрмит''' {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.
+'''Тьюрмит'''<ref name="mitin" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.
 }}
+[[Файл:Turmite_Langton_ant.png|thumb|300px|right|Результат работы [https://ru.wikipedia.org/wiki/Муравей_Лэнгтона муравья Лэнгтона] после 27731 итераций]]
 Каждая строка программы записывается в следующем виде:
 <pre><текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние></pre>
 <br>
-'''TODO: ADD PICTURES'''
+[[Игра «Жизнь»]] эмулируется<ref name="mitin" /> с помощью одного тьюрмита: он по очереди обходит все клетки поля и рисует новую конфигурацию в соответствии с правилами игры.<br>
-<br>
+В области исследований модели ДНК при моделировании активно используются взаимодействующие и плиточные тьюрмиты<ref name="mitin" /> .
-Тьюрмиты можно программировать для решения достаточно сложных задач: например, один тьюрмит может анализировать размеченную поверхность и оставлять на ней пометки для другого, который будет вносить в нее изменения. При помощи всего лишь одного тьюрмита можно реализовать<ref name="mitin" /> клеточный автомат «Жизнь»: тьюрмит обегает колонию и в соответствии с заданными правилами рисует следующее поколение.
 = См.также =
@@ Строка 536: / Строка 476: @@
 * [[Линейный ограниченный автомат]]
 * [https://ru.wikipedia.org/wiki/Автомат_фон_Неймана Автомат фон Неймана]
-* [https://ru.wikipedia.org/wiki/%D0%9C%D1%83%D1%80%D0%B0%D0%B2%D0%B5%D0%B9_%D0%9B%D1%8D%D0%BD%D0%B3%D1%82%D0%BE%D0%BD%D0%B0 Муравей Лэнгтона]
+* [https://ru.wikipedia.org/wiki/Муравей_Лэнгтона Муравей Лэнгтона]
+* Лобанов А.И. Модели клеточных автоматов<ref>Лобанов А.И. Модели клеточных автоматов // Компьютерные исследования и моделирование, 2010, т. 2, № 3, с. 273-293. URL: http://vst.ics.org.ru/uploads/crmissues/kim_2010_2_3/crm10304.pdf</ref>
 = Литература =

Модели клеточных автоматов — различия между версиями

Текущая версия на 19:13, 4 сентября 2022

Содержание

Базовые определения

Классификация клеточных автоматов

Классификация Вольфрама

Классификация Эпштейна

Одномерные клеточные автоматы

Коды Вольфрама

Правило 30

Правило 90

Правило 110

Правило 184

Клеточные автоматы на двумерной решетке

Игра «Жизнь»

Состояния и правила переходов

Основные элементы

Устойчивые фигуры

Долгожители

Осцилляторы

Двигающиеся фигуры

Ружья

Паровозы

Пожиратели

Отражатели

Размножители

Wireworld

Состояния и правила переходов

Общие закономерности

Основные элементы

Тактовый генератор

Диод

Логические элементы OR, XOR и NAND

Самовоспроизводящиеся клеточные автоматы

Автомат фон Неймана

Состояния

Правила переходов

Принцип работы

Автомат Лэнгтона

Состояния

Сигнальные состояния

Служебные состояния

Принцип работы

Тьюрмиты

См.также

Литература

Навигация

Поиск