Редактирование: Модели клеточных автоматов
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Клеточный автомат'''<ref>Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title= | + | '''Клеточный автомат'''<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>Окрестность Мура. 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>Окрестность фон Неймана. 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. Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию; | |
− | + | 3. Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с правилами переходов на следующей итерации; | |
− | + | 4. Интерпретируя полученный список состояний как <tex>S</tex>-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама. | |
Далее в статье будут приведены наиболее известные правила.<br> | Далее в статье будут приведены наиболее известные правила.<br> | ||
Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге. | Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге. | ||
+ | |||
+ | '''TODO: ADD PICTIRES''' | ||
=== Правило 30 === | === Правило 30 === | ||
Строка 64: | Строка 80: | ||
'''Правило 30''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1). | '''Правило 30''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1). | ||
}} | }} | ||
− | |||
− | |||
Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние:<br> | Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние:<br> | ||
{| class="wikitable" align="center" style="text-align:center" | {| class="wikitable" align="center" style="text-align:center" | ||
Строка 82: | Строка 96: | ||
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей. | Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей. | ||
}} | }} | ||
− | |||
− | |||
Правила перехода для Правила 90: | Правила перехода для Правила 90: | ||
{| class="wikitable" style="text-align: center" | {| class="wikitable" style="text-align: center" | ||
Строка 101: | Строка 113: | ||
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей. | Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей. | ||
}} | }} | ||
− | |||
− | |||
Правила перехода для Правила 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. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=== Правило 184 === | === Правило 184 === | ||
Строка 128: | Строка 129: | ||
'''Правило 184''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br> | '''Правило 184''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<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>Игра "Жизнь". 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 | + | ''' TODO: ADD PICTIRES''' |
==== Устойчивые фигуры ==== | ==== Устойчивые фигуры ==== | ||
Строка 254: | Строка 253: | ||
* ДДН {{---}} грабли, вырабатывающий паровозы; | * ДДН {{---}} грабли, вырабатывающий паровозы; | ||
* ДДД {{---}} грабли, вырабатывающий грабли. | * ДДД {{---}} грабли, вырабатывающий грабли. | ||
+ | |||
+ | ==== Райский сад ==== | ||
+ | [[#edem_theorem | Теорема сада Эдема]] применима к «Жизни»: конфигурация, состоящая из одной «живой клетки» переходит в ту же конфигурацию, что и конфигурация, состоящая только из «мертвых» клеток. | ||
+ | Следовательно, в «Жизни» существуют сады Эдема. | ||
== Wireworld == | == Wireworld == | ||
Строка 343: | Строка 346: | ||
|id=neiman_auto | |id=neiman_auto | ||
|definition= | |definition= | ||
− | '''Автомат фон Неймана''' (клеточная модель самовоспроизведения<ref | + | '''Автомат фон Неймана''' (клеточная модель самовоспроизведения<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> | <br> | ||
− | + | Более подробно состояния и правила перехода данного автомата описаны в §5.3 книги "Физика процессов эволюции"<ref name="physics" />. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=== Принцип работы === | === Принцип работы === | ||
+ | ''' TODO: ADD PICS'''<br> | ||
Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана. | Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана. | ||
− | |||
== Автомат Лэнгтона == | == Автомат Лэнгтона == | ||
Строка 432: | Строка 377: | ||
|definition= | |definition= | ||
'''Автомат Лэнгтона''' {{---}} двумерный клеточный самовоспроизводящийся автомат, представляющий собой сигнальную ленту, заключенную между двумя стенками.<br> | '''Автомат Лэнгтона''' {{---}} двумерный клеточный самовоспроизводящийся автомат, представляющий собой сигнальную ленту, заключенную между двумя стенками.<br> | ||
− | + | В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей. | |
− | В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей | ||
− | |||
}} | }} | ||
+ | Сигнальная лента несет информацию, необходимую для создания копии автомата.<br> | ||
=== Состояния === | === Состояния === | ||
Строка 450: | Строка 394: | ||
=== Принцип работы === | === Принцип работы === | ||
− | + | ''' TODO: ADD PICTURES'''<br> | |
− | |||
− | |||
− | < | ||
− | |||
* Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$; | * Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$; | ||
* Поворот ленты влево достигается путем передачи на ее конец сигнала $40$; | * Поворот ленты влево достигается путем передачи на ее конец сигнала $40$; | ||
* Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата. | * Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата. | ||
− | = | + | = Тюрьмиты = |
{{Определение | {{Определение | ||
|definition= | |definition= | ||
'''Тьюрмит'''<ref name="mitin" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо. | '''Тьюрмит'''<ref name="mitin" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо. | ||
}} | }} | ||
− | + | ||
Каждая строка программы записывается в следующем виде: | Каждая строка программы записывается в следующем виде: | ||
<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 Муравей Лэнгтона] |
− | |||
= Литература = | = Литература = |