EN|RU

Том 19, номер 4, 2012 г., Стр. 86-98

УДК 519.7
Марченков С. С. 
О решениях систем функциональных уравнений автоматного типа

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

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

Марченков Сергей Серафимович 1
1. Московский гос. университет им. М. В. Ломоносова,
Ленинские горы, 119991 Москва, Россия
е-mail: ssmarchen@yandex.ru

Статья поступила 4 октября 2011 г.

 © Институт математики им. С. Л. Соболева, 2015