1632
правки
Изменения
м
Определение и основные свойства клеточного автомата содержатся в статье [[Линейный клеточный автомат, эквивалентность МТ]].
= Базовые определения =
== Основные элементы ==
В данном разделе используются термины из «Словаря Жизни»<ref>«Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm</ref>.
В зависимости от начального состояния поля, клетки могут образовывать фигуры, обладающие различными свойствами. По этим свойствам принято делить фигуры на следующие классы:=== Правило 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остояние|-| «Живая клетка»| Белый| «мертвая клетка», если имеет ровно меньше двух или больше трех соседей в состоянии «живая клетка».|-| «Мертвая клетка»| Черный| «живая клетка», если имеет ровно трех соседей в статьесостоянии «живая клетка».|}
''' TODO=== Основные элементы ===В данном разделе используются термины из «Словаря Жизни»<ref>«Словарь Жизни». URL: ADD PICTIRES'''http://beluch.ru/life/lifelex/lexr_o.htm</ref>.
=== Устойчивые фигуры === Устойчивые фигуры или «натюрморты», делятся на несколько классов<ref>Eric Weisstein. Still Life</ref>''' TODO:* Устойчивый образец {{---}} объект, который является собственным родителем;* Натюрморт {{---}} устойчивый объект, являющийся конечным и непустым, из которого нельзя выделить непустую устойчивую часть;* Псевдонатюрморт {{---}} устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортов.ADD PICTURES'''
У ружья есть два периода: '''период создания космических кораблей''' и '''период повторения состояний ружья'''.
Паровозы условно делят на чистые и грязные:* Чистый паровоз оставляет след, обладающей легко уловимой на глаз периодичностью;* Грязный — сложный, хаотически выглядящий след. ==== Пожиратели ====
Размножители классифицируютсяСуществует несколько видов<ref>Breeder – from Eric Weisstein's Treasure Trove of Life</ref> по размножителей, отличающихся между собой относительной подвижности подвижностью полученных конфигураций. Типы обозначаются кодами из трёх Виды кодируются при сочетаниями трех букв, которые обозначаютописывающие, являются ли первичнаясоответственно, вторичная первичную, вторичную и третичная третичную конфигурации соответственно движущимися (: Д) или неподвижными ({{---}} движущаяся, Н).{{---}} неподвижная:<br>Четыре основных типа:
Теорема применима к «Жизни», поскольку легко найти две различные конфигурации, которые эволюционируют в следующем поколении в одну и ту же конфигурацию.==== Диод ====«Мёртвая вселенная» и одинокая живая клетка в «мёртвой вселенной» эволюционируют в одну и ту Данный элемент действует точно так же конфигурацию, все клетки которой мёртвыекак одноименный элемент<ref>Диод. URL: https://ru.wikipedia.org/wiki/Диод</ref> электрической цепи.Следовательно, в «Жизни» существуют сады Эдема<br><gallery mode="packed-hover">Image:Diode_wireworld.jpg|100px|300px|''Диод''</gallery>
Клеточный автомат '''WireworldАвтомат фон Неймана'''(клеточная модель самовоспроизведения<refname="neuman_automata">Трофимов ДНейман Дж., Наумов Лфон. Теория самовоспроизводящихся автоматов. Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизация, 2007М. URL: http://is.ifmo.ru/works/wireworld/Мир, 1971</ref> представляет ) {{---}} объект, представляющий собой синхронный поле, в каждой клетке которого находится конечный автомат с двумерной решеткой из квадратов, каждая клетка которой может находиться в одном из четырех состояний29 состояниями.
== Основные элементы ==Большие коллекции функциональных элементов имеются в пакетах Mirek's CellebrationТакже интерес представляет Муравей Лэнгтона<ref>Langton, Chris G. (1986). "Mirek's CellebrationStudying artificial life with cellular automata". URL:http://mirekw.com/ca/index.html, 120–149</ref> , разработанный в 1986 году Крисом Лэнгтоном и Zillions of Gamesявляющимся, по сути, двумерной машиной Тьюринга с 2 символами и 4 состояниями<ref>"Zillions of Games"Mária Bieliková, Gerhard Friedrich, Georg Gottlob. URLSOFSEM 2012:httpTheory and Practice of Computer Science://zillionsofgames38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012, Proceedings.com</ref>— Springer, а также на сайте WireWorld<ref>"WireWorld"2012. URL:http://karl— P.kiwi394.gen.nz/CA— ISBN 978-3-642-27660-Wireworld.html6. </ref>. Кроме того{{Определение|definition='''Автомат Лэнгтона''' {{---}} двумерный клеточный самовоспроизводящийся автомат, представляющий собой сигнальную ленту, на сайте The Wireworld computerзаключенную между двумя стенками.<refbr>"The Wireworld computer" В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. URL:http://wwwСостояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.quinapalus.com/wi-index.html</refbr> приводится пример построения в WireWorld компьютера с определенным набором инструкций и регистровСигнальная лента несет информацию, и реализация алгоритма перечисления простых чисел необходимую для этого компьютерасоздания копии автомата.}}
=== Двоичный сумматор ===Рассмотрим пример более сложной структуры, состоящей из множества простых элементов – двоичный сумматор. Его функция заключается в том, что при подаче * Увеличение длины ленты на два входа закодированных особым образом чисел, через фиксированное количество шагов (в изображенном примере – 48) $1$ достигается путем передачи на выходе появится закодированное таким же образом число – сумма чисел на входах. Числа кодируются в двоичном виде, от младших битов к старшим, каждый бит кодируется наличием или отсутствием электрона ее конец сигнала $70$;* Поворот ленты влево достигается путем передачи на определенной позиции. Наее конец сигнала $40$;рисунке ниже эти позиции отмечены точками и изображениями чисел (значений каждого бита) из клеток в состоянии «проводник» по краям входов и выхода. Сами по себе эти отметки не несут никакой функциональной нагрузки, а служат лишь в пояснительных целях. Изображенный ниже сумматор имеет разрядность входов три бита, но можно получить сумматор с любой разрядностью, удлинив или укоротив провода на входах и выходе* Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.
rollbackEdits.php mass rollback
= Базовые определения ={{В разработкеОпределение|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$. }}Определение и основные свойства линейного клеточного автомата содержатся в статье [[Линейный клеточный автомат, эквивалентность МТ | "линейный клеточный автомат, эквивалентность МТ"]].
{{Определение
|id=moore_neighborhood
|definition=
'''Окрестность Мура''' <ref>Окрестность Мура. URL: https://ru.wikipedia.org/wiki/Окрестность_Мура</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой.<br>
Окрестность Мура порядка <tex>r</tex> в двумерном случае представляет собой квадрат со стороной <tex>2r + 1</tex><ref>Weisstein, Eric W. Moore Neighborhood. URL: https://mathworld.wolfram.com/MooreNeighborhood.html</ref>.
}}
{{Определение
|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 ==={{Определение
|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 её двух соседей в [[#moore_neighborhood | окрестности Мура]].
}}
[[Файл: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>
<br>
==== Устойчивые фигуры ==== {{Определение|definition='''Устойчивый образец''' {{---}} объект, который является собственным родителем.}}{{Определение|definition='''Натюрморт'''<ref>Eric Weisstein. Still Life</ref> {{---}} устойчивый объект, являющийся конечным и непустым, из которого нельзя выделить непустую устойчивую часть.}}{{Определение|definition='''Псевдонатюрморт''' {{---}} устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортов.}} ==== Долгожители ====
{{Определение
|definition=
}}
==== Осцилляторы ====
{{Определение
|definition=
}}
==== Двигающиеся фигуры ====
{{Определение
|definition=
}}
==== Ружья ====
{{Определение
|definition=
'''Ружье''' {{---}} класс конфигураций, у которых основная часть циклически повторяется, как у осцилляторов, а также периодически создаёт космические корабли, которые удаляются от ружья. Данная конфигурация имеет два периода: '''период создания космических кораблей''' и '''период повторения состояний ружья'''.
}}
==== Паровозы ====
{{Определение
|definition=
{{Определение
|definition=
'''Грабли''' {{---}} паровозы, оставляющие за собой след исключительно из космических кораблей.<br>
}}
{{Определение
|definition=
}}
==== Отражатели ====
{{Определение
|definition=
}}
==== Размножители ====
{{Определение
|definition=
}}
* НДД {{---}} ружьё, вырабатывающее грабли;
* ДНД {{---}} паровоз, оставляющий вырабатывающий ружья на своем пути;* ДДН {{---}} грабли, оставляющие вырабатывающий паровозы;* ДДД {{---}} Граблиграбли, оставляющие вырабатывающий грабли, так что нет никаких неподвижных элементов.
=== Дублирующиеся фигуры === === Райский сад =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>представляет собой синхронный автомат с двумерной решеткой из квадратов, каждая клетка которой может находиться в одном из четырех состояний.
}}
=== Состояния и правила переходов ===
{| class="wikitable"
|-
! scope="col"| Название состояния
! scope="col"| Цвет
! scope="col"| Переходит в состояние
|-
| Пустая клетка
| Черный
|
|-
| Проводник
| Желтый
| «голова электрона», если имеет ровно одного или двух [[#moore_neighborhood | соседей]] в состоянии «голова электрона»
|-
| Голова электрона
| Красный
| «хвост электрона»
|-
| Хвост электрона
| Синий
| «проводник»
|}
=== Общие закономерности ===
Движение "электрона" в "цепи" происходит со следующими закономерностями:
* При прохождении электроном разветвления "цепи", в каждое из новых направлений уходит по "электрону";
* При одновременном столкновении трёх и более "электронов", они исчезают.
* При толщине "провода" больше $2$, "электроны" начинают двигаться хаотично.
=== Основные элементы ===
В данной статье приведены лишь основные простейшие элементы, которые можно составить в Wireworld.<br>
Большое количество примеров приведено в Mirek's Cellebration<ref>"Mirek's Cellebration". URL:http://mirekw.com/ca/index.html</ref> и Zillions of Games<ref>"Zillions of Games". URL:http://zillionsofgames.com</ref>, WireWorld<ref>"WireWorld". URL:http://karl.kiwi.gen.nz/CA-Wireworld.html. </ref>; с помощью элементов Wireworld также был построен<ref>"The Wireworld computer". URL:http://www.quinapalus.com/wi-index.html</ref> компьютер.
==== Тактовый генератор ====
Данный элемент используется для получения электронов, так как при каждом прохождении разветвления электроном, движущимся по петле генератора, образуется новый электрон. Частота появления электронов регулируется длиной петли.
<br>
<gallery mode="packed-hover">
Image:Tact_generator_wireworld.jpg|100px|300px|''Тактовый генератор''
</gallery>
= Автомат фон Неймана === Логические элементы OR, XOR и NAND ====Данный элемент действует точно так же, как и одноименные логические элементы<ref>Дизъюнкция. URL: https://ru.wikipedia.org/wiki/Дизъюнкция</ref><ref>Исключающее «или». URL: https://ru.wikipedia.org/wiki/Исключающее_«или»</ref><ref>NAND (логический элемент). URL: https://ru.wikipedia.org/wiki/Штрих_Шеффера</ref>.<br>
<gallery mode= Коды Вольфрама "packed" widths=75px heights=200px>Image:OR_wireworld.jpg|''OR''Image:XOR_wireworld.jpg|''XOR''Image:NAND_wireworld.jpg|''NAND''</gallery>
= Wireworld Самовоспроизводящиеся клеточные автоматы =В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов, которые подробно описаны в книге "Физика процессов эволюции"<ref name="physics">Эбелинг Вернер, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.: Эдиториал УРСС, 2001. - 328 с.</ref>:<br>«# Логическая универсальность.## При каких условиях определенный класс автоматов логически универсален?## Существует ли логически универсальный автомат?# Конструируемость.## Может ли один автомат быть построен другим автоматом?## Какой класс автоматов может быть построен каким-то автоматом?# Конструктивная универсальность.## Существует ли конструктивно универсальный автомат? (т. е. автомат, способный построить любой автомат)# Самовоспроизведение.## Существует ли самовоспроизводящийся автомат?## Существует ли автомат, который, помимо самовоспроизведения, может решать и другие задачи?# Эволюция.## Может ли при конструировании автомата автоматом происходить усложнение типа автомата?## Может ли такая эволюция происходить в направлении от менее эффективного к более эффективному автомату? (при надлежащем определении понятия эффективности):::::::::::::::::::::::::::::::::::::::::::::::::::::::». В то время, как Тьюринг доказал, что [[Машина Тьюринга|машина Тьюринга]] является логически универсальной, Дж. фон Нейман построил автомат<ref name="mitin">Г. Г. Малинецкий, Н. А. Митин, С. А. Науменко, “Нанобиология и синергетика. Проблемы и идеи (Часть 2)”, Препринты ИПМ им. М. В. Келдыша, 2005, 081. URL: http://spkurdyumov.ru/uploads/2013/09/miittin.pdf</ref>, удовлетворяющий всем пяти свойствам. Одна из таких моделей будет описана далее. == Автомат фон Неймана ==
{{Определение
|id=neiman_auto
|definition=
}}
=== Состояния ===Определим соседей клетки с помощью векторов, установив в координат рассматриваемую клетку:* [[Файл#neiman_neighborhood | Окрестность фон Неймана]]:Wireworld_states_meaning_table.jpg<tex>v^0 = (1, 0) \;\;\; v^1 = (0, 1) \;\;\; v^2 = (-1, 0) \;\;\; v^3 = (0, -1)</tex>;* Клетки, дополняющие окрестность фон Неймана до [[#moore_neighborhood |500px|700px|thumb|centerокрестности Мура]]: <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><br>Состояния клеток рассматриваемого автомата Wireworld]]делятся на $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}$.<br><br>Далее объясним природу вышеперечисленных состояний. Для достижения поставленных целей, Дж. фон Нейман проводит<ref name="neuman_automata"/> аналогию с системой нейронных связей, аналогичным образом строя автомат.<br><br>Для передачи информации между клетками по цепочке из клеток же вводятся состояния $T$, причем наличие нейронного импульса регулируется параметром $\varepsilon$. Так как передача должна быть направленным процессом, вводится параметр $\alpha$, обозначающий, с какого направления клетка в данном состоянии будет принимать импульс.<br><br>Работу самих нейронов представляют состояния $С$: каждый нейрон имеет один "выход" и два "входа" (стороны клетки), которые для возбуждения необходимо раздражать одновременно, то есть у "нейрона" должно быть не менее двух соседей в окрестности фон Неймана в состоянии $T_1$, выходные направления которых ориентированы на "нейрон". Для экономии количества состояний вводится условность, что каждая сторона клетки может быть как "входом", так и "выходом" нейрона.<br><br>По аналогии с нейронными сетями, автомат должен иметь возможность "расщеплять" передаваемый сигнал, т.е. обеспечить возможность передачи его нескольким клеткам сразу. Данную функцию выполняют конфлюэнтные состояния, по определению имея несколько "выходов" и один "вход".<br><br>Состояния $S_{\Sigma0}$ и $S_{\Sigma1}$ используются для совершения прямого (возбуждение невозбужденных клеток) и обратного (приведение к покою возбужденных клеток) процессов.
=== Правила переходов ===Функция переходов $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$ в состоянии $C_1$;## $T_{u{\alpha}0}$ во всех остальных случаях. # Клеткав состоянии $C_{\varepsilon\varepsilon'}$ перейдет в состояние:## $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$ перейдет в состояние «проводник»:## $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}$;## $S_{\Sigma0}$, во всех остальных случаях «проводник» остается «проводником».<br>При применении данных правил используется [[#moore_neighborhood | окрестность Мура]] – считается=== Принцип работы ===Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что с даннойчерез некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана.клеткой соседствуют все восемь ее непосредственных соседейБолее детальное описание механизма работы автомата можно найти в главе 2 книги "Теория самовоспроизводящихся автоматов"<ref name="neuman_automata"/>.
== Общие закономерности Автомат Лэнгтона ==Электрон передвигается со скоростью одна клетка за шаг. Если по проводу навстречу идут два электрона, при столкновении они исчезают. При достижении электроном разветвления проводов по каждому из направлений, кроме исходного, уходит по электрону. Если к разветвлению одновременно подходит <tex>2Примером более простого самовоспроизводящегося клеточного автомата является автомат Лэнгтона<ref name="mitin" /tex> и более электронов, все они исчезают. При толщине провода в <tex>2</texbr> клетки поведение электронов аналогично обычному, при большей толщине поведение становится хаотичным.
=== Тактовый генератор Состояния ===Данный элемент представляет собой «петлю» из клеток проводника, ==== Сигнальные состояния ====Состояния $3-7$ относят к которой подсоединен провод – выход генератора, классу сигнальных:* $3$ используется при повороте;* $5$ и изначально содержит один электрон. С периодом, равным длине петли, этот электрон достигает точки соединения петли с выходом, и дальше разветвляется на два электрона, один из которых идет по выходу, второй – дальше по петле. Таким образом, этот элемент можно использовать $6$ используются для получения в проводе бесконечного количества электронов, следующих один за другим на расстоянии, регулируемом длиной петли.<br>[[Файл:Tact_generator_wireworldсамовоспроизведения.jpg|100px|300px|thumb|center|Тактовый генератор]]
=== Диод = Служебные состояния ====Этот функциональный элемент имеет две точки подсоединения Состояния $0-2$ относят к проводам – вход и выход, и его действие состоит в томклассу служебных:* $0$, что электроны, пришедшие на вход, передаются на выход, а электроны, пришедшие на выход – исчезают. Таким образом, электроны могут перемещаться по проводу, в который включен диод, лишь в одном направлении.идущее вслед за сигнальным задает направление распространения сигнала;<br>* $1$ является «несущей лентой» сигнала;[[Файл:Diode_wireworld* Из клеток в состоянии $2$ строятся «стенки» автомата.jpg|100px|300px|thumb|center|Диод]]
=== Логические элементы OR, XOR и NAND Принцип работы ===Каждый из этих элементов имеет по 2 входа и выход. Наличие электрона на входе соответствует логическому значению «единица», отсутствие – логическому значению «ноль». Электрон на выходе появляется согласно таблице истинности соответствующей логической операции.<brgallery mode="packed" widths=75px heights=200px>* Так, для элемента Image:langton_start.jpg|''Начальная конфигурация'OR''' электрон на любом из входов, или электроны на обоих входах одновременно дают электрон на выходеImage:langton_copy.<br>* Для элемента jpg|''Порожденная копия после 151 такта'XOR''' электрон на любом из входов дает электрон на выходе, но при одновременной подаче электронов на оба входа они исчезают, и электрон на выходе не создается.<br>* Элемент '''NAND''' работает как тактовый генератор, и посылает электроны на выход во всех случаях, за исключением случая, когда на оба входа одновременно подаются электроны.<br/gallery>'''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]]
= Тьюрмиты = {{Определение|definition='''Тьюрмит'''<ref name="mitin" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.}}[[FileФайл:Binary_summator_wireworldTurmite_Langton_ant.jpgpng|200pxthumb|350px300px|centerright|thumb|Двоичный сумматорРезультат работы [https://ru.wikipedia.org/wiki/Муравей_Лэнгтона муравья Лэнгтона] после 27731 итераций]]Каждая строка программы записывается в следующем виде:<pre><текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние></pre><br>[[Игра «Жизнь»]]эмулируется<ref name="mitin" /> с помощью одного тьюрмита: он по очереди обходит все клетки поля и рисует новую конфигурацию в соответствии с правилами игры.<br>В области исследований модели ДНК при моделировании активно используются взаимодействующие и плиточные тьюрмиты<ref name="mitin" /> .
= См.также =
* [[Линейный ограниченный автомат]]
* [https://ru.wikipedia.org/wiki/Автомат_фон_Неймана Автомат фон Неймана]
* [https://ru.wikipedia.org/wiki/%D0%9C%D1%83%D1%80%D0%B0%D0%B2%D0%B5%D0%B9_%D0%9B%D1%8D%D0%BD%D0%B3%D1%82%D0%BE%D0%BD%D0%B0 Муравей_Лэнгтона Муравей Лэнгтона]* Лобанов А.И. Модели клеточных автоматов<ref>Лобанов А.И. Модели клеточных автоматов // Компьютерные исследования и моделирование, 2010, т. 2, № 3, с. 273-293. URL: http://vst.ics.org.ru/uploads/crmissues/kim_2010_2_3/crm10304.pdf</ref>
= Литература =
