Изменения

= Базовые определения ={{В разработкеОпределение|definition='''Клеточный автомат'''<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>Правила работы клеточного автомата такие: задано число $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$. }}Определение и основные свойства линейного клеточного автомата содержатся в статье [[Линейный клеточный автомат, эквивалентность МТ | "линейный клеточный автомат, эквивалентность МТ"]].

'''Окрестность Мура''' <ref>Окрестность Мура. URL: https://ru.wikipedia.org/wiki/Окрестность_Мура</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой.<br>

|id=moore_neighborhoodneiman_neighborhood|definition='''Окрестность фон Неймана'''<ref>Окрестность фон Неймана. URL: https://ru.wikipedia.org/wiki/Окрестность_фон_Неймана</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону (грань) с данной ячейкой.}} = Классификация клеточных автоматов === Классификация Вольфрама =={{Определение|definition='''Классы Вольфрама'''<ref>Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8</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>Один из них состоял в невозможности за разумное время проверить принадлежность клеточного автомата к какому-либо классу для большого числа клеточных автоматов.<br>В свою очередь он предложил систему классификации двухмерных двоичных клеточных автоматов, призванную выделять кандидатов в универсальные клеточные автоматы. <gallery mode="packed-hover" widths=500px heights=250px>Image:Eppstein_classes.jpg|250px|500px|''Классы, предложенные Д. Эпштейном<ref name="skakov" />''</gallery>Однако, данная классификация так же имела серьезные проблемы, и, в конечном счете, не удовлетворяла своему назначению.Более подробные описания данных классификаций, а также других наиболее распространенных, можно найти в работе П.С. Скакова<ref name="skakov" />. В ней, в том числе, были выделены основные достоинства и недостатки различных классификаций, и предложена новая, являющаяся уточнением и модификацией существующих и решающая многие их проблемы. = Одномерные клеточные автоматы === Коды Вольфрама =={{Определение|definition='''Код Вольфрама''' {{---}} система именования клеточных автоматов (как правило, [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]]), предложенная С. Вольфрамом в 1983 году<ref>Wolfram, Stephen (July 1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55: 601–644</ref>.<br>Данная система основана на наблюдении, что таблица, определяющая новое состояние каждой ячейки в автомате, как функция состояний в его окрестности, может интерпретироваться как число из <tex>k</tex>-цифр в <tex>S</tex>-арной позиционной системе счисления, где <tex>S</tex> {{---}} число состояний, которое может иметь каждая ячейка в автомате, <tex>k = S^{2n + 1}</tex> {{---}} число конфигураций окрестности, а <tex>n</tex> {{---}} радиус окрестности.}}В соответствии с определением, код может быть вычислен следующим образом:# Определить все возможные конфигурации окрестности данной ячейки;# Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию;# Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с правилами переходов на следующей итерации;# Интерпретируя полученный список состояний как <tex>S</tex>-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама.<br>Далее в статье будут приведены наиболее известные правила.<br>Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге. === Правило 30 ==={{Определение

'''Окрестность фон НейманаПравило 30''' ячейки {{---}} совокупность ячеек в сетке (двумерном паркете[[Линейный клеточный автомат, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону эквивалентность МТ|ЛКА]] с двумя состояниями (грань0 и 1) с данной ячейкой.

= Игра «Жизнь» (ADD PICTURES) == Правило 90 ===

'''«Жизнь»Правило 90''' {{---}} [[Линейный клеточный автомат, представляющий из себя бесконечное клетчатое поле, каждая клетка может быть белой или чернойэквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1). За один ход клетки перекрашиваются <br>Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по определенным правилам, в зависимости от их модулю 2 её двух соседей в [[#moore_neighborhood | окрестности Мура]].

== Состояния = Правило 110 ===Каждая клетка поля может быть либо белого, либо черного цвета. Белые клетки называются «живыми», черные {{Определение|definition='''Правило 110''' {{---}} «мертвыми»[[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br>Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.}}[[Файл:Rule110.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 110]]<br>== Правила перехода для Правила 110:{| class="wikitable" style="text-align: center"На каждом шаге автомата ко всем клеткам применяются следующие правила:|-! Текущее состояние трёх соседних клеток| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000|-* В черная клетка, имеющая ровно три белые соседние ! Новое состояние центральной клетки, становится белой («зарождается жизнь»);* Если у белой клетки есть две или три белые соседние клетки, то эта клетка сохраняет свой цвет;| 0 || 1|| 1|| 0||1|| 1|| 1|| 0|}* Если у белой клетки соседей белого цвета меньше двух или больше трёхТак как <tex>1101110_2 = {110}_{10}</tex>, клетка становится черной («умирает от одиночества» или «от перенаселённости»)данное правило называется Правилом 110.<br><br><br><br><br><br><br><br>

В зависимости от начального состояния поля, клетки могут образовывать фигуры, обладающие различными свойствами. По этим свойствам принято делить фигуры на следующие классы:=== Правило 184 ===* '''Устойчивые фигуры''' {{---}} фигуры, которые остаются неизменнымиОпределение* '''Долгожители''' {{---}} фигуры, которые долго меняются, прежде чем стабилизироваться;|definition=* '''ОсцилляторыПравило 184''' {{---}} фигуры[[Линейный клеточный автомат, у которых состояние повторяется через некоторое число поколений, большее эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1;* '''Двигающиеся фигуры (космические корабли)''' {{---}} фигуры, у которых состояние повторяется, но с некоторым смещением;.<br>* '''Ружья''' {{---}} фигуры с повторяющимися состояниями, дополнительно создающие движущиеся фигуры;* '''Паровозы''' {{---}} двигающиеся фигуры с повторяющимися состояниями, которые оставляют за собой другие фигуры в качестве следов;* '''Пожиратели''' {{---}} устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами, уничтожив их;* '''Отражатели''' {{---}} устойчивые или периодические фигуры, способные при столкновении с ними движущихся фигур поменять их направление;* '''Размножители''' {{---}} конфигурации, количество живых клеток в которых растёт как квадрат количества шагов;* '''Дублирующиеся фигуры''' {{---}} фигуры, которые при столкновении с некоторыми фигурами дублируются;* '''Райский сад''' {{---}} конфигурация, которая не может появиться в результате «эволюции», потому что не имеет предшественников[[Файл:Rule184.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 184]]

Наиболее известные представители данных классов Правила перехода для Правила 184:{| class="wikitable" style="text-align:center;"|-! Текущее состояние трёх соседних клеток| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000|-! Новое состояние центральной клетки| 1 || 0|| 1|| 1||1|| 0|| 0|| 0|}Так как <tex>110111000_2 = {184}_{10}</tex>, данное правило называется Правилом 184. = Клеточные автоматы на двумерной решетке === Игра «Жизнь» ==Некоторые из приведенных далее определений были взяты с этого<ref>Игра "Жизнь". URL: https://ru.wikipedia.org/wiki/Игра_«Жизнь»</ref> сайта, а также со смежных с нем страниц.{{Определение|definition='''«Жизнь»''' {{---}} клеточный автомат, представляющий из себя бесконечное клетчатое поле, каждая клетка может быть белой или черной. Состояние, в которое перейдет клетка на следующем шаге, зависит от состояний ее соседей в [[#moore_neighborhood | окрестности Мура]].}}Основную информацию по игре вы можете найти в статье [[Игра «Жизнь» | "игра «Жизнь»"]]. В данном разделе будут рассмотрены далее лишь основные типы и примеры конфигураций данной игры. === Состояния и правила переходов ==={| class="wikitable"|-! scope="col"| Название состояния! scope="col"| Цвет! scope="col"| Переходит в cостояние|-| «Живая клетка»| Белый| «мертвая клетка», если имеет ровно меньше двух или больше трех соседей в состоянии «живая клетка».|-| «Мертвая клетка»| Черный| «живая клетка», если имеет ровно трех соседей в статьесостоянии «живая клетка».|} === Основные элементы ===В данном разделе используются термины из «Словаря Жизни»<ref>«Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm</ref>.

''' TODO: ADD PICTIRESPICTURES'''

==== Устойчивые фигуры ==== Устойчивые фигуры или «натюрморты», делятся на несколько классов<ref>Eric Weisstein. Still Life</ref>:{{Определение|definition=* '''Устойчивый образец ''' {{---}} объект, который является собственным родителем;.}}{{Определение|definition=* '''Натюрморт '''<ref>Eric Weisstein. Still Life</ref> {{---}} устойчивый объект, являющийся конечным и непустым, из которого нельзя выделить непустую устойчивую часть;.* }}{{Определение|definition='''Псевдонатюрморт ''' {{---}} устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортов.}}

==== Долгожители ====

==== Осцилляторы ====

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

==== Ружья ====

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

==== Паровозы ====

'''Грабли''' {{---}} паровозы, оставляющие за собой след исключительно из космических кораблей.<br>

Паровозы условно делят на чистые и грязные:* Чистый паровоз оставляет след, обладающей легко уловимой на глаз периодичностью;* Грязный — сложный, хаотически выглядящий след. ==== Пожиратели ====

==== Отражатели ====

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

Размножители классифицируютсяСуществует несколько видов<ref>Breeder – from Eric Weisstein's Treasure Trove of Life</ref> по размножителей, отличающихся между собой относительной подвижности подвижностью полученных конфигураций. Типы обозначаются кодами из трёх Виды кодируются при сочетаниями трех букв, которые обозначаютописывающие, являются ли первичнаясоответственно, вторичная первичную, вторичную и третичная третичную конфигурации соответственно движущимися (: Д) или неподвижными ({{---}} движущаяся, Н).{{---}} неподвижная:<br>Четыре основных типа:

* ДНД {{---}} паровоз, оставляющий вырабатывающий ружья на своем пути;* ДДН {{---}} грабли, оставляющие вырабатывающий паровозы;* ДДД {{---}} Граблиграбли, оставляющие вырабатывающий грабли, так что нет никаких неподвижных элементов.

=== Дублирующиеся фигуры === === Райский сад =Wireworld =={{Теорема|about=сада ЭдемаОпределение|statementdefinition=Клеточный автомат в евклидовой вселенной является локально инъективным тогда и только тогда, когда он сюръективен.Другими словами, теорема утверждает, что сады Эдема существуют только в тех автоматах, в которых существуют близнецы.|proof=Данная теорема была выдвинута и доказана Эдвардом Муром'''Wireworld'''<ref>MooreТрофимов Д., EНаумов Л. F. (1962)Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизация, Machine models of self-reproduction, Proc2007. SympURL: http://is. Applied Mathematics Тifmo. 14: 17–33ru/works/wireworld/</ref>представляет собой синхронный автомат с двумерной решеткой из квадратов, каждая клетка которой может находиться в одном из четырех состояний.

Теорема применима к «Жизни», поскольку легко найти две различные конфигурации, которые эволюционируют в следующем поколении в одну и ту же конфигурацию<gallery mode="packed" widths=75px heights=200px>Image:OR_wireworld.jpg|''OR''«Мёртвая вселенная» и одинокая живая клетка в «мёртвой вселенной» эволюционируют в одну и ту же конфигурацию, все клетки которой мёртвыеImage:XOR_wireworld.jpg|''XOR''Следовательно, в «Жизни» существуют сады ЭдемаImage:NAND_wireworld.jpg|''NAND''</gallery>

= Автомат Ооно–Кохомото (NOT STARTED) Самовоспроизводящиеся клеточные автоматы ='''TODO: WRITE THE ARTICLE'''Смотреть В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов, которые подробно описаны в статьекниге "Физика процессов эволюции"<refname="physics">Лобанов Эбелинг Вернер, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А.ИДанилова. — М. Модели клеточных автоматов // Компьютерные исследования и моделирование: Эдиториал УРСС, 2010, т2001. 2, № 3, - 328 с. 273-293</ref>:<br>«# Логическая универсальность.## При каких условиях определенный класс автоматов логически универсален?## Существует ли логически универсальный автомат?# Конструируемость.## Может ли один автомат быть построен другим автоматом?## Какой класс автоматов может быть построен каким-то автоматом?# Конструктивная универсальность.## Существует ли конструктивно универсальный автомат? (т. е. автомат, способный построить любой автомат)# Самовоспроизведение.## Существует ли самовоспроизводящийся автомат?## Существует ли автомат, который, помимо самовоспроизведения, может решать и другие задачи?# Эволюция.## Может ли при конструировании автомата автоматом происходить усложнение типа автомата?## Может ли такая эволюция происходить в направлении от менее эффективного к более эффективному автомату? (при надлежащем определении понятия эффективности):::::::::::::::::::::::::::::::::::::::::::::::::::::::».

В то время, как Тьюринг доказал, что [[Машина Тьюринга|машина Тьюринга]] является логически универсальной, Дж. фон Нейман построил автомат<ref name= Классификация Вольфрама "mitin">Г. Г. Малинецкий, Н. А. Митин, С. А. Науменко, “Нанобиология и коды Вольфрама синергетика. Проблемы и идеи (EXPLAIN THE RULESЧасть 2)”, Препринты ИПМ им. М. В. Келдыша, 2005, 081. URL: http://spkurdyumov.ru/uploads/2013/09/miittin.pdf</ref>, удовлетворяющий всем пяти свойствам. Одна из таких моделей будет описана далее. == Автомат фон Неймана ==

'''Классификация ВольфрамаАвтомат фон Неймана'''(клеточная модель самовоспроизведения<refname="neuman_automata">Wolfram, Stephen, A New Kind of ScienceНейман Дж. фон. Теория самовоспроизводящихся автоматов. Wolfram Media, IncМ.: Мир, May 14, 2002. ISBN 1-57955-008-81971</ref> ) {{---}} система классификации клеточных автоматовобъект, представляющий собой поле, основанная на их поведении.в каждой клетке которого находится конечный автомат с 29 состояниями.

Классы=== Состояния ===Определим соседей клетки с помощью векторов, предложенные С. Вольфрамомустановив в координат рассматриваемую клетку:* [[# Эволюция системы заканчивается переходом всех клеток поля в одинаковое состояние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>

Отнесение конкретного клеточного Состояния клеток рассматриваемого автомата к какомуделятся на $4$ различных класса:<br>1. Основное состояние <tex>U</tex> (невозбужденное).<br>2. Транзитивные состояния <tex>T_{u\alpha\varepsilon}</tex>, где:::: <tex>u = \begin{equation*} \begin{cases} 0 &\text{—$\;$ обычное,}\\ 1 &\text{—$\;$ специальное;}\\ \end{cases}\end{equation*}</tex><br>::: <tex> \alpha = 0, \dots, 3 </tex> {{-либо из классов затруднено--}} выходное направление (вправо, вверх, влево, вниз);::: <tex>\varepsilon = \begin{equation*} \begin{cases} 0 &\text{—$\;$ покой,}\\ 1 &\text{—$\;$ возбуждение;}\\ \end{cases}\end{equation*}</tex><br>3. Конфлюэнтные состояния <tex>C_{\varepsilon{\varepsilon}'}</tex>, где:::: <tex>\varepsilon = \begin{equation*} \begin{cases} 0 &\text{—$\;$ покой, так как не указано}\\ 1 &\text{—$\;$ возбуждение;}\\ \end{cases}\end{equation*}</tex><br>::: <tex>{\varepsilon}' = \begin{equation*} \begin{cases} 0 &\text{—$\;$ покой на следующем такте, при каких начальных условиях ожидается указанное выше поведение}\\ 1 &\text{—$\;$ возбуждение на следующем такте;}\\ \end{cases}\end{equation*}</tex><br>4. ПредполагаетсяЧувствительные состояния $S, \; S_0 \;, S_{00} \;, S_{01} \;, S_{000} \;, S_1 \;, что класс следует выбирать по самому сложному поведениюS_{10} \;, которое удастся получитьS_{11}$.

В работе ПДалее объясним природу вышеперечисленных состояний.СДля достижения поставленных целей, Дж. Скаковафон Нейман проводит<refname="neuman_automata"/>Скаков Паналогию с системой нейронных связей, аналогичным образом строя автомат.<br><br>Для передачи информации между клетками по цепочке из клеток же вводятся состояния $T$, причем наличие нейронного импульса регулируется параметром $\varepsilon$. Так как передача должна быть направленным процессом, вводится параметр $\alpha$, обозначающий, с какого направления клетка в данном состоянии будет принимать импульс.<br><br>Работу самих нейронов представляют состояния $С$: каждый нейрон имеет один "выход" и два "входа" (стороны клетки), которые для возбуждения необходимо раздражать одновременно, то есть у "нейрона" должно быть не менее двух соседей в окрестности фон Неймана в состоянии $T_1$, выходные направления которых ориентированы на "нейрон". Классификация поведения одномерных клеточных автоматов. СПбДля экономии количества состояний вводится условность, что каждая сторона клетки может быть как "входом", так и "выходом" нейрона.<br><br>По аналогии с нейронными сетями, автомат должен иметь возможность "расщеплять" передаваемый сигнал, 2007 — URL: http://isт.ifmoе.ru/diploma-theses/_skakov_masterобеспечить возможность передачи его нескольким клеткам сразу.pdf</ref> была предложена новая классификацияДанную функцию выполняют конфлюэнтные состояния, являющаяся уточнением по определению имея несколько "выходов" и модификацией классификации Вольфрама, проведённой с целью уменьшения сложности определения классаодин "вход".<br><br>Состояния $S_{\Sigma0}$ и $S_{Определение\Sigma1}$ используются для совершения прямого (возбуждение невозбужденных клеток) и обратного (приведение к покою возбужденных клеток) процессов. |definition=== Правила переходов ===Функция переходов $F$ определяется следующими соотношениями: # Клетка в состоянии $T_{u\alpha\varepsilon}$ перейдет в состояние:## $U$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}'= v^{{\alpha}'Код Вольфрама}$ в состоянии $T_{u'{\alpha}'{\vartheta}' }$;## $T_{u{\alpha}1}$, если пункт $1.1$ не выполнен, и среди ее соседей найдется клетка, удовлетворяющая одному из условий:### ${\vartheta}'\; : \; \vartheta -{\vartheta}' = v^{{\alpha}'} \neq -v^\alpha$ в состоянии $T_{u{\alpha}'1}$;### ${\vartheta}'\; : \; \vartheta -{\vartheta}' = v^{\beta} система именования клеточных автоматов (как правило\neq -v^\alpha, [[Линейный клеточный автомат\; \beta = 0, эквивалентность МТ|ЛКА]])\dots, предложенная С. Вольфрамом 3$ в 1983 году<ref>Wolfram, Stephen (July 1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55: 601–644</ref>состоянии $C_1$;## $T_{u{\alpha}0}$ во всех остальных случаях.<br>Код основан на наблюдении, что таблица, определяющая новое состояние каждой ячейки # Клетка в автомате, как функция состояний состоянии $C_{\varepsilon\varepsilon'}$ перейдет в его окрестностисостояние:## $U$, может интерпретироваться как число из <tex>k</tex>если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta -цифр {\vartheta}' = v^{{\alpha}'}$ в <tex>S</tex>-арной позиционной системе счисления, где <tex>S</tex> состоянии $T_{1{---\alpha}'1} число состояний$;## $C_{\varepsilon'1}$, которое может иметь каждая ячейка в автоматеесли пункт $2.1$ не выполнен, <tex>k и среди ее соседей найдется клетка ${\vartheta}'\; : \; \vartheta - {\vartheta}' = Sv^{2n + 1{\alpha}'}</tex> $ в состоянии $T_{0{---\alpha}'1} число конфигураций окрестности$, а <tex>n</tex> все остальные такие клетки не будут находиться в состоянии $T_{0{---\alpha}'0} радиус окрестности.$;## $n_{\vartheta}^{t}= C_{\varepsilon'0}$, иначе.# Клетка в состоянии $U$ перейдет в состояние:В соответствии с определением## $S_0$, код может быть вычислен следующим образомесли среди ее соседей найдется ${\vartheta}'\; :\; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1}$;# Определить все возможные конфигурации состояний окрестности данной ячейки;# $U$ во всех остальных случаях.# Интерпретируя каждую конфигурацию как числоКлетка в состоянии $S_\Sigma, \; \Sigma=0, как описано выше\dots, отсортировать их по убыванию;000$ перейдет в состояние:# Для каждой конфигурации определить состояние# $S_{\Sigma1}$, которое будет иметь данная ячейка если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в соответствии с этим правилом на следующей итерациисостоянии $T_{u{\alpha}'1}$;# Интерпретируя полученный список состояний как <tex>S</tex>-арное число# $S_{\Sigma0}$, во всех остальных случаях. === Принцип работы ===Начальная конфигурация описывается конечным набором клеток, преобразовать это число находящихся в десятичноевозбудимом или чувствительном состоянии. Полученное десятичное число является кодом ВольфрамаПравила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана.Более детальное описание механизма работы автомата можно найти в главе 2 книги "Теория самовоспроизводящихся автоматов"<brref name="neuman_automata"/>Далее в статье будут приведены наиболее известные правила.

== Правило 30 Автомат Лэнгтона ==Примером более простого самовоспроизводящегося клеточного автомата является автомат Лэнгтона<ref name== Правило 90 ==== Правило 110 ==== Правило 184 =="mitin" />.<br>

Клеточный автомат '''WireworldАвтомат Лэнгтона'''<ref>Трофимов Д.{{---}} двумерный клеточный самовоспроизводящийся автомат, Наумов Л. Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизацияпредставляющий собой сигнальную ленту, 2007. URL: http://is.ifmoзаключенную между двумя стенками.ru/works/wireworld/</refbr> представляет собой синхронный автомат с двумерной решеткой из квадратов, каждая  В автомате Лэнгтона клетка которой может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех состоянийсоседей.<br>Сигнальная лента несет информацию, необходимую для создания копии автомата.

=== Состояния ===[[Файл==== Сигнальные состояния ====Состояния $3-7$ относят к классу сигнальных:Wireworld_states_meaning_table* $3$ используется при повороте;* $5$ и $6$ используются для самовоспроизведения.jpg|500px|700px|thumb|center|Состояния автомата Wireworld]]

== Правила == Служебные состояния ====На каждом шаге автомата ко всем клеткам применяются следующие правилаСостояния $0-2$ относят к классу служебных:# Пустая клетка остается пустой. # Клетка* $0$, находящаяся в состоянии «голова электрона» переходит в состояние «хвост электрона».идущее вслед за сигнальным задает направление распространения сигнала;# Клетка, находящаяся в состоянии «хвост электрона» переходит в состояние «проводник».* $1$ является «несущей лентой» сигнала;# Клетка, находящаяся в состоянии «проводник» переходит в состояние «голова электрона», в том случае, если среди соседних * Из клеток ровно одна или две находятся в состоянии «голова электрона». Во всех остальных случаях «проводник» остается «проводником».<br>При применении данных правил используется [[#moore_neighborhood | окрестность Мура]] – считается, что с даннойклеткой соседствуют все восемь ее непосредственных соседей$2$ строятся «стенки» автомата.

== Общие закономерности = Принцип работы ===Электрон передвигается со скоростью одна клетка за шаг. Если по проводу навстречу идут два электрона, при столкновении они исчезают. При достижении электроном разветвления проводов по каждому из направлений, кроме исходного, уходит по электрону. Если к разветвлению одновременно подходит <texgallery mode="packed" widths=75px heights=200px>2</tex> и более электронов, все они исчезаютImage:langton_start.jpg|''Начальная конфигурация''Image:langton_copy. При толщине провода в <tex>2jpg|''Порожденная копия после 151 такта''</texgallery> клетки поведение электронов аналогично обычному, при большей толщине поведение становится хаотичным.

== Основные элементы ==* Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$;Большие коллекции функциональных элементов имеются в пакетах 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 компьютера с определенным набором инструкций и регистров, и реализация алгоритма перечисления простых чисел для этого компьютераее конец сигнала $40$;* Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.

=Тьюрмиты ={{Определение|definition= Тактовый генератор '''Тьюрмит'''<ref name===Данный элемент представляет собой «петлю» из клеток проводника"mitin" /> {{---}} это движущаяся по плоскости, к которой подсоединен провод – выход генератораразмеченной клетками, и изначально содержит один электрон. С периодоммашина Тьюринга, равным длине петликоторая хранит свое внутреннее состояние, этот электрон достигает точки соединения петли с выходоми, в зависимости от него и дальше разветвляется от цвета клетки, на два электронакоторой она стоит, один из которых идет по выходу, второй – дальше по петле. Таким образомизменяет свое состояние, этот элемент можно использовать для получения перекрашивает клетку в проводе бесконечного количества электронов, следующих один за другим на расстоянии, регулируемом длиной петлидругой цвет и делает поворот влево или вправо.<br>}}[[Файл:Tact_generator_wireworldTurmite_Langton_ant.jpgpng|100pxthumb|300px|thumb|centerright|Тактовый генераторРезультат работы [https://ru.wikipedia.org/wiki/Муравей_Лэнгтона муравья Лэнгтона] после 27731 итераций]]Каждая строка программы записывается в следующем виде:=== Диод ===Этот функциональный элемент имеет две точки подсоединения к проводам – вход и выход, и его действие состоит в том, что электроны, пришедшие на вход, передаются на выход, а электроны, пришедшие на выход – исчезают. Таким образом, электроны могут перемещаться по проводу, в который включен диод, лишь в одном направлении.<pre><текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние></pre>

[[Файл:Diode_wireworld.jpg|100px|300px|thumb|center|ДиодИгра «Жизнь»]] эмулируется<ref name=== Логические элементы OR, XOR и NAND ===Каждый из этих элементов имеет "mitin" /> с помощью одного тьюрмита: он по 2 входа очереди обходит все клетки поля и выход. Наличие электрона на входе соответствует логическому значению «единица», отсутствие – логическому значению «ноль». Электрон на выходе появляется согласно таблице истинности соответствующей логической операции.<br>* Так, для элемента '''OR''' электрон на любом из входов, или электроны на обоих входах одновременно дают электрон на выходерисует новую конфигурацию в соответствии с правилами игры.<br>* Для элемента '''XOR''' электрон на любом из входов дает электрон на выходе, но В области исследований модели ДНК при одновременной подаче электронов на оба входа они исчезают, моделировании активно используются взаимодействующие и электрон на выходе не создается.плиточные тьюрмиты<brref name="mitin" />* Элемент '''NAND''' работает как тактовый генератор, и посылает электроны на выход во всех случаях, за исключением случая, когда на оба входа одновременно подаются электроны.<br>'''TODO: FIX FORMATTING'''[[File:OR_wireworld.jpg|75px|150px|center|thumb|OR]][[File:XOR_wireworld.jpg|75px|150px|center|thumb|XOR]][[File:NAND_wireworld.jpg|75px|150px|center|thumb|NAND]] === Двоичный сумматор ===Рассмотрим пример более сложной структуры, состоящей из множества простых элементов – двоичный сумматор. Его функция заключается в том, что при подаче на два входа закодированных особым образом чисел, через фиксированное количество шагов (в изображенном примере – 48) на выходе появится закодированное таким же образом число – сумма чисел на входах. Числа кодируются в двоичном виде, от младших битов к старшим, каждый бит кодируется наличием или отсутствием электрона на определенной позиции. Нарисунке ниже эти позиции отмечены точками и изображениями чисел (значений каждого бита) из клеток в состоянии «проводник» по краям входов и выхода. Сами по себе эти отметки не несут никакой функциональной нагрузки, а служат лишь в пояснительных целях. Изображенный ниже сумматор имеет разрядность входов три бита, но можно получить сумматор с любой разрядностью, удлинив или укоротив провода на входах и выходе. [[File:Binary_summator_wireworld.jpg|200px|350px|center|thumb|Двоичный сумматор]]

* [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 Муравей_Лэнгтона Муравей Лэнгтона]* Лобанов А.И. Модели клеточных автоматов<ref>Лобанов А.И. Модели клеточных автоматов // Компьютерные исследования и моделирование, 2010, т. 2, № 3, с. 273-293. URL: http://vst.ics.org.ru/uploads/crmissues/kim_2010_2_3/crm10304.pdf</ref>