Правило 110

Правило 110 (англ. Rule 110) — один из вариантов элементарного клеточного автомата, в котором последовательность результатов преобразования образуют бинарную последовательность 01101110, что является двоичным представлением десятичного числа 110. Все элементарные клеточные автоматы представляют собой бесконечную ленту из последовательно размещённых клеток, которые могут иметь только два состояния (0 и 1) и при этом будущее состояние клетки зависит от текущих значений трёх клеток — её самой и двух её ближайших соседей.

Для автомата, действующего по правилу 110, характерно поведение на границе хаоса и стабильности. Такое же поведение присуще игре «Жизнь». Доказано, что клеточный автомат с правилом 110 является Тьюринг-полным, то есть любая вычислительная процедура может быть реализована с его помощью. Возможно, что это самая простая система, полная по Тьюрингу^[1].

В простейших клеточных автоматах одномерный массив нулей и единиц преобразуется согласно набору правил. Значение клетки на следующем шаге формируется на основе текущего состояния этой клетки и двух её соседей (справа и слева). Правило 110 имеет следующий набор преобразований:

Наименование Правило 110 определяется кодом Вольфрама — бинарная последовательность 01101110 при переводе в десятичную систему даст число 110.

В символах булевой алгебры правило можно записать^[2]:

(p, q, r) ↦ (q AND (NOT p)) OR (q XOR r)

Вариант математического преобразования:

(p, q, r) ↦ (q + r + q r + p q r) mod 2

Стивен Вольфрам рассматривал все возможные варианты простейших клеточных автоматов, состоящих из трёх соседних клеток ленты, каждая из которых может принимать лишь два состояния (1/0, заполнена/пуста, жива/мертва). Всего может быть 8 вариантов текущего состояния для трёх соседних клеток. Так как каждый из этих вариантов может порождать лишь два новых состояния центральной клетки, то общее количество простейших автоматов 256. Если для всех 8 вариантов текущего состояния набор конечных состояний интерпретировать как десятичное число в двоичном коде, то мы получим сопоставление этого десятичного числа с однозначным набором инструкций преобразования одного из простейших клеточных автоматов. Вольфрам назвал их «Правилами» с указанием соответствующего номера.

При задании в качестве исходного состояния хаотической последовательности получаемые результаты преобразований по разным правилам Вольфрам сгруппировал в 4 класса:

1. Сходятся к состоянию из одних нулей или единиц.
2. Сходятся к циклическому или стабильному состоянию.
3. Сохраняют хаотичное, нестабильное состояние.
4. Формируют как области с циклическими или стабильными состояниями, так и структуры, которые взаимодействуют друг с другом сложными способами.

Результаты исследования клеточных автоматов Вольфрам готовил к публикации в виде книги A New Kind of Science (издана в 2002 году). В исследовании ему помогал Мэттью Кук. Значительный интерес у Вольфрама вызвали автоматы 4-го класса. Среди них было и Правило 110, относительно которого Вольфрам в 1985 году предположил, что оно является полным по Тьюрингу^[1], то есть имеется возможность производить универсальные вычисления. Мэттью Кук разработал доказательство гипотезы Вольфрама, которое Кук представил на конференции Института Санта-Фе в 1998 году.

Так как работа Кука во многом базировалась на исследованиях Вольфрама, но была посвящена только одному из рассматриваемых правил, Вольфрам не хотел, чтобы доказательство было опубликовано до выхода его собственной книги, посвящённой рассмотрению всего множества подобных клеточных автоматов. Это привело к судебному разбирательству по поводу нарушения соглашения о неразглашении сведений, полученных при работе над книгой^[3]. Хотя представленное на конференции доказательство не было включено в бумажную версию материалов конференции, тем не менее стало известно о его существовании. В 2004 году доказательство Кука было опубликовано в журнале Вольфрама «Complex Systems» (выпуск 15, том 1)^[1].

Для доказательства универсальности правила 110 Кук показал, что оно позволяет имитировать другую вычислительную модель — систему циклических тегов^[англ.], которая является универсальной.

Сначала он выделил три самовоспроизводящиеся структуры-шаблоны. На рисунках время идет сверху вниз: верхняя строка представляет начальное состояние, а каждая следующая строка — состояние на следующей итерации. Самая левая на рисунке структура сдвигается на две ячейки вправо и повторяется каждые три поколения, формируя диагональную дорожку слева направо по фоновому рисунку.

Изображённая в центре рисунка структура сдвигается на восемь ячеек влево и повторяется каждые тридцать поколений, формируя диагональную структуру справа налево по такому же фоновому рисунку.

Самая правая на рисунке структура каждые семь поколений повторяет предыдущие состояния без смещений, остается неподвижной на базовом фоне.

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