Изменения

= Базовые определения ={{В разработкеОпределение|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

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

= Игра «Жизнь» (ADD PICTURES) Классификация клеточных автоматов === Классификация Вольфрама ==

'''«Жизнь»Классы Вольфрама''' <ref>Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8</ref> {{---}} клеточный автомат, представляющий из себя бесконечное клетчатое поле, каждая клетка может быть белой или черной. За один ход клетки перекрашиваются по определенным правиламклассификация клеточных автоматов, в зависимости от основанная на их соседей в [[#moore_neighborhood | окрестности Мура]]поведении.

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

Теорема применима к «Жизни», поскольку легко найти две различные конфигурации=== Общие закономерности ===Движение "электрона" в "цепи" происходит со следующими закономерностями:* При прохождении электроном разветвления "цепи", которые эволюционируют в следующем поколении в одну и ту же конфигурацию.каждое из новых направлений уходит по "электрону";«Мёртвая вселенная» * При одновременном столкновении трёх и одинокая живая клетка в «мёртвой вселенной» эволюционируют в одну и ту же конфигурациюболее "электронов", все клетки которой мёртвыеони исчезают.Следовательно* При толщине "провода" больше $2$, в «Жизни» существуют сады Эдема"электроны" начинают двигаться хаотично.

= Автомат Ооно–Кохомото (NOT STARTED) == Основные элементы ==='''TODO: WRITE THE ARTICLE'''В данной статье приведены лишь основные простейшие элементы, которые можно составить в 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>, 2010, тWireWorld<ref>"WireWorld". URL:http://karl.kiwi.gen.nz/CA-Wireworld.html. 2, № 3, </ref>; спомощью элементов Wireworld также был построен<ref>"The Wireworld computer". 273URL:http://www.quinapalus.com/wi-293index.html</ref>компьютер.

= Классификация Вольфрама и коды Вольфрама (ADD PICS)={{Определение|definition== Тактовый генератор ===='''Классы Вольфрама'''<ref>Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8</ref> {{---}} система классификации клеточных автоматов, основанная на их поведении.}}Классы, предложенные С. Вольфрамом:# Эволюция системы заканчивается переходом всех клеток поля в одинаковое состояние;# Существует много конечных состояний, но все они состоят из набора простых структур, которые остаются неизменными или повторяются через некоторое небольшое число шагов;# Поведение сложное, во многих отношениях выглядит хаотическим;# Смесь хаоса и порядка: порождаются локальные структуры, которые перемещаются и взаимодействуют друг с другом очень сложным образом.Отнесение конкретного клеточного автомата к какому-либо из классов затрудненоДанный элемент используется для получения электронов, так как не указано, при каких начальных условиях ожидается указанное выше поведение. Предполагаетсякаждом прохождении разветвления электроном, что класс следует выбирать движущимся по самому сложному поведениюпетле генератора, которое удастся получитьобразуется новый электрон. <br><br>В работе П.С. Скакова<ref>Скаков П.С. Классификация поведения одномерных клеточных автоматов. СПб., 2007 — URL: http://is.ifmo.ru/diploma-theses/_skakov_master.pdf</ref> была предложена новая классификация, являющаяся уточнением и модификацией классификации Вольфрама, проведённой с целью уменьшения сложности определения классаЧастота появления электронов регулируется длиной петли.

{{Определение<gallery mode="packed-hover">Image:Diode_wireworld.jpg|100px|300px|definition=''Диод'Код Вольфрама''' {{---}} система именования клеточных автоматов (как правило</gallery> ==== Логические элементы OR, [[Линейный клеточный автоматXOR и NAND ====Данный элемент действует точно так же, эквивалентность МТ|ЛКА]]), предложенная Скак и одноименные логические элементы<ref>Дизъюнкция. URL: https://ru.wikipedia.org/wiki/Дизъюнкция</ref><ref>Исключающее «или». URL: https://ru.wikipedia. Вольфрамом в 1983 годуorg/wiki/Исключающее_«или»</ref>Wolfram, Stephen <ref>NAND (July 1983логический элемент). URL: https://ru.wikipedia.org/wiki/Штрих_Шеффера</ref>.<br> <gallery mode="Statistical Mechanics of Cellular Automatapacked"widths=75px heights=200px>Image:OR_wireworld. Reviews of Modern Physicsjpg|''OR''Image:XOR_wireworld. 55jpg|''XOR''Image: 601–644NAND_wireworld.jpg|''NAND''</refgallery>.

Код основан на наблюдении= Самовоспроизводящиеся клеточные автоматы =В ходе работы над математическими и логическими проблемами самовоспроизведения, что таблицаДж. фон Нейман поставил пять основных вопросов, определяющая новое состояние каждой ячейки которые подробно описаны в автомате, как функция состояний в его окрестности, может интерпретироваться как число из книге "Физика процессов эволюции"<tex>k</tex>-цифр в <texref name="physics">S</tex>-арной позиционной системе счисленияЭбелинг Вернер, где <tex>S</tex> {{---}} число состоянийЭнгель Андреас, которое может иметь каждая ячейка в автоматеФайстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.: Эдиториал УРСС, <tex>k = S^{2n + 1}2001. - 328 с.</texref> {{---}} число конфигураций окрестности, а :<texbr>n</tex> {{---}} радиус окрестности«# Логическая универсальность.## При каких условиях определенный класс автоматов логически универсален?## Существует ли логически универсальный автомат?# Конструируемость.}}## Может ли один автомат быть построен другим автоматом?В соответствии с определением, код ## Какой класс автоматов может быть вычислен следующим образом:построен каким-то автоматом?# Конструктивная универсальность.## Существует ли конструктивно универсальный автомат? (т. е. автомат, способный построить любой автомат)# Самовоспроизведение.# Определить все возможные конфигурации состояний окрестности данной ячейки;# Существует ли самовоспроизводящийся автомат?# Интерпретируя каждую конфигурацию как число# Существует ли автомат, как описано вышекоторый, отсортировать их по убыванию;помимо самовоспроизведения, может решать и другие задачи?# Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с этим правилом на следующей итерации;Эволюция.## Может ли при конструировании автомата автоматом происходить усложнение типа автомата?# Интерпретируя полученный список состояний как <tex>S</tex>-арное число, преобразовать это число # Может ли такая эволюция происходить в десятичное. Полученное десятичное число является кодом Вольфраманаправлении от менее эффективного к более эффективному автомату? (при надлежащем определении понятия эффективности):::::::::::::::::::::::::::::::::::::::::::::::::::::::».

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

== Правило 30 Автомат фон Неймана ==

'''Правило 30Автомат фон Неймана''' (клеточная модель самовоспроизведения<ref name="neuman_automata">Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} [[Линейный клеточный объект, представляющий собой поле, в каждой клетке которого находится конечный автомат, эквивалентность МТ|ЛКА]] с двумя 29 состояниями (0 и 1).

== Правило 90 = Состояния ==={{ОпределениеОпределим соседей клетки с помощью векторов, установив в координат рассматриваемую клетку:* [[#neiman_neighborhood |definitionОкрестность фон Неймана]]: <tex>v^0 =(1, 0) \;\;\; v^1 = (0, 1) \;\;\; v^2 = (-1, 0) \;\;\; v^3 = (0, -1)</tex>;'''Правило 90''' * Клетки, дополняющие окрестность фон Неймана до [[#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 и 1, \dots , 3), F</tex> {{---}} функция переходов.<br>Шаг работы <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{—$\;$ специальное;}\\Правила перехода для Правила 90: \end{cases}\end{| classequation*}</tex><br>::: <tex> \alpha ="wikitable" style="text0, \dots, 3 </tex> {{--align: center"|-}} выходное направление (вправо, вверх, влево, вниз);! Текущее состояние трёх соседних клеток::: <tex>| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000\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||1|| 0|| 1|| 0&\text{—$\;$ возбуждение;}\\ \end{cases}|\end{equation*}</tex><br>::: <tex>{\varepsilon}' == Правило 110 ==\begin{equation*} \begin{cases} 0 &\text{—$\;$ покой на следующем такте,}\\ 1 &\text{—$\;$ возбуждение на следующем такте;}\\ \end{Определениеcases}|definition=\end{equation*}</tex><br>'''Правило 110''' 4. Чувствительные состояния $S, \; S_0 \;, S_{00} \;, S_{01} \;, S_{000} \;, S_1 \;, S_{---10}\;, S_{11} [[Линейный клеточный $.<br><br>Далее объясним природу вышеперечисленных состояний. Для достижения поставленных целей, Дж. фон Нейман проводит<ref name="neuman_automata"/> аналогию с системой нейронных связей, аналогичным образом строя автомат.<br><br>Для передачи информации между клетками по цепочке из клеток же вводятся состояния $T$, причем наличие нейронного импульса регулируется параметром $\varepsilon$. Так как передача должна быть направленным процессом, вводится параметр $\alpha$, обозначающий, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1)какого направления клетка в данном состоянии будет принимать импульс.<br><br>Шаг работы автомата состоит Работу самих нейронов представляют состояния $С$: каждый нейрон имеет один "выход" и два "входа" (стороны клетки), которые для возбуждения необходимо раздражать одновременно, то есть у "нейрона" должно быть не менее двух соседей в одновременной замене значения окрестности фон Неймана в любой ячейке состоянии $T_1$, выходные направления которых ориентированы на сумму "нейрон". Для экономии количества состояний вводится условность, что каждая сторона клетки может быть как "входом", так и "выходом" нейрона.<br><br>По аналогии с нейронными сетями, автомат должен иметь возможность "расщеплять" передаваемый сигнал, т.е. обеспечить возможность передачи его нескольким клеткам сразу. Данную функцию выполняют конфлюэнтные состояния, по модулю 2 её двух соседейопределению имея несколько "выходов" и один "вход".<br><br>Состояния $S_{\Sigma0}$ и $S_{\Sigma1}$ используются для совершения прямого (возбуждение невозбужденных клеток) и обратного (приведение к покою возбужденных клеток) процессов. === Правила перехода для Правила 110переходов ===Функция переходов $F$ определяется следующими соотношениями: # Клетка в состоянии $T_{u\alpha\varepsilon}$ перейдет в состояние:## $U$, если среди ее соседей найдется ${| class\vartheta}'\; : \; \vartheta - {\vartheta}' ="wikitable" stylev^{{\alpha}'}$ в состоянии $T_{u'{\alpha}'{\vartheta}'}$;## $T_{u{\alpha}1}$, если пункт $1.1$ не выполнен, и среди ее соседей найдется клетка, удовлетворяющая одному из условий:### ${\vartheta}'\; : \; \vartheta - {\vartheta}' ="textv^{{\alpha}'} \neq -alignv^\alpha$ в состоянии $T_{u{\alpha}'1}$;### ${\vartheta}'\; : center"\; \vartheta - {\vartheta}' = v^{\beta} \neq -v^\alpha, \; \beta = 0,\dots, 3$ в состоянии $C_1$;|-## $T_{u{\alpha}0}$ во всех остальных случаях.! Текущее # Клетка в состоянии $C_{\varepsilon\varepsilon'}$ перейдет в состояние трёх соседних клеток:| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000## $U$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{1{\alpha}'1}$;|## $C_{\varepsilon'1}$, если пункт $2.1$ не выполнен, и среди ее соседей найдется клетка ${\vartheta}'\; : \; \vartheta -{\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{0{\alpha}'1}$, а все остальные такие клетки не будут находиться в состоянии $T_{0{\alpha}'0}$;## $n_{\vartheta}^{t} = C_{\varepsilon'0}$, иначе.! Новое # Клетка в состоянии $U$ перейдет в состояние центральной клетки:| 0 || ## $S_0$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1|| 1|| }$;## $U$ во всех остальных случаях.# Клетка в состоянии $S_\Sigma, \; \Sigma=0||,\dots,000$ перейдет в состояние:## $S_{\Sigma1}$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1|| 1|| 1|| 0}$;|## $S_{\Sigma0}$, во всех остальных случаях. Так как === Принцип работы ===Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана.Более детальное описание механизма работы автомата можно найти в главе 2 книги "Теория самовоспроизводящихся автоматов"<texref name="neuman_automata"/>01101110 _2 . = 110_10= Автомат Лэнгтона ==Примером более простого самовоспроизводящегося клеточного автомата является автомат Лэнгтона<ref name="mitin" /tex>, данное правило называется Правилом 110.<br>

'''Правило 184Автомат Лэнгтона''' {{---}} [[Линейный двумерный клеточный самовоспроизводящийся автомат, эквивалентность МТ|ЛКА]] с представляющий собой сигнальную ленту, заключенную между двумя состояниями (0 и 1)стенками.<br>}}Правила перехода для Правила 184:{| class="wikitable" style="text-align:center;"|-! Текущее состояние трёх соседних клеток| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000|-! Новое состояние центральной клетки| 1 || 0|| 1|| 1||1|| 0|| 0|| 0|}

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

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

== Общие закономерности == Служебные состояния ====Электрон передвигается со скоростью одна клетка за шаг. Если по проводу навстречу идут два электрона, при столкновении они исчезают. При достижении электроном разветвления проводов по каждому из направлений, кроме исходного, уходит по электрону. Если Состояния $0-2$ относят к разветвлению одновременно подходит <tex>2</tex> и более электроновклассу служебных:* $0$, все они исчезают. При толщине провода идущее вслед за сигнальным задает направление распространения сигнала;* $1$ является «несущей лентой» сигнала;* Из клеток в <tex>состоянии $2</tex> клетки поведение электронов аналогично обычному, при большей толщине поведение становится хаотичным$ строятся «стенки» автомата.

== Основные элементы = Принцип работы ===Большие коллекции функциональных элементов имеются в пакетах Mirek's Cellebration<ref>gallery mode="Mirek's Cellebrationpacked". URL:http://mirekw.com/ca/index.html</refwidths=75px heights=200px> и Zillions of Games<ref>"Zillions of Games". URL:httpImage://zillionsofgameslangton_start.com</ref>, а также на сайте WireWorld<ref>"WireWorld". URLjpg|''Начальная конфигурация''Image:http://karllangton_copy.kiwi.gen.nz/CA-Wireworld.html. </ref>. Кроме того, на сайте The Wireworld computer<ref>"The Wireworld computer". URL:http://www.quinapalus.com/wi-index.htmljpg|''Порожденная копия после 151 такта''</refgallery> приводится пример построения в WireWorld компьютера с определенным набором инструкций и регистров, и реализация алгоритма перечисления простых чисел для этого компьютера.

=== Тактовый генератор ===* Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$;Данный элемент представляет собой «петлю» из клеток проводника, к которой подсоединен провод – выход генератора, и изначально содержит один электрон. С периодом, равным длине петли, этот электрон достигает точки соединения петли с выходом, и дальше разветвляется на два электрона, один из которых идет по выходу, второй – дальше по петле. Таким образом, этот элемент можно использовать для получения в проводе бесконечного количества электронов, следующих один за другим * Поворот ленты влево достигается путем передачи на расстоянии, регулируемом длиной петли.<br>ее конец сигнала $40$;[[Файл:Tact_generator_wireworld* Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.jpg|100px|300px|thumb|center|Тактовый генератор]]

=Тьюрмиты ={{Определение|definition= Диод '''Тьюрмит'''<ref name===Этот функциональный элемент имеет две точки подсоединения к проводам – вход и выход"mitin" /> {{---}} это движущаяся по плоскости, и его действие состоит в томразмеченной клетками, что электронымашина Тьюринга, пришедшие на входкоторая хранит свое внутреннее состояние, передаются на выходи, а электроныв зависимости от него и от цвета клетки, пришедшие на выход – исчезают. Таким образомкоторой она стоит, электроны могут перемещаться по проводуизменяет свое состояние, перекрашивает клетку в который включен диод, лишь другой цвет и делает поворот влево или вправо.}}[[Файл:Turmite_Langton_ant.png|thumb|300px|right|Результат работы [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>