Введение
Элементарный клеточный автомат
Клеточный автомат по правилу 110 (часто называемый просто правилом 110) — это элементарный клеточный автомат, демонстрирующий интересное поведение на границе между стабильностью и хаосом. В этом отношении он схож с игрой «Жизнь» Конвея. Как и «Жизнь», клеточный автомат по правилу 110 с определенным повторяющимся фоновым рисунком известен как Тьюринг-полный. Это означает, что в принципе, любые вычисления или компьютерные программы могут быть смоделированы с использованием этого автомата.
История
В 2004 году Мэтью Кук опубликовал доказательство того, что правило 110 с определенным повторяющимся фоновым рисунком является Тьюринг-полным, то есть способно к универсальным вычислениям, что Стивен Вольфрам предположил в 1985 году. Кук представил свое доказательство на конференции Института Санта-Фе CA98 до публикации книги Вольфрама «Новый вид науки». Это привело к юридическому спору, основанному на соглашении о конфиденциальности с 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 существует множество других «космических кораблей», но они не играют столь важной роли в доказательстве универсальности.
Работа системы циклических меток
На рисунке выше представлена схема реконструкции циклической системы меток в правиле 110.