Просмотр исходного текста страницы Модели клеточных автоматов

= Базовые определения =
{{Определение
|definition=
'''Клеточный автомат'''<ref>Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B9_%D0%BF%D0%BE_%D0%94%D0%9C_2%D0%BA_2020_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0</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/%D0%9E%D0%BA%D1%80%D0%B5%D1%81%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%9C%D1%83%D1%80%D0%B0</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой.<br>
Окрестность Мура порядка <tex>r</tex> в двумерном случае представляет собой квадрат со стороной <tex>2r + 1</tex><ref>Weisstein, Eric W. Moore Neighborhood. URL: https://mathworld.wolfram.com/MooreNeighborhood.html</ref>.
}}
{{Определение
|id=neiman_neighborhood
|definition=
'''Окрестность фон Неймана'''<ref>Окрестность фон Неймана. URL: https://ru.wikipedia.org/wiki/%D0%9E%D0%BA%D1%80%D0%B5%D1%81%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D1%84%D0%BE%D0%BD_%D0%9D%D0%B5%D0%B9%D0%BC%D0%B0%D0%BD%D0%B0</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону (грань) с данной ячейкой.
}}

{{Определение
|id=edem_def
|definition=
'''Райский сад'''<ref name="edem">Сад Эдема (конфигурация клеточного автомата). URL: https://ru.wikipedia.org/wiki/%D0%A1%D0%B0%D0%B4_%D0%AD%D0%B4%D0%B5%D0%BC%D0%B0_(%D0%BA%D0%BE%D0%BD%D1%84%D0%B8%D0%B3%D1%83%D1%80%D0%B0%D1%86%D0%B8%D1%8F_%D0%BA%D0%BB%D0%B5%D1%82%D0%BE%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0)</ref> {{---}} конфигурация КА, которая не может появиться в результате «эволюции», потому что не имеет предшественников.
}}
{{Теорема
|id=edem_theorem
|about=сада Эдема
|statement=
Клеточный автомат в евклидовой вселенной является локально инъективным тогда и только тогда, когда он сюръективен.
Другими словами, теорема утверждает, что сады Эдема существуют только в тех автоматах, в которых существуют близнецы.
Данная теорема была выдвинута и доказана Эдвардом Муром<ref>Moore, E. F. (1962), Machine models of self-reproduction, Proc. Symp. Applied Mathematics Т. 14: 17–33</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> {{---}} радиус окрестности.
}}
В соответствии с определением, код может быть вычислен следующим образом:
 '''Алгоритм вычисления кода Вольфрама:'''
 1. Определить все возможные конфигурации окрестности данной ячейки;
 2. Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию;
 3. Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с правилами переходов на следующей итерации;
 4. Интерпретируя полученный список состояний как <tex>S</tex>-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама.
Далее в статье будут приведены наиболее известные правила.<br>
Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге.

'''TODO: ADD PICTIRES'''

=== Правило 30 ===
{{Определение
|definition=
'''Правило 30''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).
}}
Для Правила 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 её двух соседей.
}}
Правила перехода для Правила 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 её двух соседей.
}}
Правила перехода для Правила 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.

=== Правило 184 ===
{{Определение
|definition=
'''Правило 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
|}
Так как <tex>110111000_2 = {184}_{10}</tex>, данное правило называется Правилом 184.

= Клеточные автоматы на двумерной решетке =
== Игра «Жизнь» ==
Некоторые из приведенных далее определений были взяты с этого<ref>Игра "Жизнь". URL: https://ru.wikipedia.org/wiki/%D0%98%D0%B3%D1%80%D0%B0_%C2%AB%D0%96%D0%B8%D0%B7%D0%BD%D1%8C%C2%BB</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 PICTIRES'''

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

==== Долгожители ====
{{Определение
|definition=
'''Долгожитель''' {{---}} конфигурация из 10 или меньшего числа клеток, которым необходимо не менее 50 поколений для стабилизации<ref>Gardner, M. (1983). "The Game of Life, Part III". Wheels, Life and Other Mathematical Amusements: 246</ref>.
}}
 
==== Осцилляторы ==== 
{{Определение
|definition=
'''Осциллятор''' {{---}} конфигурация клеточного автомата, которая после конечного числа поколений повторяется в изначальном виде и положении.
}}
{{Определение
|definition=
'''Период осциллятора''' {{---}} минимальное число поколений, через которое осциллятор возвращается в исходное состояние.
}} 

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

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

==== Паровозы ==== 
{{Определение
|definition=
'''Паровоз''' {{---}} объект, который движется по полю подобно космическому кораблю, но при этом ещё и оставляет за собой след из других объектов.
}}
{{Определение
|definition=
'''Грабли''' {{---}} паровозы, оставляющие за собой след исключительно из космических кораблей.<br>
}}

==== Пожиратели ==== 
{{Определение
|definition=
'''Пожиратель''' {{---}} конфигурация, способная уничтожить космический корабль и восстановиться после контакта.
}}

==== Отражатели ==== 
{{Определение
|definition=
'''Отражатель''' {{---}} натюрморт или периодическая конфигурация, способная изменить направление движения другой фигуры определенного типа на 90° или 180°, восстанавливая свою структуру после отражения.
}}
{{Определение
|definition=
'''Время восстановления''' отражателя {{---}} минимальное число поколений, которое должно проходить между столкновением с другими фигурами, чтобы отражатель успевал восстановиться.
}}

==== Размножители ==== 
{{Определение
|definition=
'''Размножитель''' {{---}} конфигурация, растущая квадратично, производя множество копий вторичной конфигурации, каждая из которых производит множество копий третичной конфигурации.
}}

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

==== Райский сад ====
[[#edem_theorem | Теорема сада Эдема]] применима к «Жизни»: конфигурация, состоящая из одной «живой клетки» переходит в ту же конфигурацию, что и конфигурация, состоящая только из «мертвых» клеток.
Следовательно, в «Жизни» существуют сады Эдема.

== Wireworld ==
{{Определение
|definition=
Клеточный автомат '''Wireworld'''<ref>Трофимов Д., Наумов Л. Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизация, 2007. URL: http://is.ifmo.ru/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>

==== Диод ====
Данный элемент действует точно так же, как одноименный элемент<ref>Диод. URL: https://ru.wikipedia.org/wiki/Диод</ref> электрической цепи.
<br>
<gallery mode="packed-hover">
Image:Diode_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>

= Самовоспроизводящиеся клеточные автоматы =
В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов, которые подробно описаны в книге "Физика процессов эволюции"<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=
'''Автомат фон Неймана''' (клеточная модель самовоспроизведения<ref>Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} объект, представляющий собой поле, в каждой клетке которого находится конечный автомат с 29 состояниями.
}}

=== Состояния и правила переходов ===
Автомат фон Неймана имеет <tex>N = 29</tex> различных состояний:<br>
# Транзитивные состояния (импульсы) $T_{u\alpha\varepsilon}$. Определяются:
## Направлением движения.
## Статусом (покой/возбуждение, обычное/специальное);
# Конфлюэнтные состояния <tex>C_{\varepsilon{\varepsilon}'}</tex>. Определяются:
## Статусом (покой/возбуждение);
## Статусом на следующем такте (покой/возбуждение);
# Основное состояние <tex>U</tex> (невозбужденное);
# Чувствительные (сенситивные) состояния <tex>S_{\Sigma}</tex>.
<br>
''' TODO: ADD SCHEME'''
<br>
Переход из $U$ в $S$ осуществляется путем возбуждения, после которого автомат проходит ряд сенситивных состояний, в конечном счете, переходя в состояние $C$ или $T$. Оба конечных состояния могут попеременно находиться в возбужденной и невозбужденной форме, оставаться неизменными или переходить снова в $U$.<br>
<br>
Более подробно состояния и правила перехода данного автомата описаны в §5.3 книги "Физика процессов эволюции"<ref name="physics" />.

=== Принцип работы ===
''' TODO: ADD PICS'''<br>
Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана.

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

Также интерес представляет Муравей Лэнгтона<ref>Langton, Chris G. (1986). "Studying artificial life with cellular automata", 120–149</ref>, разработанный в 1986 году Крисом Лэнгтоном и являющимся, по сути, двумерной машиной Тьюринга с 2 символами и 4 состояниями<ref>Mária Bieliková, Gerhard Friedrich, Georg Gottlob. SOFSEM 2012: Theory and Practice of Computer Science: 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012, Proceedings. — Springer, 2012. — P. 394. — ISBN 978-3-642-27660-6.</ref>.
{{Определение
|definition=
'''Автомат Лэнгтона''' {{---}} двумерный клеточный самовоспроизводящийся автомат, представляющий собой сигнальную ленту, заключенную между двумя стенками.<br>
В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.
}}
Сигнальная лента несет информацию, необходимую для создания копии автомата.<br>

=== Состояния ===
==== Сигнальные состояния ====
Состояния $3-7$ относят к классу сигнальных:
* $3$ используется при повороте;
* $5$ и $6$ используются для самовоспроизведения. 

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

=== Принцип работы ===
''' TODO: ADD PICTURES'''<br>
* Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$;
* Поворот ленты влево достигается путем передачи на ее конец сигнала $40$;
* Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.

= Тюрьмиты = 
{{Определение
|definition=
'''Тьюрмит'''<ref name="mitin" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.
}}

Каждая строка программы записывается в следующем виде:
<pre><текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние></pre>
<br>
'''TODO: ADD PICTURES'''
<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 Муравей Лэнгтона]

= Литература =

[[Категория: Дискретная математика]]
[[Категория: Теория вычислимости]]
[[Категория: Вычислительные формализмы]]