Клеточный автомат Правила 110 (часто называемый просто Правилом 110 ) [a] — это элементарный клеточный автомат с интересным поведением на границе между стабильностью и хаосом. В этом отношении он похож на Игру Конвея «Жизнь» . Как и Жизнь, Правило 110 с определенным повторяющимся фоновым узором известно как полное по Тьюрингу . [2] Это означает, что, в принципе, любое вычисление или компьютерная программа могут быть смоделированы с использованием этого автомата.
В элементарном клеточном автомате одномерный шаблон из нулей и единиц развивается в соответствии с простым набором правил. Будет ли точка в шаблоне 0 или 1 в новом поколении, зависит от ее текущего значения, а также от значений ее двух соседей.
Автомат Правила 110 имеет следующий набор правил:
Название «Правило 110» происходит от того факта, что это правило можно обобщить в двоичной последовательности 01101110; интерпретируемое как двоичное число , это соответствует десятичному значению 110. Это схема именования кодов Wolfram .
В 2004 году Мэтью Кук опубликовал доказательство того, что Правило 110 с определенным повторяющимся фоновым рисунком является полным по Тьюрингу , т. е. способным к универсальному вычислению , что Стивен Вольфрам предположил в 1985 году. [2] Кук представил свое доказательство на конференции Института Санта-Фе CA98 перед публикацией книги Вольфрама «Новый вид науки» . Это привело к юридическому разбирательству, основанному на соглашении о неразглашении с Wolfram Research . [3] Wolfram Research блокировал публикацию доказательства Кука в течение нескольких лет. [4]
Среди 88 возможных уникальных элементарных клеточных автоматов , Правило 110 является единственным, для которого полнота по Тьюрингу была доказана напрямую, хотя доказательства для нескольких похожих правил следуют как простые следствия (например, Правило 124, которое является горизонтальным отражением Правила 110). Правило 110, возможно, является самой простой известной полной по Тьюрингу системой. [2] [5]
Правило 110, как и Игра Жизни , демонстрирует то, что Вольфрам называет « поведением класса 4 », которое не является ни полностью стабильным, ни полностью хаотичным. Локализованные структуры появляются и взаимодействуют сложным образом. [6]
Мэтью Кук доказал, что Правило 110 способно поддерживать универсальные вычисления, последовательно эмулируя циклические системы тегов , затем 2- теговую систему , а затем машины Тьюринга . Заключительный этап имеет экспоненциальные временные затраты, поскольку лента машины Тьюринга закодирована унарной системой счисления . Нири и Вудс (2006) представили другую конструкцию, которая заменяет 2-теговые системы на машины Тьюринга по часовой стрелке и имеет полиномиальные накладные расходы. [7]
Мэтью Кук представил свое доказательство универсальности Правила 110 на конференции в Институте Санта-Фе, состоявшейся перед публикацией A New Kind of Science . Wolfram Research заявила, что эта презентация нарушила соглашение Кука с его работодателем о неразглашении, и получила постановление суда об исключении статьи Кука из опубликованных материалов конференции. Тем не менее, существование доказательства Кука стало известно. Интерес к его доказательству возник не столько из-за его результата, сколько из-за его методов, в частности из-за технических деталей его построения. [8] Характер доказательства Кука значительно отличается от обсуждения Правила 110 в A New Kind of Science . С тех пор Кук написал статью, в которой изложил свое полное доказательство. [2]
Кук доказал, что Правило 110 универсально (или полно по Тьюрингу), показав, что это правило можно использовать для эмуляции другой вычислительной модели, циклической системы тегов , которая, как известно, универсальна. Сначала он выделил несколько космических кораблей , самовоспроизводящихся локализованных шаблонов, которые можно было построить на основе бесконечно повторяющегося шаблона во вселенной Правила 110. Затем он придумал способ взаимодействия комбинаций этих структур таким образом, чтобы их можно было использовать для вычислений.
Функция универсальной машины в правиле 110 требует, чтобы конечное число локализованных шаблонов было встроено в бесконечно повторяющийся фоновый шаблон. Фоновый шаблон имеет ширину четырнадцать ячеек и повторяется ровно каждые семь итераций. Шаблон — 00010011011111 .
Три локализованных шаблона имеют особое значение в универсальной машине Rule 110. Они показаны на изображении ниже, окруженные повторяющимся фоновым шаблоном. Самая левая структура смещается вправо на две ячейки и повторяется каждые три поколения. Она включает последовательность 0001110111, окруженную фоновым шаблоном, приведенным выше, а также две различные эволюции этой последовательности.
На рисунках время течет сверху вниз: верхняя линия представляет начальное состояние, а каждая последующая линия — состояние в следующий момент времени.
Центральная структура смещается влево на восемь ячеек и повторяется каждые тридцать поколений. Она включает последовательность 1001111 , окруженную фоновым рисунком, приведенным выше, а также двадцать девять различных эволюций этой последовательности.
Самая правая структура остается неподвижной и повторяется каждые семь поколений. Она включает последовательность 111, окруженную фоновым рисунком, приведенным выше, а также пять различных эволюций этой последовательности.
Ниже представлено изображение, показывающее первые две структуры, проходящие друг сквозь друга без взаимодействия, за исключением трансляции (слева), и взаимодействующие, образующие третью структуру (справа).
В правиле 110 есть и множество других космических кораблей, но они не играют столь важной роли в доказательстве универсальности.
Механизм циклической системы меток состоит из трех основных компонентов:
Начальное расстояние между этими компонентами имеет первостепенное значение. Для того чтобы клеточный автомат мог реализовать циклическую систему тегов, начальные условия автомата должны быть тщательно выбраны, чтобы различные локализованные структуры, содержащиеся в нем, взаимодействовали высокоупорядоченным образом.
Строка данных в циклической системе тегов представлена серией стационарных повторяющихся структур типа, показанного выше. Различное количество горизонтального пространства между этими структурами служит для различения символов 1 от символов 0. Эти символы представляют слово, на котором работает циклическая система тегов, и первый такой символ уничтожается при рассмотрении каждого правила производства. Когда этот ведущий символ равен 1, новые символы добавляются в конец строки; когда он равен 0, новые символы не добавляются. Механизм достижения этого описан ниже.
Справа вводится ряд структур, движущихся влево, показанного выше типа, разделенных различным количеством горизонтального пространства. Большое количество этих структур объединено с различными интервалами для представления нулей и единиц в правилах производства циклической системы тегов. Поскольку правила производства системы тегов известны на момент создания программы и бесконечно повторяются, шаблоны нулей и единиц в начальном состоянии могут быть представлены бесконечно повторяющейся строкой. Каждое правило производства отделено от следующего другой структурой, известной как разделитель правил (или разделитель блоков ), которая движется влево с той же скоростью, что и кодирование правил производства.
Когда разделитель правил, движущийся влево, встречает стационарный символ в строке данных циклической системы тегов, он уничтожает первый встреченный им символ. Однако его последующее поведение зависит от того, был ли символ, закодированный строкой, 0 или 1. Если это 0, разделитель правил преобразуется в новую структуру, которая блокирует входящее правило производства. Эта новая структура уничтожается, когда встречает следующий разделитель правил.
Если, с другой стороны, символ в строке был 1, разделитель правил меняется на новую структуру, которая допускает входящее правило производства. Хотя новая структура снова разрушается, когда она сталкивается со следующим разделителем правил, она сначала позволяет серии структур пройти влево. Затем эти структуры заставляют себя присоединяться к концу строки данных циклической системы тегов. Это окончательное преобразование выполняется с помощью серии бесконечно повторяющихся, движущихся вправо тактовых импульсов в движущемся вправо шаблоне, показанном выше. Тактовые импульсы преобразуют входящие движущиеся влево символы 1 из правила производства в неподвижные символы 1 строки данных, а входящие символы 0 из правила производства в неподвижные символы 0 строки данных.
На рисунке выше представлена схематическая диаграмма реконструкции циклической системы тегов в правиле 110.
