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

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

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

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

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