Изменения

'''Клеточный автомат''' <ref>Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title=Список_заданий_по_ДМ_2к_2020_весна</ref> представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии.<br><br>

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

'''Окрестность фон Неймана''' <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>.

'''Классы Вольфрама'''<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>:''# Эволюция системы заканчивается переходом всех клеток поля в одинаковое состояние;# Существует много конечных состояний, но все они состоят из набора простых структур, которые остаются неизменными или повторяются через некоторое небольшое число шагов;# Поведение сложное, во многих отношениях выглядит хаотическим;# Смесь хаоса и порядка: порождаются локальные структуры, которые перемещаются и взаимодействуют друг с другом очень сложным образом.Отнесение конкретного клеточного автомата к какому-либо из классов затруднено, так как не указано, при каких начальных условиях ожидается указанное выше поведение. Предполагается, что класс следует выбирать по самому сложному поведению, которое удастся получить. <br><br>В работе П.С. Скакова<ref name="skakov" /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># Все объекты расширяются: в наборе правил есть правило B1 (клетка переходит Однако, данная классификация так же имела серьезные проблемы, и, в состояние 1конечном счете, если она имеет ровно одного соседа в состоянии 1);не удовлетворяла своему назначению.# Нет расширяющихся объектов: в наборе правил нет правил B2 или B3 (клетка переходит в состояние 1Более подробные описания данных классификаций, а также других наиболее распространенных, если она имеет ровно двух / трёх соседей можно найти в состоянии 1)работе П.# Уменьшение невозможно: в наборе правил есть правила S01234 или B23С. Скакова<ref name="skakov" /S0 (клетка сохраняет состояние 1>. В ней, если у неё есть от нуля до четырех соседей в состоянии 1/клетка переходит в состояние 1 при наличии у неё ровно двух или трёх соседей в состоянии 1 том числе, были выделены основные достоинства и недостатки различных классификаций, и сохраняет это состояниепредложена новая, если у неё нет соседей в состоянии 1).# Возможны являющаяся уточнением и расширение модификацией существующих и уменьшение объектов: все остальные случаирешающая многие их проблемы.

'''Код Вольфрама''' {{---}} система именования клеточных автоматов (как правило, [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]]), предложенная С. Вольфрамом в 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> {{---}} радиус окрестности.

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

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

<br>Далее в статье будут приведены наиболее известные правила. Рассматривается бесконечный одномерный массив ячеек клеточного автомата <br>Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя возможными состояниями. Каждая из клеток имеет начальное состояние. В дискретные моменты времени каждая клетка изменяет своё состояние, причем оно зависит в зависимости от предыдущего состояния этой ячейки ее ближайших соседей и предыдущего ее состояния двух соседних ячеекна предыдущем шаге. '''TODO: ADD PICTIRES'''

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

Так как <tex>01101110 _2 1101110_2 = 110_10{110}_{10}</tex>, данное правило называется Правилом 110.<br><br><br><br><br><br><br><br> 

'''«Жизнь»''' {{---}} клеточный автомат, представляющий из себя бесконечное клетчатое поле, каждая клетка может быть белой или черной. За один ход клетки перекрашиваются по определенным правиламСостояние, в зависимости которое перейдет клетка на следующем шаге, зависит от их состояний ее соседей в [[#moore_neighborhood | окрестности Мура]].

Дополнительную информацию по игре вы можете найти в статье [[Игра «Жизнь» | "игра «Жизнь»"]]. === Состояния и правила переходов ===Каждая клетка поля может быть либо белого, либо черного цвета. Белые клетки называются «живыми», черные {{-| class="wikitable"|--}} «мертвыми».! scope="col"| Название состояния! scope="col"| Цвет! scope= Правила ==="col"| Переходит в cостояние|-| «Живая клетка»На каждом шаге автомата ко всем клеткам применяются следующие правила:| Белый* В черная клетка| «мертвая клетка», имеющая если имеет ровно три белые соседние клетки, становится белой («зарождается жизнь»);* Если у белой клетки есть две или три белые соседние клетки, то эта клетка сохраняет свой цвет;* Если у белой клетки соседей белого цвета меньше двух или больше трёхтрех соседей в состоянии «живая клетка».|-| «Мертвая клетка»| Черный| «живая клетка», клетка становится черной («умирает от одиночества» или «от перенаселённости»)если имеет ровно трех соседей в состоянии «живая клетка».|}

В зависимости от начального состояния поля, клетки могут образовывать фигуры, обладающие различными свойствами. По этим свойствам принято делить фигуры на следующие классы:* '''Устойчивые фигуры''' {{---}} фигуры, которые остаются неизменными* '''Долгожители''' {{---}} фигуры, которые долго меняются, прежде чем стабилизироваться;* '''Осцилляторы''' {{---}} фигуры, у которых состояние повторяется через некоторое число поколений, большее 1;* '''Двигающиеся фигуры (космические корабли)''' {{---}} фигуры, у которых состояние повторяется, но с некоторым смещением;* '''Ружья''' {{---}} фигуры с повторяющимися состояниями, дополнительно создающие движущиеся фигуры;* '''Паровозы''' {{---}} двигающиеся фигуры с повторяющимися состояниями, которые оставляют за собой другие фигуры в качестве следов;* '''Пожиратели''' {{---}} устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами, уничтожив их;* '''Отражатели''' {{---}} устойчивые или периодические фигуры, способные при столкновении с ними движущихся фигур поменять их направление;* '''Размножители''' {{---}} конфигурации, количество живых клеток в которых растёт как квадрат количества шагов;Наиболее известные представители данных классов будут рассмотрены далее в статье. ''' 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>Четыре основных типа:

* ДНД {{---}} паровоз, оставляющий вырабатывающий ружья на своем пути;* ДДН {{---}} грабли, оставляющие вырабатывающий паровозы;* ДДД {{---}} Граблиграбли, оставляющие вырабатывающий грабли, так что нет никаких неподвижных элементов. ==== Райский сад ====[[#edem_theorem | Теорема]] применима к «Жизни», поскольку легко найти две различные конфигурации, которые эволюционируют в следующем поколении в одну и ту же конфигурацию.«Мёртвая вселенная» и одинокая живая клетка в «мёртвой вселенной» эволюционируют в одну и ту же конфигурацию, все клетки которой мёртвые.Следовательно, в «Жизни» существуют сады Эдема.

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

! scope="col"| ЗначениеПереходит в состояние

| Клетка, не занятая проводником

| По проводнику могут распространяться электроны«голова электрона», если имеет ровно одного или двух [[#moore_neighborhood | соседей]] в состоянии «голова электрона»

| Проводник, занятый электроном: вместе с «хвостом «хвост электрона» задает направление движения электрона.

| Проводник, занятый электроном: вместе с «головой электрона» задает направление движения электрона.«проводник»

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

Большие коллекции функциональных элементов имеются В данной статье приведены лишь основные простейшие элементы, которые можно составить в 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>. Кроме того, на сайте The ; с помощью элементов Wireworld computerтакже был построен<ref>"The Wireworld computer". URL:http://www.quinapalus.com/wi-index.html</ref> приводится пример построения в WireWorld компьютера с определенным набором инструкций и регистров, и реализация алгоритма перечисления простых чисел для этого компьютеракомпьютер.

Данный элемент представляет собой «петлю» из клеток проводникаиспользуется для получения электронов, так как при каждом прохождении разветвления электроном, к которой подсоединен провод – выход движущимся по петле генератора, и изначально содержит один образуется новый электрон. С периодом, равным длине петли, этот электрон достигает точки соединения петли с выходом, и дальше разветвляется на два электрона, один из которых идет по выходу, второй – дальше по петле. Таким образом, этот элемент можно использовать для получения в проводе бесконечного количества Частота появления электронов, следующих один за другим на расстоянии, регулируемом регулируется длиной петли.<br>

Этот функциональный Данный элемент имеет две точки подсоединения к проводам – вход и выходдействует точно так же, и его действие состоит в том, что электроны, пришедшие на вход, передаются на выход, а электроны, пришедшие на выход – исчезаюткак одноименный элемент<ref>Диод. URL: https://ru.wikipedia. Таким образом, электроны могут перемещаться по проводу, в который включен диод, лишь в одном направленииorg/wiki/Диод</ref> электрической цепи.

Каждый из этих элементов имеет по 2 входа Данный элемент действует точно так же, как и выхододноименные логические элементы<ref>Дизъюнкция. Наличие электрона на входе соответствует логическому значению «единица», отсутствие – логическому значению «ноль»URL: https://ru. Электрон на выходе появляется согласно таблице истинности соответствующей логической операцииwikipedia.org/wiki/Дизъюнкция<br/ref>* Так, для элемента '''OR''' электрон на любом из входов, или электроны на обоих входах одновременно дают электрон на выходе<ref>Исключающее «или». URL: https://ru.wikipedia.org/wiki/Исключающее_«или»<br/ref>* Для элемента '''XOR''' электрон на любом из входов дает электрон на выходе, но при одновременной подаче электронов на оба входа они исчезают, и электрон на выходе не создается<ref>NAND (логический элемент). URL: https://ru.wikipedia.org/wiki/Штрих_Шеффера<br/ref>* Элемент '''NAND''' работает как тактовый генератор, и посылает электроны на выход во всех случаях, за исключением случая, когда на оба входа одновременно подаются электроны.<br>

==== Двоичный сумматор ====Рассмотрим пример более сложной структуры, состоящей из множества простых элементов – двоичный сумматор. Его функция заключается в том, что при подаче на два входа закодированных особым образом чисел, через фиксированное количество шагов (в изображенном примере – 48) на выходе появится закодированное таким же образом число – сумма чисел на входах. Числа кодируются в двоичном виде, от младших битов к старшим, каждый бит кодируется наличием или отсутствием электрона на определенной позиции. Нарисунке ниже эти позиции отмечены точками и изображениями чисел (значений каждого бита) из клеток в состоянии «проводник» по краям входов и выхода. Сами по себе эти отметки не несут никакой функциональной нагрузки, а служат лишь в пояснительных целях. Изображенный ниже сумматор имеет разрядность входов три бита, но можно получить сумматор с любой разрядностью, удлинив или укоротив провода на входах и выходе.<gallery mode="packed-hover" widths=200px heights=350px>Image:Binary_summator_wireworld.jpg|''Двоичный сумматор''</gallery> = Самовоспроизводящиеся клеточные автоматы (UNDER CONSTRUCTION) ={{В разработке}}В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов, которые подробно описаны в книге "Физика процессов эволюции"<ref name="physics">Эбелинг Вернер, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.:Эдиториал УРСС, 2001. - 328 с.</ref>:<br>«

## Существует ли конструктивно универсальный автомат ? (т. е. автомат, способный построить любой автомат)?

## Существует ли автомат, который , помимо самовоспроизведения , может решать и другие задачи?

## Может ли такая эволюция происходить в направлении от менее эффективного к более эффективному автомату ? (при надлежащем определении понятия эффективности)?:::::::::::::::::::::::::::::::::::::::::::::::::::::::».

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

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

Из 29 состояний одно является невозбудимым (покой), 20 относятся к возбудимым, 8 – к чувствительным.<br>На бесконечном поле задается исходный конечный набор клеток, имеющих не невозбудимое состояние, затем клеточная система начинает работать по правилам переходов. Логическая структура бесконечного клеточного автомата такова, что через некоторый промежуток времени в некоторой области клеточного пространства, отличной от начального условия, появляется копия начального автомата. От дискретной клеточной модели самовоспроизведения фон Нейман собирался перейти к непрерывной модели, которая представляла бы систему дифференциальных уравнений в частных производных диффузионного типа. К сожалению, он не успел осуществить свой замысел.  === Формальное описание Состояния ===Данное описание взято из §5.3 книги<ref name="physics">Эбелинг ВернерОпределим соседей клетки с помощью векторов, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.установив в координат рассматриваемую клетку: Эдиториал УРСС, 2001. - 328 с.</ref>.<br>Как было сказано выше, * [[#neiman_auto neiman_neighborhood | автомат Окрестность фон Неймана]] представляет клеточный автомат: <tex>v^0 = (1, 0) \;\;\; v^1 = (0, у которого каждая клетка может находиться в 29 состояниях. Клеточный автомат состоит из многих однотипных автоматов1) \;\;\; v^2 = (-1, 0) \;\;\; v^3 = (0, расположенных в узлах решетки-1)</tex>; выход каждого автомата служит входом для * Клетки, дополняющие окрестность фон Неймана до [[#neiman_neighborhood moore_neighborhood | соседних клетококрестности Мура]].<br>Нумерует клетки радиус-вектор : <tex>\vartheta v^4 = (i1, j1), \; i,j \;\; v^5 = 0(-1, 1) \pm ;\;\; v^6 = (-1, -1) \;\pm 2;\; v^7 = (1, \dots-1)</tex>.<br><br>'''TODOСостояние клетки $\vartheta$ на $t$-ом шаге: ADD PICTURE'''<brtex>n_{t}^{\vartheta} = F(n_{t - 1}^\vartheta; n_{t - 1}^{Определение\vartheta + v^\alpha} \; |definition\; \alpha =Назовем '''ближайшими соседями''' клетки те клетки0, что лежат в ее [[#neiman_neighborhood | окрестности фон Неймана]]; клетки\dots , дополняющие [[#neiman_neighborhood | окрестность фон Неймана]] до [[#moore_neighborhood | окрестность Мура]]3), назовем '''ближними соседями'''.F</tex> {{---}}функция переходов.<br>

Определим восемь векторов расстояния ('''TODO: ADD PICTURE''')Состояния клеток рассматриваемого автомата делятся на $4$ различных класса:<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><br>В соотношении выше <tex>F</tex> зависит от <tex>5</tex> переменных, которые могут принимать <tex>N</tex> значений, а поскольку <tex>F</tex> также принимает <tex>N</tex> различных значений при каждом значении аргумента, всего существует <tex>m = N^{N^5}</tex> различных функций <tex>FU</tex> (различных моделейневозбужденное).<br><br>Автомат фон Неймана имеет <tex>N = 29</tex> различных состояний:<br>12. Транзитивные состояния (импульсы) <tex>T_{u\alpha\varepsilon}</tex>, где:

0 &\text{—$\;$ обычное состояние,}\\ 1 &\text{—$\;$ специальное состояние;}\\ \end{cases}\end{equation*}</tex><br>::: <tex>\alpha = \begin{equation*} \begin{cases} 0 &\text{—$\;$ вправо,}\\ 1 &\text{—$\;$ вверх,}\\ 2 &\text{—$\;$ влево,}\\ 3 &\text{—$\;$ вниз;}\\

0 &\text{—$\;$ состояние покояпокой,}\\ 1 &\text{—$\;$ возбужденное состояниевозбуждение;}\\

23. Конфлюэнтные состояния <tex>C_{\varepsilon{\varepsilon}'}</tex>, где:

0 &\text{—$\;$ состояние покояпокой,}\\ 1 &\text{—$\;$ возбужденное состояниевозбуждение;}\\

0 &\text{—$\;$ состояние покоя покой на следующем такте,}\\ 1 &\text{—$\;$ возбужденное состояние возбуждение на следующем такте;}\\

34. Чувствительные состояния $S, \; S_0 \;, S_{00} \;, S_{01} \;, S_{000} \;, S_1 \;, S_{10} \;, S_{11}$. Основное состояние <br><texbr>UДалее объясним природу вышеперечисленных состояний. Для достижения поставленных целей, Дж. фон Нейман проводит<ref name="neuman_automata"/tex> (невозбужденное)аналогию с системой нейронных связей, аналогичным образом строя автомат.<br><br>4Для передачи информации между клетками по цепочке из клеток же вводятся состояния $T$, причем наличие нейронного импульса регулируется параметром $\varepsilon$. Так как передача должна быть направленным процессом, вводится параметр $\alpha$, обозначающий, с какого направления клетка в данном состоянии будет принимать импульс. Чувствительные (сенситивные) состояния <texbr>S_{\Sigma}</texbr>, где:Работу самих нейронов представляют состояния $С$::: <tex>\Sigma = \Thetaкаждый нейрон имеет один "выход" и два "входа" (стороны клетки), которые для возбуждения необходимо раздражать одновременно, 0то есть у "нейрона" должно быть не менее двух соседей в окрестности фон Неймана в состоянии $T_1$, 1выходные направления которых ориентированы на "нейрон". Для экономии количества состояний вводится условность, 00что каждая сторона клетки может быть как "входом", 01так и "выходом" нейрона.<br><br>По аналогии с нейронными сетями, 10автомат должен иметь возможность "расщеплять" передаваемый сигнал, 11т.е. обеспечить возможность передачи его нескольким клеткам сразу. Данную функцию выполняют конфлюэнтные состояния, 000по определению имея несколько "выходов" и один "вход".</texbr><br>Состояния $S_{\Sigma0}$ и$S_{\Sigma1}$ используются для совершения прямого (возбуждение невозбужденных клеток) и обратного (приведение к покою возбужденных клеток) процессов. === Правила переходов ===Функция переходов $F$ определяется следующими соотношениями: # Клетка в состоянии $T_{u\alpha\varepsilon}$ перейдет в состояние:## $U$, если среди ее соседей найдется ${\vartheta}'\; : <tex>S_\; \vartheta - {0000\vartheta} ' = v^{{\alpha}'}$ в состоянии $T_{000u'{\alpha}'{\vartheta}'}$;## $T_{u{\alpha}1}$, если пункт $1.1$ не выполнен, и среди ее соседей найдется клетка,</tex><br>удовлетворяющая одному из условий:### ${\vartheta}'\; ::: <tex>S_\; \vartheta - {0001\vartheta} ' = v^{{\alpha}'} \neq -v^\alpha$ в состоянии $T_{010u{\alpha}'1},</tex><br>$;### ${\vartheta}'\; ::: <tex>S_\; \vartheta - {001\vartheta} ' = v^{\beta} \neq -v^\alpha, \; \beta = 0,\dots, 3$ в состоянии $C_1$;## $T_{020u{\alpha}0},</tex><br>$ во всех остальных случаях.# Клетка в состоянии $C_{\varepsilon\varepsilon'}$ перейдет в состояние:## $U$, если среди ее соседей найдется ${\vartheta}'\; :: <tex>S_\; \vartheta - {010\vartheta} ' = v^{{\alpha}'}$ в состоянии $T_{0301{\alpha}'1}$;## $C_{\varepsilon'1}$, если пункт $2.1$ не выполнен,</tex><br>и среди ее соседей найдется клетка ${\vartheta}'\; ::: <tex>S_\; \vartheta - {011\vartheta} ' = v^{{\alpha}'}$ в состоянии $T_{1000{\alpha}'1}$,</tex><br>а все остальные такие клетки не будут находиться в состоянии $T_{0{\alpha}'0}$;::: <tex>S_## $n_{\vartheta}^{100t} = T_C_{110\varepsilon'0}$,</tex><br>иначе.# Клетка в состоянии $U$ перейдет в состояние:## $S_0$, если среди ее соседей найдется ${\vartheta}'\; :: <tex>S_\; \vartheta - {101\vartheta} ' = v^{{\alpha}'}$ в состоянии $T_{120u{\alpha}'1}$;## $U$ во всех остальных случаях.# Клетка в состоянии $S_\Sigma, \; \Sigma=0,\dots,</tex><br>000$ перейдет в состояние:## $S_{\Sigma1}$, если среди ее соседей найдется ${\vartheta}'\; ::: <tex>S_\; \vartheta - {110\vartheta} ' = v^{{\alpha}'}$ в состоянии $T_{130u{\alpha}'1},</tex><br>$;::: <tex>## $S_{111\Sigma0} $, во всех остальных случаях. = C_{00}== Принцип работы ===Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той,в которой начальная конфигурация была задана.Более детальное описание механизма работы автомата можно найти в главе 2 книги "Теория самовоспроизводящихся автоматов"<ref name="neuman_automata"/tex><br>.

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

'''ТьюрмитАвтомат Лэнгтона''' {{---}} это движущаяся по плоскостидвумерный клеточный самовоспроизводящийся автомат, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, ипредставляющий собой сигнальную ленту, заключенную между двумя стенками.<br> В автомате Лэнгтона клетка может находиться в зависимости от него и от цвета одном из восьми возможных состояний. Состояние клеткив следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.<br>Сигнальная лента несет информацию, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправонеобходимую для создания копии автомата.

* [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>