On linear cellular automata

1. ВВЕДЕНИЕ

Конечные автоматы представляют из себя абстрактные математические модели дискретных устройств, имеющих один вход и один выход и в каждый момент времени находящихся в некотором состоянии из множества возможных (см., например, [1], [2]). Они используются в задачах моделирования многих естественных и технологических процессов. Так, в работе [3] был предложен клеточный автомат, развивающийся по очень простым правилам, но моделирующий поведение различных сложных систем. Частным случаем конечных автоматов являются клеточные автоматы, которые используются как инструмент моделирования процессов в различных областях знания, таких как градостроительная наука ([4], [5]), задачи моделирования транспортных потоков [6], физика жидких кристаллов [7] и др. (см., например, [8], [9], [10]).

Клеточный автомат полностью определяется своим начальным состоянием и правилом эволюционирования, которое может быть задано десятичным числом, называемым кодом Вольфрама, впервые введенным в работах [11], [12].

В компьютерных технологиях клеточные автоматы рассматриваются в связи с низкоуровневыми и архитектурными вопросами, такими как аппаратная генерация случайных чисел [13], создание новой вычислительной архитектуры, основанной на квантовых точках [14], вычисления на GPU [15].

Многие вопросы, связанные со свойствами инъективности, сюръективности, обратимости клеточных автоматов, приводят к рассмотрению линейной теории (см., например, [16], [17], [18]).

В данной работе мы вводим понятие линейности для клеточного автомата на одномерной конечной (или бесконечной) решетке со значениями в некотором конечном поле, что позволяет построить матричное представление для таких систем в виде трехдиагональных теплицевых матриц. Для решения данной задачи строится взаимно-однозначное соответствие между кодами Вольфрама и операторами Жегалкина. Следует отметить, что многочлены Жегалкина хорошо известны в дискретной математике и являются удобным средством представления функций булевой логики [19].

2. КЛЕТОЧНЫЕ АВТОМАТЫ И КОДЫ ВОЛЬФРАМА

В работе [11] был введен класс элементарных клеточных автоматов. Рассмотрим бесконечную последовательность из пронумерованных клеток

 $s^0\mathrm{<mo>=</mo>}(\dots \mathrm{,}{s}_{-1}^0\mathrm{,}{s}_0^0\mathrm{,}{s}_1^0\mathrm{,}\dots )\mathrm{,}{s}_i^0\in \mathrm{<mo>\{</mo>0,1<mo>\}</mo>,}i\in \mathbb{Z}\mathrm{,}$

которую будем называть начальным состоянием клеточного автомата (здесь верхний индекс <<0>> соответствует начальному состоянию клеточного автомата). Зададим правила преобразования состояния за один шаг (такт времени). Верхний индекс соответствует номеру шага (такта). Окрестностью i-й клетки на k-м шаге назовем множество $U_i^k\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{s}_{i-1}^k\mathrm{,}{s}_i^k\mathrm{,}{s}_{i+1}^k\mathrm{<mo\; stretchy="false">)</mo>},$ состоящее из самой клетки и двух ее ближайших соседей. Множество всех типов окрестностей имеет мощность 2³. Правилом клеточного автомата назовем трехместную булеву функцию

 $s_i^k\mathrm{<mo>=</mo>}f\left(s_{i-1}^{k-1}\mathrm{,}{s}_i^{k-1}\mathrm{,}{s}_{i+1}^{k-1}\right)\mathrm{,}$

определяющую состояние клетки s_i на k-м шаге в зависимости от состояния ее окрестности на (k – 1)-м шаге. Очевидно, что для задания такой функции нужно определить ее значения на 2³ = 8 наборах аргументов

 $(0,0,0),(0,0,1),...,(1,1,1)$. (1)

На векторном языке речь идет о задании восьмимерного бинарного вектора

 $r\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{r}_0\mathrm{,}\dots \mathrm{,}{r}_7\mathrm{<mo\; stretchy="false">)</mo>,}r\mathrm{<mo>:</mo>}{s}^{k-1}\mapsto s^k\mathrm{,}$

где аргументы r₀,…,r₇ соответствуют наборам (1), а в клетку $s_i^k$ записывается значение r_j, $j\mathrm{<mo>=</mo>}{s}_{i-1}^{k-1}\times 2^0+s_i^{k-1}\times 2^1+s_{i+1}^{k-1}\times 2^2$. Компонента r_j вектора r соответствует двоичному представлению числа j, записанного слева направо (рис. 1).

Рис. 1. Правило клеточного автомата с кодом Вольфрама W=254.

Определение 1. Элементарным клеточным автоматом назовем пару $⟨s_0\mathrm{,}r⟩$.

В данной статье мы ограничимся рассмотрением клеточных автоматов, для которых правило преобразования предыдущего состояния одно и то же на каждом такте. Этим свойством не обладают, например, клеточные автоматы, моделирующие поведение фотонных топологических изоляторов [20]. Множество правил для класса элементарных клеточных автоматов состоит из 2²³=256 элементов. Правило r можно закодировать десятичным числом, равным

$W\mathrm{<mo>=</mo>}{\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^7}{r}_j{2}^j\mathrm{,}$

которое мы будем называть кодом Вольфрама. Упорядочим правила клеточного автомата в соответствии с возрастанием кодов Вольфрама.

Правило клеточного автомата r = (0,1,1,1,1,1,1,1) с кодом Вольфрама W=254 изображено на рис. 1, где темные клетки — нули, а светлые — единицы. В каждой Т-образной фигуре, соответствующей определенному виду окрестности, верхний ряд клеток — $s_{i-1}^{k-1}$, $s_i^{k-1}$, $s_{i+1}^{k-1}$, нижняя клетка — $s_i^k$.

Действие клеточного автомата с кодом Вольфрама W=30 и с начальным состоянием s⁰= $\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{s}_0^0\mathrm{,}\dots \mathrm{,}{s}_{102}^0\mathrm{<mo\; stretchy="false">)</mo>}$, где $s_{52}^0\mathrm{<mo>=</mo>1}$, $s_i^0\mathrm{<mo>=</mo>0}$ при i ≠52 изображено на рис. 2.

Рис. 2. Первые 50 тактов клеточного автомата с кодом Вольфрама W=30 с одноточечным начальным состоянием.

Иногда в случае работы с конечной последовательностью

$s^0\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{s}_0^0\mathrm{,}{s}_1^0\mathrm{,}\dots \mathrm{,}{s}_{n-2}^0\mathrm{,}{s}_{n-1}^0\mathrm{<mo\; stretchy="false">)</mo>}$

ее замыкают, положив $U_0^0\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{s}_{n-1}^0\mathrm{,}{s}_0^0\mathrm{,}{s}_1^0\mathrm{<mo\; stretchy="false">)</mo>}$ и $U_{n-1}^0\mathrm{<mo>=</mo>}$$\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{s}_{n-2}^0\mathrm{,}{s}_{n-1}^0\mathrm{,}{s}_0^0\mathrm{<mo\; stretchy="false">)</mo>}$. Тем самым, избавившись от особенностей на границе, мы можем применять правила преобразования ко всем клеткам последовательности s⁰.

Для иллюстрации построения взаимно-однозначного соответствия между операторами Жегалкина и кодами Вольфрама рассмотрим наиболее простой нетривиальный пример одномерных клеточных автоматов с проколотой окрестностью $U_i^0\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{s}_{i-1}^0\mathrm{,}{s}_{i+1}^0\mathrm{<mo\; stretchy="false">)</mo>}$, состоящей только из правого и левого соседей клетки. В этом случае правила задаются четырехмерными бинарными векторами, а общее количество правил в этом случае составляет 2⁴ = 16. На рис. 3 представлены все правила клеточного автомата, для которого состояние клетки зависит от состояний только правого и левого соседей. При этом индекс i в записи правила w_i является кодом Вольфрама соответствующего клеточного автомата.

Рис. 3. Все правила клеточного автомата, для которого состояние клетки зависит только от состояний соседних клеток.

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

Примером клеточных автоматов с большими кодами Вольфрама являются трехцветные клеточные автоматы, рассмотренные в статье [20]. В данной работе на языке таких автоматов дается описание игры Руднера, являющейся упрощенной моделью топологического изолятора. Количество правил в рассматриваемом классе клеточных автоматов существенно превосходит 10¹⁰⁰. Рассмотрим правила 1–4, где

правило 1 = 871896424859609582029110705858

6077169685819630062952928588471702570724518

4955461514567350134642761960475397463135221;

правило 2 = 871896424859609582029110705858

6077169686562900693751685664642053530708374

8847009511688466704807114187492178155124653;

правило 3 = 871896424859609582029110705858

6077169686575887924022212825477616423051103

2271591445048493784239863824054082719415381;

правило 4 = 871896424859609582029110705858

6077169686575887949397362871618148203681507

8820525046538331816246773325439025350595533.

Эти правила включаются в определенной последовательности для клеток, в зависимости от четности, которая определяется шахматной раскраской, в соответствии с табл. 1.

Таблица 1. Четырехтактный клеточный автомат, моделирующий игру Руднера

Отметим, что предложенный клеточный автомат может быть реализован с помощью нарушенного полного внутреннего отражения в массиве, составленном из стеклянных призм [21], и описан на языке математических бильярдов (см., например, [22]).

Проиллюстрируем, как предложенная в [20] модель может быть использована при моделировании транспортного потока. Для этого реализуем транспортную сеть в виде трехцветного клеточного автомата, представленного на рис. 4, где светлые клетки изображают край проезжей части, на которой расположены машины. Клеточный автомат работает на основе периодического четырехтактного правила, описанного в табл. 1. Клетки машин перемещаются по проезжей части. Для того чтобы машины не исчезали, элемент транспортной сети превращен в двумерный тор с помощью стандартной процедуры подклеивания противоположных сторон.

Рис. 4. Элемент транспортной сети, смоделированной с помощью клеточного автомата.

На каждом такте наличие машины в клетке приводит к инкрементированию значения, приписанного данной клетке (начальное значение равно 0), а тепловая карта показывает, в каких клетках чаще всего находилась машина. Через 200 тактов работы клеточного автомата получим график распределения машин на элементе транспортной сети, изображенный на рис. 5.

Рис. 5. Результат моделирования загруженности транспортной сети.

Отметим, что данный трехцветный клеточный автомат на элементе транспортной сети ведет себя согласовано с моделью Нагеля—Шрекенберга (см., например, [6, 2.2.4]).

3. ОПЕРАТОРЫ ЖЕГАЛКИНА

Исследуя подобные системы, мы применяем алгебраические методы в теории клеточных автоматов, переходя при этом на эквивалентный язык операторов Жегалкина.

Определение 2. Многочленом Жегалкина d от n переменных над полем $\mathbb{Z}$/2$\mathbb{Z}$ назовем выражение

$d\mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{,}\dots \mathrm{,}{x}_n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\underset{I}{{\displaystyle \oplus }}{a}_I{x}^I\text{}\mathrm{,}$

где $I\mathrm{<mo>=</mo>}\mathrm{<mo\; stretchy="false">(</mo>}{i}_1\mathrm{,}\dots \mathrm{,}{i}_n\mathrm{<mo\; stretchy="false">)</mo>,}$ $i_k\in \mathbb{Z}\mathrm{<mo>/</mo>2}\mathbb{Z}$ — мультииндекс длины n, $x^I\mathrm{<mo>=</mo>}{x}_1^{i_1}\dots x_n^{i_n}\mathrm{,}$ $x_k\mathrm{,}{a}_I\in \mathbb{Z}\mathrm{<mo>/</mo>}2\mathbb{Z}$.

Количество мономов в многочлене Жегалкина равно 2ⁿ. Роль произведения здесь играет конъюнкция, а в качестве суммы выступает сложение по модулю 2.

Пример 1. В случае трех переменных многочлен Жегалкина имеет вид

$d\mathrm{<mo>=</mo>}{a}_0\oplus a_1{x}_1\oplus a_2{x}_2\oplus a_3{x}_1{x}_2\oplus \dots \oplus a_7{x}_1{x}_2{x}_3\mathrm{.}$ (2)

Пример 2. Выпишем все шестнадцать многочленов Жегалкина d(x₁,x₂) от двух переменных.

$d_0\mathrm{<mo>=</mo>0,}$

$d_1\mathrm{<mo>=</mo>1,}$

$d_2\mathrm{<mo>=</mo>}{x}_1\mathrm{,}$

$d_3\mathrm{<mo>=</mo>1}\oplus x_1\mathrm{,}$

$d_4\mathrm{<mo>=</mo>}{x}_2\mathrm{,}$

$d_5\mathrm{<mo>=</mo>1}\oplus x_2\mathrm{,}$

$d_6\mathrm{<mo>=</mo>}{x}_1\oplus x_2\mathrm{,}$

$d_7\mathrm{<mo>=</mo>1}\oplus x_1\oplus x_2\mathrm{,}$

$d_8\mathrm{<mo>=</mo>}{x}_1{x}_2\mathrm{,}$

$d_9\mathrm{<mo>=</mo>1}\oplus x_1{x}_2\mathrm{,}$

$d_{10}\mathrm{<mo>=</mo>}{x}_1\oplus x_1{x}_2\mathrm{,}$

$d_{11}\mathrm{<mo>=</mo>1}\oplus x_1\oplus x_1{x}_2\mathrm{,}$

$d_{12}\mathrm{<mo>=</mo>}{x}_2\oplus x_1{x}_2\mathrm{,}$

$d_{13}\mathrm{<mo>=</mo>1}\oplus x_2\oplus x_1{x}_2\mathrm{,}$

$d_{14}\mathrm{<mo>=</mo>}{x}_1\oplus x_2\oplus x_1{x}_2\mathrm{,}$

$d_{15}\mathrm{<mo>=</mo>1}\oplus x_1\oplus x_2\oplus x_1{x}_2\mathrm{.}$

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

Пусть $⟨V\mathrm{,}\oplus ⟩\mathrm{<mo>=</mo>}{\mathrm{<mo\; stretchy="false">(</mo>}\mathbb{Z}\mathrm{<mo>/</mo>}2\mathbb{Z}\mathrm{<mo\; stretchy="false">)</mo>}}^n$ — векторное пространство над полем $\mathbb{Z}$/2$\mathbb{Z}$.

Определение 3. Оператором Жегалкина с мультипликатором $d\mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{,}{x}_2\mathrm{,}{x}_3\mathrm{<mo\; stretchy="false">)</mo>}$ назовем отображение $g_d\mathrm{<mo>:</mo>}V\to V$ $\mathrm{<mo\; stretchy="false">(</mo>}{g}_d\mathrm{<mo\; stretchy="false">(</mo>}v\mathrm{<mo\; stretchy="false">)</mo>}\mathrm{<mo>=</mo>}w\mathrm{<mo\; stretchy="false">)</mo>,}$ действующее по правилу

$w_1\mathrm{<mo>=</mo>}d\mathrm{<mo\; stretchy="false">(</mo>}{v}_n\mathrm{,}{v}_1\mathrm{,}{v}_2\mathrm{<mo\; stretchy="false">)</mo>,}{w}_n\mathrm{<mo>=</mo>}d\mathrm{<mo\; stretchy="false">(</mo>}{v}_{n-1}\mathrm{,}{v}_n\mathrm{,}{v}_1\mathrm{<mo\; stretchy="false">)</mo>,}$

$w_{j+1}\mathrm{<mo>=</mo>}d\mathrm{<mo\; stretchy="false">(</mo>}{v}_j\mathrm{,}{v}_{j+1}\mathrm{,}{v}_{j+2}\mathrm{<mo\; stretchy="false">)</mo>,}j\mathrm{<mo>=</mo>}\mathrm{1,}\dots \mathrm{,}n-2.$

На рис. 6 проиллюстрированы действия операторов Жегалкина с мультипликаторами двух переменных. Нумерация рисунков совпадает с нумерацией из примера 2.

Рис. 6. Действия операторов Жегалкина с мультипликаторами двух переменных.

Определение 4. Оператор g_d назовем линейным, если

$g_d\mathrm{<mo\; stretchy="false">(</mo>}v\oplus v^{\prime }\mathrm{<mo\; stretchy="false">)</mo>}\mathrm{<mo>=</mo>}{g}_d\mathrm{<mo\; stretchy="false">(</mo>}v\mathrm{<mo\; stretchy="false">)</mo>}\oplus g_d\mathrm{<mo\; stretchy="false">(</mo>}{v}^{\prime }\mathrm{<mo\; stretchy="false">)</mo>}$

для всех $v\mathrm{,}{v}^{\prime }\in V.$

4. ОПИСАНИЕ АЛГОРИТМА

Для нахождения линейных операторов Жегалкина были разработаны и программно реализованы алгоритмы, описание которых приводится ниже. Программная реализация алгоритмов на языке Python доступна по адресу https://github.com/vrkulikov/cellural_automata.

Приведем краткое описание алгоритмов. Алгоритм 7 преобразует десятичное число в двоичный код. Алгоритм 8 по коду Вольфрама, т.е. десятичному номеру правила клеточного автомата, строит многочлен Жегалкина. Алгоритм 9 вычисляет значение многочлена Жегалкина на векторе x. Алгоритм 10 реализует перебор всех построенных многочленов Жегалкина на трехклеточных шаблонах и выбор тех из них, которые индуцируют линейный оператор Жегалкина согласно определению 4.

Рис. 7. Линейные операторы Жегалкина с мультипликаторами трех переменных.

Приведенные алгоритмы позволяют получить полный список линейных операторов Жегалкина с мультипликаторами трех переменных, а именно, справедлив следующий результат: оператор g_d является линейным в точности для следующего набора мультипликаторов

 $d\mathrm{<mo>=</mo>}\mathrm{0,}d\mathrm{<mo>=</mo>}{x}_1\mathrm{,}d\mathrm{<mo>=</mo>}{x}_2\mathrm{,}d\mathrm{<mo>=</mo>}{x}_3\mathrm{,}d\mathrm{<mo>=</mo>}{x}_1\oplus x_2\mathrm{,}$

 $d\mathrm{<mo>=</mo>}{x}_1\oplus x_3\mathrm{,}d\mathrm{<mo>=</mo>}{x}_2\oplus x_3\mathrm{,}d\mathrm{<mo>=</mo>}{x}_1\oplus x_2\oplus x_3\mathrm{.}$

Действия линейных операторов Жегалкина проиллюстрированы на рис. 11.

Легко видеть, что действие оператора g_d на вектор v $\in$V может быть представлено трехдиагональной теплицевой матрицей $T_{g_d}v\mathrm{<mo>=</mo>}w$

$T_{g_d}\mathrm{<mo>=</mo>}\left(\begin{array}{cccccccc}{a}_2& a_4& 0& 0& ⋮& 0& 0& a_1\\ a_1& a_2& a_4& 0& ⋮& 0& 0& 0\\ 0& a_1& a_2& a_4& ⋮& 0& 0& 0\\ 0& 0& a_1& a_2& \ddots & 0& 0& 0\\ 0& 0& 0& a_1& \ddots & 0& 0& 0\\ 0& 0& 0& 0& \ddots & 0& 0& 0\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮\\ 0& 0& 0& 0& ⋮& a_1& a_2& a_4\\ a_4& 0& 0& 0& ⋮& 0& a_1& a_2\end{array}\right)\mathrm{,}$

где a₁,a₂,a₄ — произвольные коэффициенты многочлена Жегалкина (2), а коэффициенты a₀ и a₃,a₅,a₆,a₇ и равны нулю.

Сопоставим теперь каждому коду Вольфрама многочлен Жегалкина. Пусть r = (r₀,r₁,…,r₇) — одно из 256 правил клеточного автомата. Рассмотрим многочлен Жегалкина d(x₁,x₂,x₃) с произвольными коэффициентами a = (a₀,a₁,…,a₇). Последовательно подставляя в d вместо переменных (x₁,x₂,x₃) наборы значений (0,0,0),(1,0,0),(0,1,0),…,(1,1,1), получим систему линейных уравнений

$Aa\mathrm{<mo>=</mo>}r$ (3)

с обратимой нижнетреугольной матрицей коэффициентов

$A\mathrm{<mo>=</mo>}\left(\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 0& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 0& 0& 0\\ 1& 1& 0& 0& 1& 1& 0& 0\\ 1& 0& 1& 0& 1& 0& 1& 0\\ 1& 1& 1& 1& 1& 1& 1& 1\end{array}\right)\mathrm{,}$

определитель которой равен 1. Решая систему (3) для заданных правых частей (r_j), j =0,…,7, найдем коэффициенты многочлена Жегалкина d.

5. ЗАКЛЮЧЕНИЕ

Для одномерных клеточных автоматов на эквивалентном языке операторов Жегалкина найдены линейные правила. Соответствие операторов Жегалкина и кодов Вольфрама может быть установлено в случае клеточных автоматов большей размерности, а также над конечным полем большего порядка. Для этого важно, чтобы сработал метод Гаусса решения системы линейных уравнений (3). Однако вопрос линейности в этих случае требует отдельного изучения.

БЛАГОДАРНОСТИ

Работа поддержана Красноярским математическим центром, финансируемым Минобрнауки РФ (Соглашение 075-02-2023-936).