Аннотация:В работе Екатерины Шестовских исследуется задача сравнения сложности решения некоторых простейших арифметических задач с помощью стандартных клеточных автоматов и клеточных автоматов с локаторами. Клеточные автоматы с локаторами отличаются от обычных клеточных автоматов тем, что автоматы могут посылать в эфир некоторые сигналы и получать из эфира суммарный сигнал. Решаются следующие задачи:
1) определение четности числа единиц в начальной конфигурации;
2) перевод числа представленного в виде массива единиц в двоичную запись;
3) сложение чисел, представленных единицами и минус единицами в начальной конфигурации;
4) умножение числа, представленного массивом единиц, на 2.
Для каждой задачи предполагалось получить решение клеточными автоматами и клеточными автоматами с локаторами. Также предполагалось получить нижние оценки для обоих случаев, которые доказывали оптимальность по порядку предлагаемых решений. Тем самым предполагалось доказать 16 утверждений: для каждой задачи верхние и нижние оценки для двух типов клеточных автоматов. На данный момент в работе имеется доказательство 4 утверждений.