О линейных клеточных автоматах

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

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

Полный текст

Доступ закрыт

Об авторах

В. Р. Куликов

Сибирский федеральный университет

Автор, ответственный за переписку.
Email: v.r.kulikov@mail.ru
Россия, Красноярск

А. А. Кытманов

МИРЭА — Российский технологический университет

Email: aakytm@gmail.com
Россия, Москва

А. О. Порошин

Сибирский федеральный университет

Email: poroshin.012332@gmail.com
Россия, Красноярск

И. В. Тимофеев

Институт физики им. Л.В. Киренского СО РАН, обособленное подразделение ФИЦ КНЦ СО РАН; Сибирский федеральный университет

Email: tiv@iph.krasn.ru
Россия, Красноярск; Красноярск

Д. П. Федченко

Институт физики им. Л.В. Киренского СО РАН, обособленное подразделение ФИЦ КНЦ СО РАН; Сибирский федеральный университет

Email: fdp@iph.krasn.ru
Россия, Красноярск; Красноярск

Список литературы

  1. Neumann J. Theory of self-reproducing automata //Edited by Arthur W. Burks. 1966.
  2. Цетлин М.Л. Некоторые задачи о поведении конечных автоматов //Доклады Академии наук. Российская академия наук, 1961. Т. 139. № 4. С. 830–833.
  3. Conway J. et al. The game of life //Scientific American. 1970. Т. 223. № 4. С. 4.
  4. Batty M. Cities as Complex Systems: Scaling, Interaction, Networks, Dynamics and Urban Morphologies. 2009.
  5. Ghosh P. et al. Application of Cellular automata and Markov-chain model in geospatial environmental modeling-A review //Remote Sensing Applications: Society and Environment. — 2017. Т. 5. С. 64–77.
  6. Гасников А. и др. (ред.). Введение в математическое моделирование транспортных потоков. Litres, 2022.
  7. Fronczak P. et al. Cellular automata approach to modeling self-organized periodic patterns in nanoparticle-doped liquid crystals //Physical Review E. 2022. Т. 106. № 4. С. 44705.
  8. Janssens K.G.F. An introductory review of cellular automata modeling of moving grain boundaries in polycrystalline materials //Mathematics and Computers in Simulation. 2010. Т. 80. № 7. С. 1361–1381.
  9. Lemont B. Kier and Paul G. Seybold. Cellular Automata Modeling of Complex Biochemical Systems // Encyclopedia of Complexity and Systems Science, 2015.
  10. Kozhoridze G., Dor E.B., Sternberg M. Assessing the Dynamics of Plant Species Invasion in Eastern-Mediterranean Coastal Dunes Using Cellular Automata Modeling and Satellite Time-Series Analyses //Remote Sensing. 2022 Т. 14. № 4. С. 1014.
  11. Wolfram S. Statistical mechanics of cellular automata //Reviews of modern physics. – 1983. Т. 55. № 3. С. 601.
  12. Wolfram S. et al. A new kind of science. Champaign: Wolfram media, 2002. Т. 5. С. 130.
  13. Tomassini M., Sipper M., Perrenoud M. On the generation of high-quality random numbers by two-dimensional cellular automata // IEEE Transactions on computers. 2000. Т. 49. № 10. С. 1146–1151.
  14. Walus K. et al. RAM design using quantum-dot cellular automata // NanoTechnology Conference. 2003. Т. 2. С. 160–163.
  15. Cagigas-Muniz D. et al. Efficient simulation execution of cellular automata on GPU // Simulation Modelling Practice and Theory. 2022. Т. 118. С. 102519.
  16. Sato T. Decidability for some problems of linear cellular automata over finite commutative rings // Information Processing Letters. 1993. Т. 46. № 3. С. 151–155.
  17. Martin A. et al. Reversibility of linear cellular automata // Applied Mathematics and Computation. 2011. Т. 217. № 21. С. 8360-8366.
  18. Martin del Rey A., Casado Vara R., Hernández Serrano D. Reversibility of symmetric linear cellular automata with radius r = 3 //Mathematics. 2019. Т. 7. № 9. С. 816.
  19. Жегалкин И.И. Арифметизация символической логики //Математический сборник. 1928. Т. 35. № 3–4. С. 311–377.
  20. Федченко Д.П., Новиков В.В., Тимофеев И.В. Фотонные топологические изоляторы типа Руднера на языке трехцветных клеточных автоматов // Ученые записки физического факультета МГУ. 2021. № 5. С. 2150302.
  21. Fedchenko D.P., Kim P.N., Timofeev I.V. Photonic Topological Insulator Based on Frustrated Total Internal Reflection in Array of Coupled Prism Resonators //Symmetry. 2022. Т. 14. № 12. С. 2673.
  22. Гальперин Г. А., Земляков А. Н. Математические бильярды: Бильярдные задачи и смежные вопросы математики и механики. Наука. Гл. ред. физ.-мат. лит., 1990.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать
2. Рис. 1. Правило клеточного автомата с кодом Вольфрама W=254.

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

Скачать (244KB)
Метаданные
4. Рис. 3. Все правила клеточного автомата, для которого состояние клетки зависит только от состояний соседних клеток.

Скачать (551KB)
Метаданные
5. Рис. 4. Элемент транспортной сети, смоделированной с помощью клеточного автомата.

Скачать (198KB)
Метаданные
6. Рис. 5. Результат моделирования загруженности транспортной сети.

Скачать (184KB)
Метаданные
7. Рис. 6. Действия операторов Жегалкина с мультипликаторами двух переменных.

Скачать (613KB)
Метаданные
8. Рис. 7. Линейные операторы Жегалкина с мультипликаторами трех переменных.

Скачать (266KB)
Метаданные
9. Рис. 8. Алгоритм 1

Скачать (154KB)
Метаданные
10. Рис. 9. Алгоритм 2

Скачать (267KB)
Метаданные
11. Рис. 10. Алгоритм 3

Скачать (219KB)
Метаданные
12. Рис. 11. Алгоритм 4

Скачать (368KB)
Метаданные

© Российская академия наук, 2024

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».