ИСТИНА

В работе исследуется возможность вычисления малыми коллективами автоматов арифметических функций на целочисленной прямой. Будем говорить, что коллектив автоматов (W1, W2) находится в а-расстановке (а>=0), если автомат W2 находится на а делений правее автомата W1. Будем говорить, что коллектив автоматов (W1, W2) вычисляет целочисленную функцию f(x), если для любого целого неотрицательного х, стартуя из х-расстановки, коллектив останавливается в f(x)-расстановке. В зависимости от ограничений на подвижность автоматов коллектива определяются сильная вычислимость функций коллективом автоматов, слабая вычислимость и просто вычислимость. В работе полностью описан класс целочисленных функций, вычислимых коллективами из двух автоматов. Этот класс представляет собой композиции «периодических» функций и функций вида f(x)=х+с. Показано, что классы всех функций, вычислимых коллективами из двух автоматов, слабо вычислимых коллективами из двух автоматов и сильно вычислимых коллективами из двух автоматов – совпадают. Также показано, что класс функций, вычислимых коллективами из трех автоматов – значительно шире.