Элементарные клеточные автоматы

256 правил. Одномерный ряд клеток. Каждая клетка смотрит на себя и двух соседей, и по правилу решает своё следующее состояние. Из этого — фракталы, хаос, и даже Тьюринг-полнота.

Что здесь происходит

Элементарный клеточный автомат — это одномерный ряд ячеек, каждая из которых может быть «живой» (1) или «мёртвой» (0). На каждом шаге каждая ячейка смотрит на себя и двух соседей — это 3 бита, 8 возможных комбинаций. Правило определяет, какой будет ячейка на следующем шаге для каждой комбинации.

Номер правила — это просто десятичная запись этих 8 бит результата. Правило 110 = 01101110 в двоичной. Стивен Вольфрам систематически исследовал все 256 правил и обнаружил среди них фракталы (правило 90), генераторы случайности (правило 30), и даже Тьюринг-полную систему (правило 110).