Клеточные автоматы

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

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

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

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

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

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

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

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