Правило 110 - Rule 110

Правило 110 клеточный автомат (часто называемый просто Правилом 110 ) представляет собой элементарный клеточный автомат с интересным поведением на границе между стабильностью и хаосом. В этом отношении она похожа на «Игру жизни» Конвея . Известно, что правило 110, как и жизнь, завершено по Тьюрингу . Это означает, что в принципе любой расчет или компьютерная программа могут быть смоделированы с помощью этого автомата.

Пример запуска правила 110 клеточного автомата

Определение

В элементарном клеточном автомате одномерный образец нулей и единиц развивается в соответствии с простым набором правил. Будет ли точка в шаблоне иметь значение 0 или 1 в новом поколении, зависит от ее текущего значения, а также от значений двух его соседей.

Анимация того, как правила одномерного клеточного автомата определяют следующее поколение с использованием правила 110.

Автомат Rule 110 имеет следующий набор правил:

Текущий шаблон	111	110	101	100	011	010	001	000
Новое состояние для центральной ячейки	0	1	1	0	1	1	1	0

Название «Правило 110» происходит от того факта, что это правило можно резюмировать в двоичной последовательности 01101110; интерпретируемое как двоичное число , это соответствует десятичному значению 110.

История

В 2004 году Мэтью Кук опубликовал доказательство того, что Правило 110 является полным по Тьюрингу , т. Е. Способным к универсальным вычислениям , которое Стивен Вольфрам предположил в 1985 году. Кук представил свое доказательство на конференции CA98 Института Санта-Фе перед публикацией книги Вольфрама A New Kind of Наука . Это привело к юридическому делу, основанному на соглашении о неразглашении с Wolfram Research . Wolfram Research блокировала публикацию доказательства Кука на несколько лет.

Интересные свойства

Среди 88 возможных уникальных элементарных клеточных автоматов Правило 110 - единственное, для которого была доказана полнота Тьюринга, хотя доказательства нескольких подобных правил должны следовать как простые следствия (например, Правило 124, которое является горизонтальным отражением Правила 110). Правило 110, возможно, является самой простой известной полной системой Тьюринга.

Правило 110, как и « Игра в жизнь» , демонстрирует то, что Вольфрам называет « поведением класса 4 », которое не является ни полностью стабильным, ни полностью хаотичным. Локализованные структуры возникают и взаимодействуют сложным образом.

Мэтью Кук доказал, что правило 110 способно поддерживать универсальные вычисления, последовательно эмулируя циклические системы тегов , затем систему с двумя тегами , а затем машины Тьюринга . Последний этап имеет экспоненциальные накладные расходы по времени, потому что лента машины Тьюринга закодирована в унарной системе счисления . Нири и Вудс (2006) представили другую конструкцию, которая заменяет системы с двумя тегами машинами Тьюринга по часовой стрелке и имеет полиномиальные накладные расходы.

Доказательство универсальности

Мэтью Кук представил свое доказательство универсальности Правила 110 на конференции Института Санта-Фе, состоявшейся перед публикацией книги «Новый вид науки» . Wolfram Research заявила, что эта презентация нарушила соглашение Кука о неразглашении с его работодателем, и получила постановление суда, исключившее статью Кука из опубликованных материалов конференции. Тем не менее стало известно о существовании доказательства Кука. Интерес к его доказательству возник не столько из-за его результата, сколько из-за его методов, особенно из технических деталей его построения. Характер доказательства Кука значительно отличается от обсуждения правила 110 в книге «Новый вид науки» . Кук с тех пор написал статью, в которой изложил свое полное доказательство.

Кук доказал, что правило 110 было универсальным (или полным по Тьюрингу), показав, что это правило можно использовать для имитации другой вычислительной модели, системы циклических тегов , которая, как известно, является универсальной. Сначала он выделил несколько космических кораблей , самовоспроизводящихся локализованных структур, которые можно было построить по бесконечно повторяющемуся образцу во вселенной Правила 110. Затем он разработал способ взаимодействия комбинаций этих структур таким образом, чтобы его можно было использовать для вычислений.

Космические корабли в Правиле 110

Функция универсальной машины в Правиле 110 требует, чтобы конечное число локализованных шаблонов было встроено в бесконечно повторяющийся фоновый узор. Фоновый узор имеет ширину четырнадцать ячеек и повторяется ровно каждые семь итераций. Шаблон 00010011011111 .

Три локализованных шаблона особенно важны в универсальном автомате по Правилу 110. Они показаны на изображении ниже в окружении повторяющегося фонового рисунка. Самая левая структура сдвигается на две ячейки вправо и повторяется каждые три поколения. Он состоит из последовательности 0001110111, окруженной приведенным выше фоновым рисунком, а также двух различных эволюций этой последовательности.

На рисунках время течет сверху вниз: верхняя строка представляет начальное состояние, а каждая следующая строка - состояние в следующий раз.

Центральная структура сдвигается на восемь ячеек влево и повторяется каждые тридцать поколений. Он включает последовательность 1001111, окруженную приведенным выше фоновым рисунком, а также двадцать девять различных эволюций этой последовательности.

Самая правая структура остается неподвижной и повторяется каждые семь поколений. Он включает последовательность 111, окруженную приведенным выше фоновым рисунком, а также пять различных эволюций этой последовательности.

Ниже приведено изображение, на котором показаны первые две структуры, проходящие друг через друга без взаимодействия, кроме как путем перевода (слева), и взаимодействующие друг с другом, чтобы сформировать третью структуру (справа).

В Правиле 110 есть множество других космических кораблей, но они не занимают столь заметного места в доказательстве универсальности.

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

Механизм системы циклических тегов состоит из трех основных компонентов:

Строка данных , которая находится в неподвижном состоянии ;
Бесконечно повторяющийся ряд конечных производственных правил, которые начинаются справа и движутся влево;
Бесконечно повторяющаяся серия тактовых импульсов, которые начинаются слева и движутся вправо.

Первоначальное расстояние между этими компонентами имеет первостепенное значение. Для того, чтобы клеточный автомат реализовал систему циклических тегов, начальные условия автомата должны быть тщательно выбраны так, чтобы различные локализованные структуры, содержащиеся в нем, взаимодействовали высоко упорядоченным образом.

Строка данных в циклической системе тегов представлена рядом стационарных повторяющихся структур типа , показанный выше. Различное количество горизонтальных промежутков между этими структурами позволяет отличить 1 символ от 0 символов. Эти символы представляют слово, на котором работает система циклических тегов, и первый такой символ уничтожается при рассмотрении каждого правила продукции. Когда этот начальный символ равен 1, в конец строки добавляются новые символы; когда он равен 0, новые символы не добавляются. Механизм достижения этого описан ниже.

Вход справа - это ряд движущихся влево структур указанного выше типа, разделенных разным количеством горизонтального пространства. Большое количество этих структур комбинируется с различными интервалами, чтобы представлять нули и единицы в производственных правилах системы циклических тегов. Поскольку правила производства системы тегов известны во время создания программы и бесконечно повторяются, шаблоны нулей и единиц в начальном состоянии могут быть представлены в виде бесконечно повторяющейся строки. Каждое производственное правило отделено от следующего другой структурой, известной как разделитель правил (или разделитель блоков ), которая перемещается влево с той же скоростью, что и кодирование производственных правил.

Когда левый разделитель правил встречает неподвижный символ в строке данных системы циклических тегов, он вызывает уничтожение первого встретившегося символа. Однако его последующее поведение меняется в зависимости от того, был ли символ, закодированный строкой, 0 или 1. Если 0, разделитель правил изменяется на новую структуру, которая блокирует входящее производственное правило. Эта новая структура уничтожается, когда встречается со следующим разделителем правил.

Если, с другой стороны, символ в строке был 1, разделитель правил изменяется на новую структуру, которая допускает входящее производственное правило. Хотя новая структура снова разрушается, когда встречает следующий разделитель правил, она сначала позволяет ряду структур пройти влево. Затем эти структуры добавляются в конец строки данных системы циклических тегов. Это окончательное преобразование выполняется посредством серии бесконечно повторяющихся тактовых импульсов, движущихся вправо, в показанном выше шаблоне движения вправо. Тактовые импульсы преобразуют входящие левосторонние символы 1 из правила производства в стационарные символы 1 строки данных, а входящие символы 0 из правила производства в стационарные символы 0 строки данных.

Система циклических тегов работает

На рисунке выше представлена схематическая диаграмма реконструкции системы циклических тегов в Правиле 110.

Смотрите также

дальнейшее чтение

Кук, Мэтью (2008). «Конкретный взгляд на вычисления по правилу 110». В Нэри, Т .; Woods, D .; Седа, АК; Мерфи, Н. (ред.). Сложность простых программ . Электронные труды по теоретической информатике . 1 . С. 31–55. arXiv : 0906.3248v1 . DOI : 10,4204 / EPTCS.1.4 .
Мартинес, Хенаро Дж .; Адамацки, А .; Чен, Фан Юэ; Чуа, Леон (2012). «О солитонных столкновениях между локализациями в сложных элементарных клеточных автоматах: правила 54 и 110 и далее». Сложные системы . 21 (2): 117–142. arXiv : 1301,6258 . DOI : 10.25088 / ComplexSystems.21.2.117 .
Мартинес, Хенаро Дж .; Адамацки, А .; Стивенс, Кристофер Р .; Хёфлих, Алехандро Ф. (2011). "Суперколлайдеры клеточных автоматов" . Int. J. Mod. Phys. C . 22 (4): 419–439. arXiv : 1105,4332 . Bibcode : 2011IJMPC..22..419M . DOI : 10.1142 / S0129183111016348 .
Мартинес, Хенаро Дж .; Макинтош, Гарольд В .; Мора, Хуан CST; Вергара, Серджио В.К. (2003–2008). «Воспроизведение систем циклических тегов, разработанных Мэтью Куком с Правилом 110 с использованием фаз fi_1» (PDF) . Журнал клеточных автоматов . 6 (2–3): 121–161.
Мартинес, Хенаро Дж .; Макинтош, Гарольд В .; Мора, Хуан CST; Вергара, Серджио ВК (2008). «Определение регулярного языка с помощью структур, основанных на планере, называемых фазами fi_1 в Правиле 110». Журнал клеточных автоматов . 3 (3): 231–270. arXiv : 0706.3348v1 . Bibcode : 2007arXiv0706.3348J .
Мартинес, Хенаро Дж .; Макинтош, Гарольд В .; Мора, Хуан CST; Вергара, Серджио ВК (2007). «Правило 110 объектов и других конструкций на основе коллизий» (PDF) . Журнал клеточных автоматов . 2 (3): 219–242.
Мартинес, Хенаро Дж .; Макинтош, Гарольд В .; Мора, Хуан CST (2006). «Планеры в Правиле 110» (PDF) . Int. J. Нетрадиционных вычислений . 2 : 1–49.
Мартинес, Хенаро Дж .; Макинтош, Гарольд В .; Мора, Хуан CST (2003). «Производство планеров путем столкновений в Правиле 110» (PDF) . Конспект лекций по информатике . 2801 : 175–182. DOI : 10.1007 / 978-3-540-39432-7_19 . ISBN 978-3-540-20057-4.
Мартинес, Хенаро Дж .; Макинтош, Гарольд В. (2001). «ATLAS: Столкновения планеров как фазы эфира в правиле 110» .
Макинтош, Гарольд В. (1999). «Правило 110 в отношении наличия планеров» (PDF) .
Макинтош, Гарольд В. (2002). «Правило 110 универсально!» (PDF) .

Внешние ссылки

[FOOTNOTECook2004-1] а ^б ^в Кук (2004) .

[FOOTNOTEGiles2002-2] Перейти ↑ Giles (2002) .

[3] Перейти ↑ Wolfram 2002 , pp. 169, 675–691

[4] Перейти ↑ Wolfram 2002 , p. 229

[FOOTNOTENearyWoods2006-5] Нири и Вудс (2006) .

[6] Мартинес, Хенаро Дж .; Сек Туох Мора, Хуан; Чапа, Серджио; Леметр, Кристиан (апрель 2019 г.). «Краткие заметки и история вычислений в Мексике за 50 лет» . Международный журнал параллельных, возникающих и распределенных систем . 35 : 1–8. arXiv : 1905.07527 . DOI : 10.1080 / 17445760.2019.1608990 . Проверено 15 апреля 2020 .

Languages

In other projects