Правило 110 (англ. Rule 110) — один из вариантов элементарного клеточного автомата, в котором последовательность результатов преобразования образуют бинарную последовательность 01101110, что является двоичным представлением десятичного числа 110. Все элементарные клеточные автоматы представляют собой бесконечную ленту из последовательно размещённых клеток, которые могут иметь только два состояния (0 и 1) и при этом будущее состояние клетки зависит от текущих значений трёх клеток — её самой и двух её ближайших соседей.
Для автомата, действующего по правилу 110, характерно поведение на границе хаоса и стабильности. Такое же поведение присуще игре «Жизнь». Доказано, что клеточный автомат с правилом 110 является Тьюринг-полным, то есть любая вычислительная процедура может быть реализована с его помощью. Возможно, что это самая простая система, полная по Тьюрингу[1].
В простейших клеточных автоматах одномерный массив нулей и единиц преобразуется согласно набору правил. Значение клетки на следующем шаге формируется на основе текущего состояния этой клетки и двух её соседей (справа и слева). Правило 110 имеет следующий набор преобразований:
Наименование Правило 110 определяется кодом Вольфрама — бинарная последовательность 01101110 при переводе в десятичную систему даст число 110.
Стивен Вольфрам рассматривал все возможные варианты простейших клеточных автоматов, состоящих из трёх соседних клеток ленты, каждая из которых может принимать лишь два состояния (1/0, заполнена/пуста, жива/мертва). Всего может быть 8 вариантов текущего состояния для трёх соседних клеток. Так как каждый из этих вариантов может порождать лишь два новых состояния центральной клетки, то общее количество простейших автоматов 256. Если для всех 8 вариантов текущего состояния набор конечных состояний интерпретировать как десятичное число в двоичном коде, то мы получим сопоставление этого десятичного числа с однозначным набором инструкций преобразования одного из простейших клеточных автоматов. Вольфрам назвал их «Правилами» с указанием соответствующего номера.
При задании в качестве исходного состояния хаотической последовательности получаемые результаты преобразований по разным правилам Вольфрам сгруппировал в 4 класса: