Линейная алгебра и мат. Статистика
Виды клеточных автоматов: В зависимости от размерности решетки
жүктеу/скачать 294.26 Kb.
|
- Бұл бет үшін навигация:
- Элементарные (простейшие) клеточные автоматы
| Виды клеточных автоматов:
В зависимости от размерности решетки: одно-, дву-, трёхмерные, и т.д. В зависимости от количества возможных состояний: бинарные, троичные, и т.д. КА бывают синхронные и асинхронные. В синхронных все клетки системы обновляются одновременно, в асинхронных — каждая делает это независимо. В разных клеточных автоматах может по-разному определяться окрестность клетки По типам поведения Клетки одномерного автомата располагаются в целочисленных узлах координатной прямой. Для каждой клетки соседи определяются естественным образом: соседями -ой клетки являются все клетки удаленные от заданной на расстояние не большее . Параметр называется рангом клеточного автомата. Минимальный ранг равен единице. В этом случае имеется всего два соседа с номерами , а локальная окрестность -ой клетки содержит три клетки , и . Число клеток автомата может быть бесконечным или конечным. В последнем случае будем считать, что клетки располагаются в точках с координатами от до . Для граничных точек этого сегмента не выполняется условие однородности, т. к. у этих точек имеется всего по одному соседу. Поэтому приходится вводить специальные условия, называемые граничными, которые бы говорили, как должны изменяться состояния граничных клеток. В наиболее распространенных случаях состояния граничных клеток либо просто фиксируются (например, нулевые граничные условия), либо используются так называемые циклические условия, когда отрезок сворачивается в цикл — сразу за -ой точкой идет нулевая точка. Еще одним числовым параметром одномерного клеточного автомата является число состояний . Минимальное число равно двум, такие автоматы называются двоичными. Состояния двоичного автомата обозначаются как и . Одномерные двоичные клеточные автоматы ранга 1 называются элементарными. Таким образом, чтобы определить элементарный клеточный автомат, достаточно задать его систему правил (и граничные условия, если число клеток конечно). Т. к. локальная окрестность любой клетки элементарного автомата содержит только три клетки, каждая из которых может находиться в двух состояниях, то всего надо задать правил, для каждого возможного состояния локальной окрестности точки. Эти правила можно задавать либо формулой, либо таблично Элементарные (простейшие) клеточные автоматы Одномерный бинарный (с двумя возможными состояниями) клеточный автомат, где состояние клетки в каждый момент времени зависит только от её собственного состояния и состояний смежных с ней клеток в предыдущий момент времени. Простейших клеточных автоматов существует всего 256, и поведение некоторых из них дублирует другие. Но, несмотря на это, широко известный в узких кругах Стивен Вольфрам посвятил годы жизни их изучению, до него этим также занимались десятки математиков, да и по сей день ученые пишут диссертации и научные труды на эту тему. Также Вольфрам предложил разделить клеточные автоматы на четыре класса по типу поведения: жүктеу/скачать 294.26 Kb. Достарыңызбен бөлісу:
|