Правило 110¶

Правило 110 — это элементарный клеточный автомат с двумя состояниями (0 и 1) и радиусом взаимодействия 1, демонстрирующий сложное, непериодическое и, как было доказано, полное по Тьюрингу поведение. Относится к классу IV по классификации Стивена Вольфрама и является одним из самых известных примеров того, как простая система может порождать вычислительно универсальное поведение.

¶История

Правило 110 было впервые описано Стивеном Вольфрамом в 1983 году в его работе по систематическому изучению клеточных автоматов. Вольфрам исследовал все 256 возможных правил для одномерных клеточных автоматов с двумя состояниями и радиусом 1, и классифицировал их по четырём классам поведения. Правило 110 оказалось в классе IV — автоматы, которые генерируют сложные, локализованные структуры (например, движущиеся «частицы» и «поезда»), взаимодействующие друг с другом.

В 2000 году Мэтью Кук, работавший под руководством Вольфрама, представил доказательство того, что правило 110 является тьюринг-полным, то есть способно моделировать любую вычислимую функцию. Это доказательство было опубликовано в 2004 году в книге Вольфрама «A New Kind of Science». Кук показал, что правило 110 может эмулировать циклическую теговую систему, которая, в свою очередь, является универсальной моделью вычислений.

¶Определение и описание

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

Всего существует 8 возможных комбинаций состояний трёх соседних ячеек (от 111 до 000). Для каждой из этих комбинаций правило 110 задаёт новое состояние центральной ячейки. Правило обозначается числом 110, которое получается при интерпретации последовательности выходных битов как двоичного числа (от комбинации 111 до 000). В случае правила 110 эта последовательность выглядит так: 0, 1, 1, 0, 1, 1, 1, 0. В двоичной записи это 01101110, что соответствует десятичному числу 110.

¶Таблица переходов

¶Классификация Вольфрама и поведение

Стивен Вольфрам разделил все одномерные клеточные автоматы на четыре класса:

• Класс I: Почти все начальные конфигурации приводят к однородному состоянию (например, все ячейки становятся 0 или 1).
• Класс II: Возникают простые периодические структуры.
• Класс III: Хаотическое, непериодическое поведение, напоминающее шум.
• Класс IV: Сложное поведение, сочетающее как периодические, так и хаотические элементы. Возникают локализованные структуры (частицы), которые движутся, сталкиваются и взаимодействуют.

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

• Странные (или подвижные) частицы: Локализованные структуры, которые движутся по решётке с постоянной скоростью. В правиле 110 существует несколько типов таких частиц, обозначаемых буквами (например, A, B, C, D, E, F, G, H).
• Поезда (trains): Группы частиц, движущиеся вместе.
• Стены (walls): Стабильные, неподвижные структуры, которые могут отражать или поглощать частицы.

Взаимодействие этих частиц друг с другом и со стенами лежит в основе вычислительной универсальности правила 110. Например, столкновение двух частиц может привести к их аннигиляции, рождению новой частицы или изменению направления движения.

¶Доказательство тьюринг-полноты

В 2000 году Мэтью Кук доказал, что правило 110 является тьюринг-полным. Это означает, что оно может выполнять любые вычисления, которые может выполнить машина Тьюринга, при условии бесконечной решётки и бесконечного времени.

Доказательство Кука основано на эмуляции циклической теговой системы (cyclic tag system). Теговая система — это простая модель вычислений, использующая строку символов и набор правил переписывания. Кук показал, как можно закодировать состояния и правила теговой системы в виде начальной конфигурации правила 110, а затем интерпретировать эволюцию автомата как выполнение шагов теговой системы.

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

Это доказательство имеет важное значение, так как показывает, что даже чрезвычайно простая система может обладать огромной вычислительной мощностью. Правило 110 является одним из самых простых известных тьюринг-полных автоматов.

¶Применение и значение

Правило 110 не имеет прямого практического применения в промышленности или быту. Его значение в первую очередь теоретическое и философское.

• Теория вычислений: Правило 110 служит простым и наглядным примером вычислительной универсальности, демонстрируя, что сложные вычисления могут возникать из простых правил.
• Изучение сложных систем: Оно является модельным объектом для изучения эмерджентности — появления сложного поведения из простых взаимодействий.
• Философия науки: Работа Вольфрама, в том числе и правило 110, привела к пересмотру взглядов на то, как можно описывать и моделировать сложные явления в природе. Вольфрам предположил, что многие сложные системы в природе (например, турбулентность, биологические структуры) могут быть описаны простыми программами, подобными клеточным автоматам.
• Образование: Правило 110 часто используется в учебных курсах по информатике, теории автоматов и сложным системам для демонстрации ключевых концепций.

¶Интересные факты

• Правило 110 является одним из 256 правил для одномерных клеточных автоматов с двумя состояниями и радиусом 1. Вольфрам назвал такие автоматы «элементарными».
• Существуют и другие тьюринг-полные элементарные клеточные автоматы, например, правило 124 и правило 137.
• Доказательство тьюринг-полноты правила 110 было впервые представлено на конференции, но не было опубликовано в рецензируемом журнале до 2004 года, когда оно вошло в книгу Вольфрама. Это вызвало некоторые споры в научном сообществе.
• Визуализация эволюции правила 110 из случайного начального состояния часто напоминает узоры на раковинах моллюсков или другие природные структуры, что привлекает внимание не только учёных, но и художников.

¶Источники

• Wolfram, S. (2002). A New Kind of Science. Wolfram Media.
• Cook, M. (2004). Universality in Elementary Cellular Automata. Complex Systems, 15(1), 1-40.
• Wolfram, S. (1983). Statistical mechanics of cellular automata. Reviews of Modern Physics, 55(3), 601-644.