О решениях систем функциональных уравнений автоматного типа

Рассматриваются функциональные уравнения автоматного типа – уравнения, которые наряду с предметной переменной для натуральных чисел содержат одноместные функциональные переменные для бесконечных двоичных последовательностей. Строится алгоритм, решающий проблему выполнимости для конечных систем функциональных уравнений, содержащих только функции $1$ и $t+1$. С использованием линейных однородных структур устанавливается нижняя оценка временно́й сложности для разрешающих алгоритмов подобного вида. Доказывается алгоритмическая неразрешимость проблемы выполнимости для систем функциональных уравнений, содержащих дополнительно функции $2t,3t$ и $5t$. Табл. 1, библиогр. 10.