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

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

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

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

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

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

Литература

[1] Бюхи Д. Р. Слабая арифметика второго порядка и конечные автоматы // Кибернет. сборник. Вып. 8. — М.: Мир, 1964. — С. 42–77.

[2] Катериночкина Н. Н. Об эквивалентности некоторых вычислительных устройств // Кибернетика. — 1970. — № 5. — С. 27–31.

[3] Кобринский Н. Е., Трахтенброт Б. А. Введение в теорию конечных автоматов. — М.: Физматлит, 1962. — 404 с.

[4] Курода С. И. Классы языков и линейно ограниченные автоматы // Кибернет. сборник. Вып. 9. — М.: Мир, 1972. — С. 36–51.

[5] Лялин И. В. О решении автоматных уравнений // Дискрет. математика. — 2004. — Т. 16, № 2. — С. 104–116.

[6] Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, 1986. — 392 с.

[7] Марченков С. С. О сложности класса $\mathcal{E}^2$ Гжегорчика // Дискрет. математика. — 2010. — Т. 22, № 1. — С. 5–16.

[8] Мейер А. Р. Слабая сингулярная теория второго порядка функции следования не элементарно рекурсивна // Кибернет. сборник. Вып. 12. — М.: Мир, 1975. — С. 62–77.

[9] Минский М. Вычисления и автоматы. — М.: Мир, 1971. — 364 с.

[10] Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы. Поведение и синтез. — М.: Наука, 1970. — 400 с.