Эта публикация цитируется в 1 статье

О вычислимости функций коллективами из двух автоматов

Н. Ю. Волков, В. В. Ушакова

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: В работе исследуется возможность вычисления малыми коллективами автоматов арифметических функций на целочисленной прямой. Будем говорить, что коллектив автоматов $(W_1,W_2)$ находится в $a$-расстановке $(a \geqslant 0)$, если автомат $W_2$ находится на $a$-делений правее автомата $W_1$. Будем говорить, что коллектив автоматов $(W_1,W_2)$ вычисляет целочисленную функцию $f(x)$, если для любого целого неотрицательного $x$, стартуя из $x$-расстановки, коллектив останавливается в $f(x)$-расстановке. В зависимости от ограничений на подвижность автоматов коллектива определяются сильная вычислимость функций коллективом автоматов, слабая вычислимость и просто вычислимость. В работе полностью описан класс целочисленных функций, вычислимых коллективами из двух автоматов. Этот класс представляет собой композиции «периодических» функций и функций вида $f(x)=x + c$. Показано, что классы всех функций, вычислимых коллективами из двух автоматов, слабо вычислимых коллективами из двух автоматов и сильно вычислимых коллективами из двух автоматов — совпадают. Также показано, что класс функций, вычислимых коллективами из трех автоматов — значительно шире.

Ключевые слова: коллектив автоматов, лабиринт, вычислимость, целочисленные функции.