Метод синтеза генераторов детерминированных тестов на сетях клеточных автоматов (СКА)

дипломная работа

1.4 Моделирование физических процессов

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

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

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

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

Часто задавался вопрос о том, могут ли клеточные автоматы моделировать непосредственно законы физики, а не некие аспекты их проявления в природе. Камнем преткновения стал вопрос обратимости пути развития, основного свойства микроскопической физики. При решении такого рода задач решётка становится пространством для моделирования некой среды.

Пусть на рис.1.7 изображено некое вещество. В задаче существенен какой-то его параметр. Зоны, обладающие одинаковым значением этого параметра, выделены одним и тем же цветом. Чтобы решать задачу численно необходимо как-то описать для машины исследуемый материал, сообщить распределение значений параметра. Для этого следует произвести дискретизацию, заменить непрерывный массив данных конечным числом информативных значений.

Наложим на вещество решётки, составленные из квадратов и шестиугольников. В каждую клетку поместим значение, соответствующее той зоне материала, которую она охватывает.

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

Рис 1.7 - Дискретизация на примере квадратной и гексагональной решёток

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

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

Таким образом, вычислительная система может оперировать своей материальной частью, модифицировать, расширять себя и строить себе подобных [1]. Хотя системы этого класса и были придуманы Джоном фон Нейманом, такая параллельная архитектура получила название "не-фон-неймановской", так как последовательную архитектуру он создал раньше.

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

Например, рассмотрим автомат, реализующий игру "Жизнь". При данных решётке и правилах, меняя лишь состояние решётки, можно реализовать универсальные вычислительные системы, позволяющие производить любые вычисления, которые, по своим выразительным способностям эквивалентны произвольным машинам Тьюринга и клеточным автоматам [7]. Теми же возможностями обладает, в частности, автомат, называемый компьютером Бэнкса [1]. Однако использовать их крайне неэффективно, но с теоретической точки зрения это - важный результат.

Делись добром ;)