Почти полиномиальные возвратные последовательности с алгоритмически неразрешимыми проблемами

Поступила: 09.01.2023

Принята к публикации: 05.03.2023

Дата публикации в журнале: 20.09.2023

Ключевые слова: почти полиномиальные возвратные последовательности

DOI: 10.55959/MSU/0137–0782–15–2023–47–3–49–55

Для цитирования статьи

Марченков С.С. Почти полиномиальные возвратные последовательности с алгоритмически неразрешимыми проблемами // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2023. № 3. С. 49-55 https://doi.org/10.55959/MSU/0137–0782–15–2023–47–3–49–55.

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция-Некоммерчески») 4.0 Всемирная

Марченков С.С. (Московский государственный университет им. М.В. Ломоносова (МГУ))

Аннотация

Рассмотрены возвратные последовательности над множеством целых чисел, у которых в качестве порождающих функций используются произвольные суперпозиции полиномиальных функций и функций, близких к полиномиальным, - почти полиномиальные возвратные последовательности. Выделена серия функций вида b · ji(x). Каждая из этих функций вместе с полиномиальными функциями позволяет строить порождающие функции, которые дают возможность определять почти полиномиальные возвратные последовательности, моделирующие вычисления на машинах Минского. На основе этого результата сформулированы алгоритмически неразрешимые проблемы, связанные с данными почти полиномиальными возвратными последовательностями. Получены следствия, которые существенно расширяют круг функций, способных порождать возвратные последовательности с алгоритмически неразрешимыми проблемами.