|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Почти полиномиальные возвратные последовательности с алгоритмически неразрешимыми проблемамистатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКСтатья опубликована в журнале из списка Web of Science и/или Scopus
- Автор: Марченков С.С.
- Журнал: Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика
- Номер: 3
- Год издания: 2023
- Издательство: Изд-во Моск. ун-та
- Местоположение издательства: М.
- Первая страница: 49
- Последняя страница: 55
- DOI: 10.55959/MSU/0137-0782-15-2023-47-3-49-55
- Аннотация: Рассмотрены возвратные последовательности над множеством целых чисел, у которых в качестве порождающих функций используются произвольные суперпозиции полиномиальных функций и функций, близких к полиномиальным, --- почти полиномиальные возвратные последовательности. Выделена серия функций вида bj_i(x). Каждая из этих функций вместе с полиномиальными функциями позволяет строить порождающие функции, которые дают возможность определять почти полиномиальные возвратные последовательности, моделирующие вычисления на машинах Минского. На основе этого результата сформулированы алгоритмически неразрешимые проблемы, связанные с данными почти полиномиальными возвратными последовательностями. Получены следствия, которые существенно расширяют круг функций, способных порождать возвратные последовательности с алгоритмически неразрешимыми проблемами.
- Добавил в систему: Марченков Сергей Серафимович