Что такое клеточный автомат?
ВВЕДЕНИЕ
На протяжении всей своей истории человечество постоянно генерировало какие-то идеи, обеспечивающие его развитие. Делались открытия и появлялись изобретения в самых разных отраслях жизни. Каменный топор, колесо, бумага, пенициллин, автомобиль - предметы, вещества и соответствующие им понятия, без которых развитие цивилизации представить невозможно. Истина, бог, время, функция - абстрактные понятия, возникшие в процессе развития человечества. Все они возникали тогда, когда знания и потребности человека достигали определённого уровня. По всей видимости, в конце 60-х годов XX века понятие «клеточный автомат» было просто необходимо для дальнейшего прогресса физики, биологии, химии, математики, компьютерных наук и других областей знаний, так они изобретались многократно под разными названиями, в разных странах, людьми, работающими в разных областях знаний. Тем не менее, концептуально возникшие понятия были практически эквивалентны. «Итеративные массивы», «вычисляющие пространства», «однородные структуры» и «клеточные автоматы» являются синонимами.
Когда Станислав Улам (Stanislaw Ulam) начинал свои исследования он, наверное, не предполагал, что, основываясь на его идеях, выдающийся американский учёный Джон фон Нейман (John von Neumann) придумает концепцию клеточных автоматов. Хотя фон Нейман был математиком и физиком, эта идея пришла к нему при решении задач из области биологии. Он использовал клеточные автоматы для создания более правдоподобных моделей пространственно протяжённых систем.
Однако вернёмся назад во времени. В конце Второй Мировой Войны, в то время как фон Нейман создавал один из первых электронных компьютеров, немецкий инженер Конрад Цузе (Konrad Zuse) прятался от нацистов в австрийских Альпах. Там, в уединении, у него возникло множество идей из области параллельных вычислений. Среди прочего он придумал и «вычисляющие пространства», то есть клеточные автоматы. Особый интерес Цузе вызывало их применения к задачам численного моделирования в механике. К сожалению политическая обстановка помешала работам учёному стать известными в то время. За работами же фон Неймана следил весь научный мир.
Профессиональные математики пришли к клеточным автоматам, рассматривая итерационные преобразования пространственно распределённых структур с дискретным набором состояний. Сразу стали возникать решения важных теоретических задач в этой области, например, вопросов обратимости и вычислимости. В группе компьютерной логики университета штата Мичиган Джон Холланд (John Holland) применял клеточные автоматы к решению задач адаптации и оптимизации.
Однако настоящий эффект разорвавшейся бомбы произвела статья ведущего рубрики математических игр и головоломок журнала «Scientific American» Мартина Гарднера (Martin Gardner). Он опубликовал описание клеточного автомата Джона Хортона Конвея (John Horton Conway) «Жизнь». Игра «Жизнь», как стали называть этот автомат, фактически, стала культовой и сделала понятия «клеточный автомат» чрезвычайно популярным особенно среди людей с техническим образованием.
Область применения клеточных автоматов чрезвычайно широка . Однако необходимо отметить, что в подавляющем большинстве случаев, они применяются либо в качестве параллельных вычислительных сред, либо в качестве сред моделирования пространственно распределённых систем (например, физических, биологических, химических, социологических и других).
Многофункциональная среда моделирования клеточных автоматов позволила бы использовать вычислительную машину в качестве: подчас весьма дорогостоящей экспериментальной установки для физических, биологических, химических и прочих опытов; средства реализации и визуализации алгоритмов параллельных вычислений.
Что такое клеточный автомат?
Клеточный автомат является дискретной динамической системой, поведение которой полностью определяется в терминах локальных зависимостей.
Экземпляр пространства дискретного множества будем называть решёткой клеточного автомата, а каждый его элемент - клеткой. Каждая клетка характеризуется определённым значением из некого множества. О клетке говорят, что она содержит или имеет соответствующее значение, либо находится или пребывает в состоянии, кодируемом данным значением. Оно можем быть булевым, целым, числом с плавающей точкой, множеством или другим объектом, в зависимости от потребностей задачи.
Совокупность состояний всех клеток решётки называется состоянием решётки. Состояние решётки меняется в соответствии с некоторым законом, который называется правилами клеточного автомата. Каждое изменение состояния решётки называется итерацией. Время в рассматриваемой модели дискретно и каждая итерация соответствует некому моменту времени.
Правила определяют, какое значение должно содержаться в клетке в следующий момент времени, в зависимости от значений в некоторых других клетках в текущий момент, а также, возможно, от значения, содержащегося в ней самой в текущий момент. Если новое состояние клетки зависит от текущего её состояния, то о соответствующем клеточном автомате говорят, что он является автоматом с клетками с памятью, иначе - автоматом с клетками без памяти.
Одномерные клеточные автоматы
В одномерном (линейном) клеточном автомате решетка представляет собой цепочку клеток (одномерный массив), в которой для каждой из них, кроме крайних, имеется по два соседа.
Двумерные клеточные автоматы
В двумерном (плоскостном) клеточном автомате решетка реализуется двумерным массивом. В ней каждая клетка имеет восемь соседей.
Автоматы с клетками без памяти
При этом отметим, что, несмотря на то, что в автоматах этого класса клетки памятью не обладают, за счет переобозначения переменных, такие автоматы в целом имеют память. Этот класс автоматов является простейшим, применение которого обеспечивает самовоспроизведение.