Сложность задачи адресации идемпотентными клеточными автоматами с локаторами

Аннотация

Исследуется сложность задачи адресации для одномерных идемпотентных клеточных автоматов с локаторами. На бесконечной в обе стороны ленте рассматривается отрезок из \(N+1\) размеченной клетки, вне которого все клетки находятся в состоянии покоя. Требуется по переданному адресу выделить клетку с этим адресом. Установлен порядок сложности: при константном числе состояний задача адресации разрешима за \(O(\log N)\) шагов.

Ключевые слова: клеточные автоматы с локаторами, задача адресации, идемпотентность, сложность.

BibTeX
@article{IS-Bukharina2026,
  author  = {Бухарина, Дарья Анатольевна},
  title   = {{Сложность задачи адресации идемпотентными клеточными автоматами с локаторами}},
  journal = {Интеллектуальные системы. Теория и приложения},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {70--73},
}
AMSBIB
\RBibitem{IS-Bukharina2026}
\by Д.\,А.~Бухарина
\paper Сложность задачи адресации идемпотентными клеточными автоматами с локаторами
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 70--73
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover