13.4.   КЛЕТОЧНЫЕ АВТОМАТЫ

В этом разделе мы познакомимся с другим классом геометрических моделей, которые называются клеточными автоматами. Отличительной особенностью клеточных автоматов являются их полная дискретность и, следовательно, приспособленность к точному моделированию на цифровом компьютере. Клеточные автоматы были впервые рассмотрены фон Нейманом и Уламом в 1948 г. в качестве возможной идеализации биологического самовоспроизводства. Наш интерес к ним обусловлен, главным образом, тем, что многие модели клеточных автоматов являются примерами простых динамических систем, которые дают упорядоченные узоры, возникающие из случайных начальных условий. Вы можете убедиться в том, что пространственные узоры многих клеточных автоматов напоминают узоры, наблюдаемые в природных явлениях, таких как коагуляция и рост кристалов. Однако сейчас мы будем рассматривать клеточные автоматы как интересные компьютерные модели, которые сохраняют привлекательные возможности для описания физических систем.

Клеточные автоматы представляют собой математические идеализации физических систем, в которых пространство и время дискретны, а физические величины принимают конечное множество дискретных значений. Представьте регулярную решетку (илн «таблицу») ячеек («клеток»), каждая из которых может находиться в конечном числе возможных состояний, например 0 или 1. Состояние системы полностью определяется значениями переменных в каждой клетке. Важными особенностями клеточных автоматов являются следующие:

Состояние каждой ячейки обновляется за последовательность дискретных шагов по времени.

Переменные в каждой ячейке изменяются  одновременно («синхронно»), исходя из значений переменных иа предыдущем шаге.

Правило определения  нового состояния  ячейки  зависит только от локальных значений в соседних ячейках.

Сначала рассмотрим одномерный автомат с двумя допустимыми значениями переменных в каждой клетке, при этом окружением данной клетки считается она сама и ближайшие клетки справа и слева. Для такого «элементарного» автомата Существует 256 возможных правил. На рис. 13.14 иллюстрируется один конкретный набор локальных правил. Свойства всех 256 элементарных одномерных клеточных автоматов каталогизированы (Вольфрам). В задаче 13.10 изучаются некоторые свойства одномерных клеточных автоматов.