Что такое клеточный автомат?

ВВЕДЕНИЕ

На протяжении всей своей истории человечество постоянно генерировало какие-то идеи, обеспечивающие его развитие. Делались открытия и появлялись изобретения в са­мых разных отраслях жизни. Каменный топор, колесо, бумага, пенициллин, автомобиль - предметы, вещества и соответствующие им понятия, без которых развитие цивилизации представить невозможно. Истина, бог, время, функция - абстрактные понятия, возникшие в процессе развития человечества. Все они возникали тогда, когда знания и потребности человека достигали определённого уровня. По всей видимости, в конце 60-х годов XX века понятие «клеточный автомат» было просто необходимо для дальнейшего прогресса физи­ки, биологии, химии, математики, компьютерных наук и других областей знаний, так они изобретались многократно под разными названиями, в разных странах, людьми, работаю­щими в разных областях знаний. Тем не менее, концептуально возникшие понятия были практически эквивалентны. «Итеративные массивы», «вычисляющие пространства», «од­нородные структуры» и «клеточные автоматы» являются синонимами.

Когда Станислав Улам (Stanislaw Ulam) начинал свои исследования он, навер­ное, не предполагал, что, основываясь на его идеях, выдающийся американский учёный Джон фон Нейман (John von Neumann) придумает концепцию клеточных автоматов. Хотя фон Нейман был математиком и физиком, эта идея пришла к нему при решении задач из области биологии. Он использовал клеточные автоматы для создания более правдоподоб­ных моделей пространственно протяжённых систем.

Однако вернёмся назад во времени. В конце Второй Мировой Войны, в то время как фон Нейман создавал один из первых электронных компьютеров, немецкий инженер Кон­рад Цузе (Konrad Zuse) прятался от нацистов в австрийских Альпах. Там, в уединении, у него возникло множество идей из области параллельных вычислений. Среди прочего он придумал и «вычисляющие пространства», то есть клеточные автоматы. Особый инте­рес Цузе вызывало их применения к задачам численного моделирования в механике. К со­жалению политическая обстановка помешала работам учёному стать известными в то вре­мя. За работами же фон Неймана следил весь научный мир.

Профессиональные математики пришли к клеточным автоматам, рассматривая ите­рационные преобразования пространственно распределённых структур с дискретным на­бором состояний. Сразу стали возникать решения важных теоретических задач в этой области, например, вопросов обратимости и вычислимости. В группе компьютерной логи­ки университета штата Мичиган Джон Холланд (John Holland) применял клеточные авто­маты к решению задач адаптации и оптимизации.

Однако настоящий эффект разорвавшейся бомбы произвела статья ведущего рубри­ки математических игр и головоломок журнала «Scientific American» Мартина Гарднера (Martin Gardner). Он опубликовал описание клеточного автомата Джона Хортона Конвея (John Horton Conway) «Жизнь». Игра «Жизнь», как стали называть этот автомат, фактически, стала культовой и сделала понятия «клеточный автомат» чрезвычайно попу­лярным особенно среди людей с техническим образованием.

Область применения клеточных автоматов чрезвычайно широка. Однако необходимо отметить, что в подавляющем большинстве случаев, они применяются либо в качестве параллельных вычислительных сред, либо в качестве сред моделирования про­странственно распределённых систем (например, физических, биологических, химических, социологических и других).

Многофункциональная среда моделирования клеточных автоматов позволила бы использовать вычислительную машину в качестве: подчас весьма дорогостоящей экспериментальной установки для физических, био­логических, химических и прочих опытов; средства реализации и визуализации алгоритмов параллельных вычислений.

 

 

 

 

 

Что такое клеточный автомат?

Клеточный автомат является дискретной динамической системой, поведение ко­торой полностью определяется в терминах локальных зависимостей.

Экземпляр пространства дискретного множества будем называть решёткой клеточ­ного автомата, а каждый его элемент - клеткой. Каждая клетка характеризуется опреде­лённым значением из некого множества. О клетке говорят, что она содержит или имеет соответствующее значение, либо находится или пребывает в состоянии, кодируемом дан­ным значением. Оно можем быть булевым, целым, числом с плавающей точкой, множест­вом или другим объектом, в зависимости от потребностей задачи.

Совокупность состояний всех клеток решётки называется состоянием решётки. Состояние решётки меняется в соответствии с некоторым законом, который называется правилами клеточного автомата. Каждое изменение состояния решётки называется итера­цией. Время в рассматриваемой модели дискретно и каждая итерация соответствует неко­му моменту времени.

Правила определяют, какое значение должно содержаться в клетке в следующий момент времени, в зависимости от значений в некоторых других клетках в текущий мо­мент, а также, возможно, от значения, содержащегося в ней самой в текущий момент. Если новое состояние клетки зависит от текущего её состояния, то о соответствующем клеточ­ном автомате говорят, что он является автоматом с клетками с памятью, иначе - авто­матом с клетками без памяти.

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

В одномерном (линейном) клеточном автомате решетка представляет собой це­почку клеток (одномерный массив), в которой для каждой из них, кроме край­них, имеется по два соседа.

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

В двумерном (плоскостном) клеточном автомате решетка реализуется двумерным массивом. В ней каждая клетка имеет восемь соседей.

Автоматы с клетками без памяти

При этом отметим, что, несмотря на то, что в автоматах этого класса клетки па­мятью не обладают, за счет переобозначения переменных, такие автоматы в це­лом имеют память. Этот класс автоматов является простейшим, применение которого обеспечивает самовоспроизведение.