WikiSort.ru - Не сортированное

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

История

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

Определение

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

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

Для улучшения этой статьи желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).