связи. В качестве окрестности ячейки используется подмножество яче-
ек, смежных с данной, а также, возможно, она сама. Использование
более широкого множества увеличивает число аргументов локальной
функции связи и делает ее реализацию непрактичной.
Свойства клеточных автоматов
.
Зависимость числа единичных
заполнений ячеек от веса локальной функции связи.
Локальная функ-
ция связи является основным параметром, определяющим особенно-
сти функционирования КлА. Важной задачей является изучение связи
между характеристиками локальной функции связи и распределением
заполнений ячеек решетки КлА.
Рассмотрим локальную функцию связи
f
, вектор значений которой
имеет длину
2
s
, где
s
— число аргументов функции (оно совпадает с
мощностью окрестности ячейки). Пусть вес функции
f
, т.е. число
наборов аргументов, на которых функция принимает единичные зна-
чения, равно
ω
. Относительным весом функции назовем величину
ω
0
=
ω/
2
s
.
Предположим, что начальные заполнения ячеек решетки распре-
делены случайно и равновероятно, т.е. для произвольной ячейки
m
имеем
Pr
[
m
= 0] =
Pr
[
m
= 1] =
1
2
.
В таком случае все возможные двоичные наборы
Ψ(
m
)
длины
s
, со-
ответствующие заполнениям ячеек из окрестности
m
, также будут
встречаться с равной вероятностью.
Поскольку вес функции
f
равен
ω
и все наборы аргументов равно-
вероятны, вероятности того, что функция
f
принимает единичное или
нулевое значение на наборе
Ψ(
m
)
, составляют соответственно
Pr
[
f
(Ψ(
m
)) = 1] =
ω/
2
s
=
ω
0
,
Pr
[
f
(Ψ(
m
)) = 0] = 1
−
ω
0
.
Напомним, что заполнение ячейки
m
на следующем такте рабо-
ты КлА совпадает со значением локальной функции связи на наборе
Ψ(
m
)
. Из этого очевидным образом следует, что одинаковое число еди-
ничных и нулевых заполнений ячеек достигается только при
ω
0
= 1
/
2
,
что соответствует равновесным локальным функциям связи.
На рис. 1 изображены графики временн´ой зависимости отношения
числа единичных заполнений к общему числу ячеек КлА для различ-
ных весов локальной функции связи. Данные отражают усреднение
для 1 000 различных КлА с размерами решетки
37
×
11
ячеек и слу-
чайно выбранной локальной функцией связи от 9 аргументов (длина
вектора значений 512). На графиках хорошо видно, что каждому зна-
чению относительного веса
ω
0
соответствует быстрое приближение к
некоторому стационарному значению числа единичных ячеек КлА.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2011. № 2 69
