Редактирование: Модели клеточных автоматов

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Клеточный автомат'''<ref>Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title=Список_заданий_по_ДМ_2к_2020_весна</ref> представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии.<br><br>
+
'''Клеточный автомат'''<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>
 
Множество состояний $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>
 
Изначально все ячейки находятся в состоянии $B \in Q$, кроме ячеек с номерами от $1$ до $n$. Ячейка с номером $i$, где $1 \le i \le n$ находится в состоянии $x_i$, где $x$ - входное слово (будем считать, что $\Sigma \subset Q$, $B \notin \Sigma$). <br><br>
Строка 12: Строка 12:
 
|id=moore_neighborhood
 
|id=moore_neighborhood
 
|definition=
 
|definition=
'''Окрестность Мура'''<ref>Окрестность Мура. URL: https://ru.wikipedia.org/wiki/Окрестность_Мура</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой.<br>
+
'''Окрестность Мура'''<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>.
 
Окрестность Мура порядка <tex>r</tex> в двумерном случае представляет собой квадрат со стороной <tex>2r + 1</tex><ref>Weisstein, Eric W. Moore Neighborhood. URL: https://mathworld.wolfram.com/MooreNeighborhood.html</ref>.
 
}}
 
}}
Строка 18: Строка 18:
 
|id=neiman_neighborhood
 
|id=neiman_neighborhood
 
|definition=
 
|definition=
'''Окрестность фон Неймана'''<ref>Окрестность фон Неймана. URL: https://ru.wikipedia.org/wiki/Окрестность_фон_Неймана</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону (грань) с данной ячейкой.
+
'''Окрестность фон Неймана'''<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>.
 
}}
 
}}
  
Строка 25: Строка 39:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Классы Вольфрама'''<ref>Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8</ref> {{---}} классификация клеточных автоматов, основанная на их поведении.
+
'''Классы Вольфрама'''<ref>Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8</ref> {{---}} система классификации клеточных автоматов, основанная на их поведении.
 
}}
 
}}
  
Строка 51: Строка 65:
 
}}
 
}}
 
В соответствии с определением, код может быть вычислен следующим образом:
 
В соответствии с определением, код может быть вычислен следующим образом:
# Определить все возможные конфигурации окрестности данной ячейки;
+
'''Алгоритм вычисления кода Вольфрама:'''
# Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию;
+
1. Определить все возможные конфигурации окрестности данной ячейки;
# Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с правилами переходов на следующей итерации;
+
2. Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию;
# Интерпретируя полученный список состояний как <tex>S</tex>-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама.
+
3. Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с правилами переходов на следующей итерации;
<br>
+
4. Интерпретируя полученный список состояний как <tex>S</tex>-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама.
 
Далее в статье будут приведены наиболее известные правила.<br>
 
Далее в статье будут приведены наиболее известные правила.<br>
 
Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге.
 
Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге.
 +
 +
'''TODO: ADD PICTIRES'''
  
 
=== Правило 30 ===
 
=== Правило 30 ===
Строка 64: Строка 80:
 
'''Правило 30''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).
 
'''Правило 30''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).
 
}}
 
}}
[[Файл:Rule30.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 30]]
 
<br>
 
 
Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние:<br>
 
Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние:<br>
 
{| class="wikitable"  align="center" style="text-align:center"
 
{| class="wikitable"  align="center" style="text-align:center"
Строка 82: Строка 96:
 
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.
 
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.
 
}}
 
}}
[[Файл:Rule90.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 90]]
 
<br>
 
 
Правила перехода для Правила 90:
 
Правила перехода для Правила 90:
 
{| class="wikitable" style="text-align: center"
 
{| class="wikitable" style="text-align: center"
Строка 101: Строка 113:
 
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.
 
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.
 
}}
 
}}
[[Файл:Rule110.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 110]]
 
<br>
 
 
Правила перехода для Правила 110:
 
Правила перехода для Правила 110:
 
{| class="wikitable" style="text-align: center"
 
{| class="wikitable" style="text-align: center"
Строка 113: Строка 123:
 
|}
 
|}
 
Так как <tex>1101110_2 = {110}_{10}</tex>, данное правило называется Правилом 110.
 
Так как <tex>1101110_2 = {110}_{10}</tex>, данное правило называется Правилом 110.
<br>
 
<br>
 
<br>
 
<br>
 
<br>
 
<br>
 
<br>
 
<br>
 
 
  
 
=== Правило 184 ===
 
=== Правило 184 ===
Строка 128: Строка 129:
 
'''Правило 184''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br>
 
'''Правило 184''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br>
 
}}
 
}}
[[Файл:Rule184.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 184]]
 
<br>
 
 
Правила перехода для Правила 184:
 
Правила перехода для Правила 184:
 
{| class="wikitable" style="text-align:center;"
 
{| class="wikitable" style="text-align:center;"
Строка 143: Строка 142:
 
= Клеточные автоматы на двумерной решетке =
 
= Клеточные автоматы на двумерной решетке =
 
== Игра «Жизнь» ==
 
== Игра «Жизнь» ==
Некоторые из приведенных далее определений были взяты с этого<ref>Игра "Жизнь". URL: https://ru.wikipedia.org/wiki/Игра_«Жизнь»</ref> сайта, а также со смежных с нем страниц.
+
Некоторые из приведенных далее определений были взяты с этого<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=
 
|definition=
Строка 169: Строка 168:
 
В данном разделе используются термины из «Словаря Жизни»<ref>«Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm</ref>.
 
В данном разделе используются термины из «Словаря Жизни»<ref>«Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm</ref>.
  
''' TODO: ADD PICTURES'''
+
''' TODO: ADD PICTIRES'''
  
 
==== Устойчивые фигуры ====  
 
==== Устойчивые фигуры ====  
Строка 254: Строка 253:
 
* ДДН {{---}} грабли, вырабатывающий паровозы;
 
* ДДН {{---}} грабли, вырабатывающий паровозы;
 
* ДДД {{---}} грабли, вырабатывающий грабли.
 
* ДДД {{---}} грабли, вырабатывающий грабли.
 +
 +
==== Райский сад ====
 +
[[#edem_theorem | Теорема сада Эдема]] применима к «Жизни»: конфигурация, состоящая из одной «живой клетки» переходит в ту же конфигурацию, что и конфигурация, состоящая только из «мертвых» клеток.
 +
Следовательно, в «Жизни» существуют сады Эдема.
  
 
== Wireworld ==
 
== Wireworld ==
Строка 343: Строка 346:
 
|id=neiman_auto
 
|id=neiman_auto
 
|definition=
 
|definition=
'''Автомат фон Неймана''' (клеточная модель самовоспроизведения<ref name="neuman_automata">Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} объект, представляющий собой поле, в каждой клетке которого находится конечный автомат с 29 состояниями.
+
'''Автомат фон Неймана''' (клеточная модель самовоспроизведения<ref>Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} объект, представляющий собой поле, в каждой клетке которого находится конечный автомат с 29 состояниями.
 
}}
 
}}
  
=== Состояния ===
+
=== Состояния и правила переходов ===
Определим соседей клетки с помощью векторов, установив в координат рассматриваемую клетку:
+
Автомат фон Неймана имеет <tex>N = 29</tex> различных состояний:<br>
* [[#neiman_neighborhood | Окрестность фон Неймана]]: <tex>v^0 = (1, 0) \;\;\; v^1 = (0, 1) \;\;\; v^2 = (-1, 0) \;\;\; v^3 = (0, -1)</tex>;
+
# Транзитивные состояния (импульсы) $T_{u\alpha\varepsilon}$. Определяются:
* Клетки, дополняющие окрестность фон Неймана до [[#moore_neighborhood | окрестности Мура]]: <tex>v^4 = (1, 1) \;\;\; v^5 = (-1, 1) \;\;\; v^6 = (-1, -1) \;\;\; v^7 = (1, -1)</tex><br><br>
+
## Направлением движения.
Состояние клетки $\vartheta$ на $t$-ом шаге: <tex>n_{t}^{\vartheta} = F(n_{t - 1}^\vartheta; n_{t - 1}^{\vartheta + v^\alpha} \; | \; \alpha = 0, \dots , 3), F</tex> {{---}} функция переходов.<br>
+
## Статусом (покой/возбуждение, обычное/специальное);
 +
# Конфлюэнтные состояния <tex>C_{\varepsilon{\varepsilon}'}</tex>. Определяются:
 +
## Статусом (покой/возбуждение);
 +
## Статусом на следующем такте (покой/возбуждение);
 +
# Основное состояние <tex>U</tex> (невозбужденное);
 +
# Чувствительные (сенситивные) состояния <tex>S_{\Sigma}</tex>.
 +
<br>
 +
''' TODO: ADD SCHEME'''
 +
<br>
 +
Переход из $U$ в $S$ осуществляется путем возбуждения, после которого автомат проходит ряд сенситивных состояний, в конечном счете, переходя в состояние $C$ или $T$. Оба конечных состояния могут попеременно находиться в возбужденной и невозбужденной форме, оставаться неизменными или переходить снова в $U$.<br>
 
<br>
 
<br>
Состояния клеток рассматриваемого автомата делятся на $4$ различных класса:<br>
+
Более подробно состояния и правила перехода данного автомата описаны в §5.3 книги "Физика процессов эволюции"<ref name="physics" />.
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}$,  во всех остальных случаях.
 
  
 
=== Принцип работы ===
 
=== Принцип работы ===
 +
''' TODO: ADD PICS'''<br>
 
Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана.
 
Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана.
Более детальное описание механизма работы автомата можно найти в главе 2 книги "Теория самовоспроизводящихся автоматов"<ref name="neuman_automata"/>.
 
  
 
== Автомат Лэнгтона ==
 
== Автомат Лэнгтона ==
Строка 432: Строка 377:
 
|definition=
 
|definition=
 
'''Автомат Лэнгтона''' {{---}} двумерный клеточный самовоспроизводящийся автомат, представляющий собой сигнальную ленту, заключенную между двумя стенками.<br>
 
'''Автомат Лэнгтона''' {{---}} двумерный клеточный самовоспроизводящийся автомат, представляющий собой сигнальную ленту, заключенную между двумя стенками.<br>
 
+
В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.
В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.<br>
 
Сигнальная лента несет информацию, необходимую для создания копии автомата.
 
 
}}
 
}}
 +
Сигнальная лента несет информацию, необходимую для создания копии автомата.<br>
  
 
=== Состояния ===
 
=== Состояния ===
Строка 450: Строка 394:
  
 
=== Принцип работы ===
 
=== Принцип работы ===
<gallery mode="packed" widths=75px heights=200px>
+
''' TODO: ADD PICTURES'''<br>
Image:langton_start.jpg|''Начальная конфигурация''
 
Image:langton_copy.jpg|''Порожденная копия после 151 такта''
 
</gallery>
 
 
 
 
* Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$;
 
* Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$;
 
* Поворот ленты влево достигается путем передачи на ее конец сигнала $40$;
 
* Поворот ленты влево достигается путем передачи на ее конец сигнала $40$;
 
* Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.
 
* Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.
  
= Тьюрмиты =  
+
= Тюрьмиты =  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
 
'''Тьюрмит'''<ref name="mitin" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.
 
'''Тьюрмит'''<ref name="mitin" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.
 
}}
 
}}
[[Файл:Turmite_Langton_ant.png|thumb|300px|right|Результат работы [https://ru.wikipedia.org/wiki/Муравей_Лэнгтона муравья Лэнгтона] после 27731 итераций]]
+
 
 
Каждая строка программы записывается в следующем виде:
 
Каждая строка программы записывается в следующем виде:
 
<pre><текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние></pre>
 
<pre><текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние></pre>
 +
<br>
 +
'''TODO: ADD PICTURES'''
 
<br>
 
<br>
 
[[Игра «Жизнь»]] эмулируется<ref name="mitin" /> с помощью одного тьюрмита: он по очереди обходит все клетки поля и рисует новую конфигурацию в соответствии с правилами игры.<br>
 
[[Игра «Жизнь»]] эмулируется<ref name="mitin" /> с помощью одного тьюрмита: он по очереди обходит все клетки поля и рисует новую конфигурацию в соответствии с правилами игры.<br>
Строка 476: Строка 418:
 
* [[Линейный ограниченный автомат]]
 
* [[Линейный ограниченный автомат]]
 
* [https://ru.wikipedia.org/wiki/Автомат_фон_Неймана Автомат фон Неймана]
 
* [https://ru.wikipedia.org/wiki/Автомат_фон_Неймана Автомат фон Неймана]
* [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>
 
  
 
= Литература =
 
= Литература =

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: