Простые правила, сложное поведение
Элементарные клеточные автоматы — одни из простейших вычислительных систем: ряд ячеек, каждая включена или выключена, обновляющихся одновременно по локальному правилу, учитывающему лишь три ячейки (левый сосед, сама ячейка, правый сосед). Существует ровно 256 возможных правил, пронумерованных от 0 до 255 по конвенции Стивена Вольфрама. Несмотря на предельную простоту, некоторые из этих правил порождают паттерны необычайной сложности.
Классификация Вольфрама
Вольфрам разделил 256 правил на четыре поведенческих класса. Правила класса 1 (напр., правило 0, правило 255) быстро схлопываются в однородное состояние. Правила класса 2 (напр., правило 4, правило 108) создают простые периодические паттерны — полоски, треугольники, повторяющиеся блоки. Правила класса 3 (напр., правило 30, правило 90) порождают хаотические, на вид случайные паттерны. Правила класса 4 (напр., правило 110) находятся на границе — создают сложные долгоживущие структуры, взаимодействующие замысловатым образом.
Ключевые правила для исследования
Правило 30 — визитная карточка хаоса в клеточных автоматах. Из одной ячейки оно порождает паттерн, который выглядит случайным слева, но имеет регулярную структуру справа. Вольфрам использовал его как генератор случайных чисел.
Правило 90 — создаёт треугольник Серпинского, знаменитый фрактал. Это потому, что правило 90 эквивалентно XOR двух соседей, а двоичные строки треугольника Паскаля по модулю 2 дают тот же паттерн.
Правило 110 — доказано полным по Тьюрингу Мэтью Куком в 2004 году. Это означает, что в принципе этот простейший одномерный автомат может выполнить любое вычисление — глубочайший результат, связывающий простейшие системы с самыми мощными.
Эмерджентность и вычисления
Клеточные автоматы демонстрируют фундаментальный принцип: сложное глобальное поведение может возникать из простых локальных правил без центрального управления. Этот принцип лежит в основе явлений от роста кристаллов до пробок и развития биологических организмов. Тот факт, что правило 110 вычислительно универсально, предполагает, что способность к сложности присуща даже минимальным системам.