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

История

Мэттью Кук представил своё доказательство на конференции Института Санта-Фе в 1998 году, но Вольфрам запретил включать это доказательство в бумажную версию материалов конференции, потому что не хотел, чтобы оно было опубликовано до издания книги A New Kind of Science. В 2004 году доказательство Кука было опубликовано в журнале Вольфрама «Complex Systems»(выпуск 15, том 1), через 10 лет после того как Кук впервые представил его.

Определение

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

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