Правило 110

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Эволюция клеточного автомата по Правилу 110

История[править | править вики-текст]

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

Определение[править | править вики-текст]

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

Текущее состояние 111 110 101 100 011 010 001 000
Новое состояние центральной клетки 0 1 1 0 1 1 1 0

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