Интеллектуальные системы.
Теория и приложения

Аннотация

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

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