Когда впервые были введены клеточные автоматы

Клеточные автоматы, основанные на графах Рамануджана, в задачах генерации псевдослучайных последовательностей Текст научной статьи по специальности «Математика»

В статье рассмотрены вопросы явного построения обобщенных клеточных автоматов для задач генерации псевдослучайных последовательностей. Обосновано теоретически и экспериментально подтверждено, что характеристики лавинного эффекта обобщенных клеточных автоматов , основанных на графах Рамануджана, близки к оптимальным. Предлагается генератор псевдослучайных последовательностей криптографического качества, основанный на таких клеточных автоматах

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Ключарёв П. Г.

Криптографические хэш-функции, основанные на обобщённых клеточных автоматах
Построение псевдослучайных функций на основе обобщённых клеточных автоматов
Метод построения криптографических хэш-функций на основе итераций обобщенного клеточного автомата

Детерминированные методы построения графов Рамануджана, предназначенных для применения в криптографических алгоритмах, основанных на обобщённых клеточных автоматах

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

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

Текст научной работы на тему «Клеточные автоматы, основанные на графах Рамануджана, в задачах генерации псевдослучайных последовательностей»

Электронное научно-техническое издание

НАУКА и ОБРАЗОВАНИЕ

Эя №ФС 77 — 30569. Государственная регистрация №0421100025.155Н 1994-0408_

Клеточные автоматы, основанные на графах Рамануджана, в задачах генерации псевдослучайных последовательностей

# 10, октябрь 2011 Ключарёв П. Г.

УДК 519.713.1; 519.177; 004.056.55

МГТУ им. Н.Э. Баумана pgkl@yandex.ru

В задачах вычислительной математики, криптографии, математического моделирования часто применяются псевдослучайные последовательности. Причем такие последовательности должны быть неотличимы от истинно случайных последовательностей по своим статистическим свойствам. Для выработки таких последовательностей используют специальные алгоритмы — генераторы псевдослучайных последовательностей (ГПСП). В работах [3, 4] предлагается использовать клеточные автоматы в качестве элементов таких генераторов. Этот подход является многообещающим, так как ГПСП, основанные на клеточных автоматах, имеют очень высокую скорость работы, как при программной, так и при аппаратной реализации. Однако остается открытым вопрос о явном детерминируемом построении обобщенных клеточных автоматов для таких генераторов. Решению этого вопроса и посвящена настоящая статья.

2. Обобщенные клеточные автоматы

Классические клеточные автоматы впервые были предложены Дж. Фон Нейманом в работе [20]. Они активно исследовались (см. работы [15, 21-24]), в том числе и в контексте выработки псевдослучайных последовательностей. Недавно, в работах [3, 4], было предложено и исследовано обобщение клеточных автоматов — неоднородные клеточные автоматы. Такие автоматы мы будем называть обобщенными.

Назовем обобщенным клеточным автоматом пару (О, /), где G = (V, Е) —

ориентированный регулярный мультиграф (V — множество вершин, а Е — мультимножество ребер) размера п, с каждой вершиной которого ассоциирована булева переменная,

причем все вершины пронумерованы числами 0. (п-1). Переменную, ассоциированную с г-ой вершиной, будем обозначать тг. Такие переменные мы будем называть ячейками. Для каждой вершины входящие в нее ребра пронумерованы числами 0. (к — 1) .

Функция I : |0;1> —> |0;1> — локальная функция связи.

Обобщенный клеточный автомат работает следующим образом: в начальный момент времени, каждая ячейка памяти тг, I = 0. (п — 1) имеет некоторое

начальное значение т1 (0). Далее автомат работает по шагам. На шаге с номером г с помощью локальной функции связи вычисляются новые значения переменных:

тг (г) = I(т,0,0) (г— 1),тф ,ц (г— 1). тф(г — 1)), (1)

где /(г,у) — номер вершины, из которой исходит ребро, входящее в вершину г и имеющее номер у.

Выходом обобщенного клеточного автомата на шаге с номером г являются значения первых г ячеек: т0(г),т1(г). тг—1(г) . Соответственно, последовательность

т0(г0Х ml(t0). тг-Г т0(*0 + 1), т1^0 + 1). тг-1(0 + 1), т0^0 + 2Х. будем

называть выходной последовательностью клеточного автомата.

Поскольку клеточный автомат, очевидно, является конечным автоматом, выходная последовательность является периодической.

Рассмотрим частный случай обобщенных клеточных автоматов — неориентированный обобщенный клеточный автомат.

Назовем неориентированным обобщенным клеточным автоматом обобщённый клеточный автомат (О, I), где граф О = (V, Е) такой, что для любого (и, у) Е Е существует (у, и) Е Е .

Граф неориентированного обобщённого клеточного автомата можно рассматривать как неориентированный мультиграф, если каждую пару ребер вида (и,у) Е Е и

(у,и) Е Е заменить на одно неориентированное ребро |и, у>. Такой автомат можно рассматривать как тройку (О, I, /), где О — неориентированный мультиграф, I- локальная функция связи, а / : Z п X Z а —> Z п — функция нумерации ребер, определенная выше.

Одними из важных криптографических характеристик клеточного автомата являются характеристики лавинного эффекта. Лавинный эффект представляет собой способ-

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

Рассмотрим два идентичных неориентированных обобщенных клеточных автомата

А1 и А2. Будем обозначать векторы их ячеек соответственно т(1) = (т(1). т^Д) и

т^2) = (т(2). тП)\). Начальное заполнение отличается только в одной ячейке. Для

определенности будем считать, что номер такой ячейки равен нулю (это не нарушает общности, поскольку перенумеровать переменные можно как угодно):

Будем рассматривать две характеристики лавинного эффекта: интегральную и пространственную.

Интегральной характеристикой лавинного эффекта [3] назовем зависимость доли несовпадающих ячеек у двух конечных автоматов от номера такта:

Пространственной характеристикой лавинного эффекта назовем зависимость отношения расстояния от вершины с номером 0 до самой дальней вершины, ячейка которой у двух автоматов не совпадает, к эксцентриситету вершины с номером 0:

tit) = -1- -max ((jt) ® m?\t ))-A(0, j)), (4)

где A(i, j) — длина минимального пути из вершины i в вершину j, а e(i) — эксцентриситет вершины i.

Как показано в работе [4], для того, чтобы вероятности нулей и единиц в выходной последовательности обобщенного клеточного автомата совпадали, необходимо и достаточно, чтобы локальная функция связи являлась равновесной. Мы будем полагать ее таковой.

Мы будем рассматривать усредненные по достаточно большому количеству начальных заполнений интегральную и пространственную характеристику лавинного эф-

Начиная с некоторого гп, выполняется и)(г) = шп и />(г) = цп при г > гп. Для обеспечений хороших статистических характеристик выходной последовательности необходимо, чтобы шп = 0.5, а цп = 1.

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

Диаметр Б регулярного графа размера п степени к имеет следующую нижнюю оценку (граница Мура [8, 13]):

Учитывая тот очевидный факт, что tn > D, по-видимому, следует выбрать граф с

диаметром, не слишком превосходящим границу Мура. Кроме того, для реализации лавинного эффекта граф должен быть таким, чтобы изменения одной ячейки клеточного автомата приводило к изменению все большего и большего числа ячеек с каждым шагом. Этим требованиям отвечают так называемые расширяющие графы (expander graphs).

3. Расширяющие графы

Теория расширяющих графов — сравнительно молодая область дискретной математики, нашедшая много приложений в математике и информатике. Этой теории посвящено большое количество литературы. Не задаваясь целью дать полный ее обзор, приведем здесь ссылки лишь на основные источники: [5, 7, 9, 10, 14, 17, 18]. Расширяющие графы применяются в ряде прикладных областей, в том числе, в задачах дерандомизации [18, 19] и для построения кодов, исправляющих ошибки [1]. Приведем здесь основные определения из этой теории.

Коэффициентом расширения неориентированного регулярного мультиграфа G = (V, E) называется величина:

где dS — множество ребер, каждое из которых инцидентно ровно одной вершине из множества S.

Расширяющим графом (expander graph) называется неориентированный регулярный мультиграф G, такой, что h(G) > с , где с — некоторая константа.

D > log*_1n + 1 — logk_1 к .

Коэффициент расширения графа связан с его спектральными свойствами. Так, рассмотрим отсортированный по убыванию спектр графа (то есть собственные числа его матрицы смежности):

Как известно из спектральной теории графов [5], Л1 = к, где к — степень графа О и справедливо следующее соотношение, называемое неравенством Чигера:

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

Согласно теореме Нили, нижняя граница для этой величины:

где В — диаметр графа.

К этой границе приближаются графы Рамануджана, то есть такие расширяющие графы, для которых справедливо неравенство

Для диаметра графов Рамануджана справедливо соотношение:

В = 21св к-1 п + О (1). (11)

Другими словами, диаметр графа Рамануджана всего в два раза больше границы Мура (5).

Учитывая близость графов Рамануджана к случайным графам по целому ряду свойств, можно ожидать, что для конечных автоматов, основанных на таких графах, 1п

будет близка к диаметру.

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

Одно из семейств графов Рамануджана — графы Любоцкого-Филипса-Сарнака (¿/’¿’-графы) [2, 11]. Одним из вариантов явных конструкций таких графов является конструкция, приведенная в книге [17]. Опишем ее здесь.

Выберем простые числар и q, для которых выполняются условия:

р = 1 (шоё4) q = 1 (шоё4)

Мы будем строить неориентированный мультиграф О = (У, Е) . Множеством

вершин мультиграфа V является проективная прямая над конечным полем К , другими

словами, V = К и . Мультимножество ребер Е состоит из всех пар (и,у), для которых выполняется:

((а0 + га1)и + (а2 + га3)) •

• ((—а2 + га3)г + (а0 — га1))—1, при (^ — iaъ)z ^^ — iax, z ^то

то, при — ia3)z = а0 —ia1, z ^то (13)

(а0 + га1)(—а2 + га3)—1, при a2 ^ia3, z = то

то, при a2 = ia3, z = то

для всех четверок а0, а1, а2, а3 Е Z, таких что:

• а0 — нечетное положительное;

• а1, а2, а3 — четные положительные;

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

В построенном таким образом графе могут быть кратные ребра (в том случае, когда (13) выполняется и для (и, у) и для (у, и) ) и петли. Степенью графа является количество решений уравнения (14), равное р +1.

В книге [17] доказано, что этот граф является графом Рамануджана.

4. Применение графов Рамануджана в клеточных автоматах

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

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

В качестве графа обобщенного клеточного автомата, мы будем использовать ЬРБ-граф, конструкция которого приведена в предыдущем разделе. У полученного таким образом клеточного автомата имеется q +1 ячейка, а его граф имеет степень р + 1. Числа р и

q являются простыми. На них накладываются приведенные в предыдущем разделе ограничения (12).

Были проведены вычислительные эксперименты по определению характеристик лавинного эффекта построенных таким образом клеточных автоматов, при параметрах

268 < q < 500 и р е , удовлетворяющих ограничениям (12). Во всех случаях, характеристики лавинного эффекта были близки к лучшим возможным теоретически: параметр 1п был близок к диаметру графа, шп = 0.5 и ¡1п = 1.

Были произведены исследования статистических свойств выходных последовательностей, при помощи тестов, рекомендованных МБТ [16], по стандартной методике. При р = 5 выходные последовательности автоматов проходили большинство тестов, в

том числе такие важные тесты, как универсальный тест Маурера [12]. При р = 13 последовательности проходили все тесты.

В качестве примера рассмотрим £Р£-граф размера 270 и степени 6 (q = 269,

р = 5), вид которого показан на Рис. 1, а характеристики лавинного эффекта соответствующего обобщенного клеточного автомата приведены на Рис. 2 и Рис. 3. У этого графа параметр Л2 = 4.4281, а диаметр равен 5. Этот диаметр близок к минимально возможному для регулярных графов такой степени и такого размера диаметру, равному, согласно границе Мура (5), четырем. Из графиков видно, что = 6, что близко к диаметру графа.

Рис. 1. LPS-граф размера 270, степени 6.

Рис. 2. Усредненная пространственная характеристика лавинного эффекта.

Рис. 3. Усредненная интегральная характеристика лавинного эффекта.

Использование одного автомата не обеспечивает непредсказуемости. Поэтому, мы, основываясь на схеме, предложенной в работе [4], будем использовать два обобщенных клеточных автомата A1 и A2 разного размера с различными локальными функциями связи: f1 и f2 . Выходные последовательности этих автоматов поразрядно складываются по модулю два (выбор именно сложения по модулю два связан с тем, что эта функция является корреляционно-иммунной). Функции f и f2, судя по результатам экспериментов, могут быть почти любыми равновесными, с нелинейностью, близкой к максимальной. Единственное условие, которое на них следует, по-видимому, наложить, это f ^ f © 1. Такая схема также существенно улучшает статистические свойства последовательности.

В качестве примера удачного сочетания параметров, для длины выхода r = 256, можно использовать размеры клеточных автоматов 270 и 282, как наиболее близкие к r. Для повышения эффективности реализации, степень графов должна быть наименьшей возможной, то есть равной 6.

Построенный таким образом ГПСП, при p = 5 генерирует случайные последовательности, которые успешно проходят все статистические тесты, рекомендованные NIST.

Предложен способ детерминированного построения обобщенных клеточных автоматов, имеющих близкие к оптимальным характеристики лавинного эффекта. Генераторы псевдослучайных последовательностей, основанные на таких клеточных автоматах, вырабатывают последовательности, имеющие статистические свойства криптографического качества, что подтверждается успешным прохождением тестов, рекомендованных NIST. Такие генераторы могут найти применения как в криптографии и стеганографии, так и в различных областях математического моделирования.

1. Жуков Д.А. Асимптотически хорошие коды с линейной сложностью кодирования и декодирования // Дискретная математика и её приложения. — 2009. — №5. — С. 23-25.

2. Маргулис Г.А. Явные теоретико-групповые конструкции комбинаторных схем и их применения в построении расширителей и концентраторов // Пробл. передачи информ. — 1988. — Vol. 24, №1. — С. 51-60.

3. Сухинин Б.М. Исследование характеристик лавинного эффекта в двоичных клеточных автоматах с равновесными функциями переходов // Наука и образование: электронное научно-техническое издание. -2010. — №8. — http://technomag.edu.ru/doc/159565.html.

4. Сухинин Б.М. Разработка генераторов псевдослучайных двоичных последовательностей на основе клеточных автоматов // Наука и образование: электронное научно-техническое издание. — 2010. — №9.

— http: //technomag. edu. ru/doc/159714. html.

5. Chung F.R.K. Regional conference series in mathematics,. Spectral graph theory. — Providence, R.I.: Published for the Conference Board of the mathematical sciences by the American Mathematical Society, 1997. — 207 p.

6. Cusick T.W., Stanica P. Cryptographic Boolean functions and applications. Academic Press, 2009.

7. Davidoff G.P., Sarnak P., Valette A. London Mathematical Society student texts. Elementary number theory, group theory, and Ramanujan graphs. -New York: Cambridge University Press, 2003. — 144 p.

8. Hoffman A., Singleton R. On Moore graphs with diameter 2 and 3, IBM Res // Develop. — 1960. — Vol. 4, P. 497-504.

9. Hoory S., Linial N., Wigderson A. Expander graphs and their applications // Bulletin-American Mathematical Society. — 2006. — Vol. 43, №4. — 439 p.

10. Krebs M., Shaheen A. Expander families and Cayley graphs. — Oxford ; New York: Oxford University Press, 2011.

11. Lubotzky A., Phillips R., Sarnak P. Ramanujan graphs // Combinatorica. -1988. — Vol. 8, №3. — P. 261-277.

12. Maurer U.M. A universal statistical test for random bit generators // Journal of cryptology. — 1992. — Vol. 5, №2. — P. 89-105.

13. Miller M., Siran J. Moore graphs and beyond: A survey of the degree/diameter problem // Electronic Journal of Combinatorics. — 2005. -Vol. 61, P. 1-63

14. Morgenstern M. Existence and explicit constructions of q+ 1 regular Ramanujan graphs for every prime power q // Journal of Combinatorial Theory, Series B. — 1994. — Vol. 62, №1. — P.44-62.

15. Packard N.H., Wolfram S. Two-dimensional cellular automata // Journal of Statistical Physics. — 1985. — Vol. 38, №5. — P.901-946.

16. Rukhin A., и др. A statistical test suite for random and pseudorandom number generators for cryptographic applications (SP 800-22). NIST, 2010.

17. Sarnak P. Cambridge tracts in mathematics. Some applications of modular forms. — Cambridge ; New York: Cambridge University Press, 1990. — 111 p.

18. Vadhan S. The unified theory of pseudorandomness // ACM SIGACT News.

— 2007. — Vol. 38, №3. — P. 39-54.

19. Vadhan S.P. Pseudorandomness // Foundations and Trends in Theoretical Computer Science. — 2010. — 200 p.

20. Von Neumann J. The general and logical theory of automata // Cerebral mechanisms in behavior. — 1951. — P. 1-41.

21. Wolfram S. Cryptography with cellular automata //: Springer, 1986. — P. 429-432.

22. Wolfram S. Statistical mechanics of cellular automata // Reviews of Modern Physics. — 1983. — Vol. 55, №3. — 601 p.

23. Wolfram S. Theory and applications of cellular automata // Advanced Series on Complex Systems, Singapore: World Scientific Publication, 1986. -1986. — Vol. 1.

24. Wolfram S. Universality and complexity in cellular automata // Physica D: Nonlinear Phenomena. — 1984. — Vol. 10, №1-2. — P. 1-35.

Анализ сложных систем с помощью моделей клеточных автоматов

Клеточный автомат — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Включает регулярную решётку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0. Решетка может быть любой размерности. Для каждой ячейки определено множество ячеек, называемых соседством. К примеру, соседство может быть определено как все ячейки на расстоянии не более 2 от текущей. Для работы клеточного автомата требуется задание начального состояния всех ячеек, и правил перехода ячеек из одного состояния в другое. На каждой итерации, используя правила перехода и состояния соседних ячеек, определяется новое состояние каждой ячейки. Обычно правила перехода одинаковы для всех ячеек и применяются сразу ко всей решётке.

Клеточный автомат является математическим объектом с дискретными пространством и временем. Каждое положение в пространстве представлено отдельной клеткой, а каждый момент времени — дискретным временным шагом или поколением. Состояние каждого пространственного локуса или клетки определяется очень простыми правилами взаимодействия. Эти правила предписывают изменения состояния каждой клетки в следующем такте времени в ответ на текущее состояние соседних клеток. Впервые, идея таких автоматов отмечена в работах Неймана в 1940-х годах, когда он работал над идеей саморепродуцирующихся машин. Вплоть до конца 60-х идея клеточных автоматов была забыта и лишь в 1970 Джон Конвей, математик Кембриджского университета, описал ныне широко известный двумерный клеточный автомат, названный «Игра жизни» ( » Game of life «) .

Игра разыгрывается на двумерном массиве во избежание краевого эффекта, свернутом в тор. Каждая клетка может быть в одном из двух состояний: клетка может быть «живой» (на экране — черной) или «м е ртвой» (на экране — белой). Если клетка в текущем моменте времени жива, то в следующем такте времени она

будет жива в лишь в том случае, если две или три из восьми соседних клеток живы в текущем такте

времени. В противном случае, клетка погибает. Если клетка мертва, то в следующем такте времени она оживает если и только если ровно 3 соседние клетки живы в текущем такте времени. В противном случае клетка остается мертвой. Если в качестве начального состояния установить случайное распределение живых имертвых клеток, запустить модель и проследить за ее эволюцией, то можно увидеть следующее. Часть структур стабилизируются и не изменяются во времени (рис.1), часть претерпевают циклические изменения (рис .2), и, наконец, некоторые развиваются, не повторяясь, практически неограниченное время (рис.3). Эти мод усы поведения структур в клеточном автомате соответствуют в дифференциальных уравнениях фиксированной точке, предельному циклу и хаосу. Таким образом, клеточные автоматы представляют альтернативный дифференциальным уравнениям путь анализа поведения сложных систем. Поскольку пространственная подразделенность является имманентным свойством клеточных автоматов, то они сильны именно там, где дифференциальные уравнения малоэффективны или неприменимы. Нет другого способа узнать эволюцию начальной конфигурации в Игре жизнь, чем реализовать игру.

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

Такие свойства или явления, которые не были явно заданы изначально, но возникающие в результате процессов взаимодействия исходных составляющих, называются эмерджентными (дословно, возникающими). Эти свойства создаются и поддерживаются процессами внутри среды. Как только процессы исчезают – свойства также исчезают, как исчезает жизнь если разобрать организм на составляющие, а потом механически попытаться собрать воедино.

Эмерджентные свойства – неотъемлемая особенность сложных систем.

Клеточные автоматы Стивена Вольфрама

Вольфрам провел эксперименты с самым простым вариантом игры жизнь, в котором среда представляет собой длинную замкнутую ленту шириной в одну клетку. Им двигала идея, что если нельзя понять, что происходит в этом самом простом клеточном автомате, то о более сложных системах и нечего думать.
Правила просты. Клетка может быть живой либо мертвой в зависимости от своего прежнего состояния и состояния двух её соседей. Итого, последующее состояние клетки определяется тремя параметрами. Из возможных состояний 3 ячеек можно составить лишь 8 возможных комбинаций.

Каждая комбинация может переводить клетку в одно из 2 возможных состояний (вкл. и выкл.) Итого получается небольшое конечное число возможных правил: 256 (2 8 ).
На каждом правиле Вольфрам провел серию экспериментов с различными начальными данными и в результате выделил 4 класса правил:

1) Почти все начальные конфигурации устанавливаются в один и тот же финальный паттерн

2) Почти все начальные конфигурации устанавливаются в один и тот же финальный паттерн или циркулируют между несколькими финальными паттернами

3) Большинство начальных конфигураций создают выглядящее случайным поведение, а также порождают треугольники или другие регулярные структуры

4) Последний класс объединяет порядок и случайность, порождая локализованные структуры, которые будучи простыми сами по себе, двигаются и взаимодействуют друг с другом очень сложным образом.

Класс 4 является самым интересным. Примером правила 4 класса может служить «правило 110» (рис.4)

Есть кое-что неожиданное в нём. Ученик Вольфрама Мэтью Кук доказал, что это правило является Тьюринг-полным. Иными словами – это простейшая известная на данный момент вычислительная модель.

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

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

Применение клеточных автоматов

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

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

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

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

Кроме того клеточные автоматы очень часто используют при решении задач алгоритмической разрешимости той или иной задачи.

Математическая составляющая клеточных автоматов

История возникновения клеточных автоматов

Понятие клеточных автоматов вводилось учёными неоднократно. Они могли непринципиально отличаться названием или заложенным в них механизмом функционирования. В теории динамических систем они присутствуют как один из разделов топологической динамики, в электротехнике их можно встретить как итеративные массивы, различные компьютерные игры построены на основе клеточного поля с различной геометрией клеток и правилами поведения.

Интересующие нас клеточные автоматы как инструмент математического моделирования ввёл в конце 1940 годов фон Нейман, следуя идее Улама. В качестве основной цели преследовалась необходимость обеспечения более реалистичных моделей поведения сложных и распределённых в двух- или трёхмерном пространстве систем. В его клеточных автоматах и объекты, характеризующиеся массивами пассивных данных, и объекты, описывающиеся как вычислительные устройства, собираются из одного типа структурных элементов и подчиняются одним и тем же законам.

При том, что фон Нейман был ведущим физиком и математиком, точные физические рассуждения в его работах по клеточным автоматам отсутствуют. Учёного в большей степени интересовало объяснение определенных аспектов биологии. И в самом деле, принципы межклеточного взаимодействия, которые им были предложены для реализации с помощью клеточного автомата, оказались схожими с открытыми в следующем десятилетии механизмами, реально наблюдаемыми в биологических системах.

В конце Второй мировой войны, когда фон Нейман участвовал в создании одного из первых электронных компьютеров, немецкий инженер Цузе прятался от нацистов в Австрии. Там у него возникло множество идей параллельной обработки, включая языки программирования и «вычисляющие пространства», то есть сами клеточные автоматы. Цузе особенно интересовался численными моделями в механике, поэтому интерес к физическим процессам на микроуровне играл основную роль в его работе.

Работа фон Неймана по самовоспроизводящимся автоматам была завершена и описана одним из конструкторов первого электронного компьютера Бёрксом, который сохранил активный интерес к этой области и на протяжении последующих лет. Его «Очерки по клеточным автоматам» являлись хорошим обобщением знаний того времени в данной области. Одновременно с работами Бёркса его коллега по Мичиганскому университету Голланц приступил к использованию клеточных автоматов для решения задач адаптации и оптимизации. Им был разработан программный имитатор универсальных клеточных автоматов общего назначения.

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

Игра английского математика Конуэя «Жизнь», основанная на принципах клеточного автомата, была представлена широкой общественности в 1970 году. Благодаря её популяризации с помощью ряда научных и научно-популярных изданий, в том числе в журнале Scientific American, она довольно продолжительное время пользовалась особым успехом и закрепила понятие «клеточный автомат» в научной терминологии исследователей.

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

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

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

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

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

• dsp
• История
• 2013-08-21
• 7 888

Клеточный автомат

Кле́точный автома́т — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Включает регулярную решётку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0. Решетка может быть любой размерности. Для каждой ячейки определено множество ячеек, называемых соседством. К примеру, соседство может быть определено как все ячейки на расстоянии не более 2 от текущей. Для работы клеточного автомата требуется задание начального состояния всех ячеек, и правил перехода ячеек из одного состояния в другое. На каждой итерации, используя правила перехода и состояния соседних ячеек, определяется новое состояние каждой ячейки. Обычно правила перехода одинаковы для всех ячеек и применяются сразу ко всей решётке.

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

История

Станислав Улам, работая в Лос-аламосской национальной лаборатории в 1940-е годы, изучал рост кристаллов, используя простую решёточную модель. В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота. Такая модель известна как кинематическая. Разработав эту модель, фон Нейман осознал сложность создания самовоспроизводящегося робота и, в частности, обеспечения необходимого «запаса частей», из которого должен строиться робот. Улам предложил фон Нейману использовать более абстрактную математическую модель, подобную той, что Улам использовал для изучения роста кристаллов. Таким образом возникла первая клеточно-автоматная система. Подобно решётке Улама, клеточный автомат фон Неймана двухмерный, а самовоспроизводящийся робот описан алгоритмически. Результатом явился универсальный конструктор, работающий «внутри» клеточного автомата с окрестностью, включающей непосредственно прилегающие ячейки, и имеющего 29 состояний. Фон Нейман доказал, что для такой модели существует паттерн, который будет бесконечно копировать самого себя.

Также в 1940-е годы, Норберт Винер и Артуро Розенблют разработали клеточно-автоматную модель возбудимой среды. Целью было математическое описание распространения импульса в сердечных нервных узлах. Их оригинальная работа продолжает цитироваться в современных исследованиях по аритмии и возбудимым средам.

В 1960-е годы клеточные автоматы изучались как частный тип динамических систем, и впервые была установлена их связь с областью символьной динамики. В 1969 году Г.А.Хедланд провёл обзор результатов, полученных в этом направлении. Наиболее значимым результатом явилось описание набора правил клеточного автомата как множества непрерывных эндоморфизмов в сдвиговом пространстве.

В 1970-е получила известность двухмерная клеточно-автоматная модель с двумя состояниями, известная как игра «Жизнь». Изобретенная Джоном Конвеем и популяризованная Мартином Гарднером, она использует следующие правила: если клетка имеет двух «живых» соседей, она остаётся в прежнем состоянии. Если клетка имеет трёх «живых» соседей, она переходит в «живое» состояние. В остальных случаях клетка «умирает». Несмотря на свою простоту, система проявляет огромное разнообразие поведения, колеблясь между очевидным хаосом и порядком. Одним из феноменов игры «Жизнь» являются глайдеры — сочетания клеток, движущиеся по сетке как единое целое. Возможно построить автомат, в котором глайдеры будут выполнять некоторые вычисления, и впоследствии было показано, что игра «Жизнь» может эмулировать универсальную машину Тьюринга.

В 1969 году немецкий инженер Конрад Цузе опубликовал книгу «Вычислимый космос», где выдвинул предположение, что физические законы дискретны по своей природе, и что вся Вселенная является гигантским клеточным автоматом. Это была первая книга из области, называемой сейчас цифровой физикой.

В 1983 Стивен Вольфрам опубликовал первую из серии статей, исследующих очень простой, но до сих пор неизученный класс клеточных автоматов, называемых элементарными клеточными автоматами. Неожиданная сложность поведения этих простых автоматов привела Вольфрама к предположению, что сложность естественных систем обусловлена сходным механизмом. Кроме того, в течение этого периода Вольфрам формулирует концепцию истинной случайности и вычислительной неприводимости, и выдвигает предположение, что Правило 110 (англ.) русск. может быть универсальным — факт, доказанный в 1990 году ассистентом Вольфрама Мэтью Куком.

В 2002 году Вольфрам публикует 1280-страничный текст «Новый тип науки» (A New Kind of Science), где широко аргументирует, что достижения в области клеточных автоматов не являются изолированными, но весьма устойчивы и имеют большое значение для всех областей науки.

11-го ноября 2002 года Пауль Чепмен (Paul Chapman) построил образец Жизни, который является РММ (Регистровой Машиной Минского). Фактически РММ эквивалентна машине Тьюринга. Первая версия образца была большой (268,096 живых ячеек на площади 4,558 x 21,469 клеток) и медленной (20 поколений/сек при использовании Life32 Иогана Бонтеса (Johan Bontes) на 400 MHz AMD K6-II). Таким образом, в игре Жизнь можно выполнить любой алгоритм, который можно реализовать на современном компьютере.

Математическое определение

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

Число всех возможных правил перехода определяется числом состояний и количеством соседей n и составляет

Узор на поверхности раковины Conus textile формируется по механизму клеточного автомата

Некоторые живые организмы проявляют свойства клеточных автоматов. Раскраска некоторых морских ракушек, таких как Conus или Cymbiola, генерируется естественным клеточным автоматом. Их пигментные клетки располагаются тонкой полоской вдоль края раковины. Секреция пигмента каждой клетки зависит от активирующей и ингибиторной активности соседних клеток. В процессе роста полоса клеток оставляет цветной узор на поверхности ракушки.

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

Нейронные сети также могут быть использованы как клеточные автоматы. Сложный движущийся узор на коже головоногих является отражением паттернов активирования в мозгу животных.

Реакция Белоусова-Жаботинского представляет собой пространственно-временной химический осциллятор, который может быть смоделирован клеточным автоматом. В 1950-х годах А.М.Жаботинский, продолжая работу Б.П.Белоусова, обнаружил, что тонкий однородный слой смеси определённых химических веществ способен образовывать движущиеся геометрические узоры, такие как концентрические круги и спирали.

См. также

• Жизнь (игра)
• Автомат фон Неймана
• Муравей Лэнгтона
• Метод подвижных клеточных автоматов
• Задача синхронизации стрелков

Примечания

1. ↑ A.G.Hoekstra, J.Kroc, P.Sloot. Simulating complex systems by cellular automata. Springer, 2010. ISBN 978-3-642-12202-6

Ссылки

• Т. Тоффоли, Н. Марголус, Машины клеточных автоматов, М.: «Мир», 1991. ISBN 5-03-001619-8
• Life Universal Computer
• S. Wolfram «New Kind of Science»
• англоязычный сайт с массой информации по КА, обновляется Tim Tyler см. usenet:comp.theory.cell-automata
• Usenet конференция по КА
• КА в математической энциклопедии WolframMathWorld
• Статья на научно-популярном портале GeniusLand
• В.К. ВанагИсследование пространственно распределённых динамических систем методами вероятностного клеточного автомата (рус.) // Успехи физических наук. Обзоры актуальных проблем. : журнал. — май 1999. — Т. 169. — № 5. — С. 481-505.

• Викифицировать статью.
• Проставив сноски, внести более точные указания на источники.