Почти полиномиальные возвратные последовательности с алгоритмически неразрешимыми проблемамистатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 24 июля 2024 г.
Аннотация:Рассмотрены возвратные последовательности над множеством целых чисел, у которых в качестве порождающих функций используются произвольные суперпозиции полиномиальных функций и функций, близких к полиномиальным, --- почти полиномиальные возвратные последовательности. Выделена серия функций вида bj_i(x). Каждая из этих функций вместе с полиномиальными функциями позволяет строить порождающие функции, которые дают возможность определять почти полиномиальные возвратные последовательности, моделирующие вычисления на машинах Минского. На основе этого результата сформулированы алгоритмически неразрешимые проблемы, связанные с данными почти полиномиальными возвратными последовательностями. Получены следствия, которые существенно расширяют круг функций, способных порождать возвратные последовательности с алгоритмически неразрешимыми проблемами.