Клеточный автоматCellular automaton

Общая информация

Клеточный автомат представляет собой набор клеток, прилегающих друг к другу и образующих решётку. Само поле может быть бесконечным или конечным. Если оно конечно, то оно может быть закольцовано. Каждая клетка находится в одном из конечного набора состояний. Для каждой клетки определена окрестность. Существует набор правил для перехода клетки из одного состояния в другое. Как правило, для всех клеток правила переходов из одного состояния в другое одинаковы. Наиболее известным примером клеточного автомата является игра «Жизнь».

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

Элементарный клеточный автомат представляет собой одномерную ленту, бесконечно протянутую в обе стороны, в которой клетки находятся в одном из двух состояний: 0 или 1. Также есть правило, определяющее состояние клетки на следующем шаге. Для определения состояния клетки на следующем шаге используется состояние этой клетки, а также состояния двух её соседних клеток.

Можно заметить, что существует 2³ = 8 возможных комбинаций состояний клетки и двух её соседей. Правило должно указывать следующее состояние для всех этих восьми комбинаций. Таким образом, существует всего 2⁸ = 256 правил. Стивен Вольфрам предложил систему нумерации правил, которая сейчас известна как код Вольфрама. Суть кода Вольфрама заключается в выписывании в порядке убывания возможных комбинаций (111, 110, 101, 100, 011, 010, 001, 000), а под ними выписывать соответствующий результат комбинаций. Полученную строку результатов необходимо интерпретировать как двоичное число.

Пример кода Вольфрама

111	110	101	100	011	010	001	000
0	1	1	1	0	0	1	1

01110011₂ = 115₁₀. Таким образом, схема из таблицы соответствует правилу 115.

Классификация

Клеточный автомат быстро переходит к однородному стабильному состоянию.
Клеточный автомат быстро переходит в неоднородное неизменяемое состояние или возникают периодически повторяющиеся последовательности.
Клеточный автомат образует хаотичные последовательности. Стабильные структуры быстро исчезают.
Клеточный автомат может формировать сложные структуры. Некоторые клеточные автоматы данного типа обладают универсальностью по Тьюрингу. Например, таким автоматом является игра «Жизнь».