|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
О полиномиально-модульных возвратных последовательностяхстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК- Автор: Марченков С.С.
- Журнал: Дискретная математика
- Том: 34
- Номер: 2
- Год издания: 2022
- Издательство: ФГБУ "Издательство "Наука"
- Местоположение издательства: Москва
- Первая страница: 43
- Последняя страница: 49
- DOI: 10.4213/dm1667
- Аннотация: Рассмотрены возвратные последовательности над множеством целых чисел, у которых в качестве порождающих функций используются произвольные суперпозиции полиномиальных функций и функции |x|, -полиномиально-модульные возвратные последовательности. Показано, как вычисления на трехленточных машинах Минского можно промоделировать с помощью полиномиально-модульных возвратных последовательностей. На основе этого результата сформулированы алгоритмически неразрешимые проблемы, связанные с полиномиально-модульными возвратными последовательностями. Рассмотрены также возвратные последовательности, вкоторых в качестве порождающих функций используются функции, образованные некоторыми суперпозициями полиномиальных функций и функции [\sqrt{x}]. Для множества таких возвратных последовательностей указана алгоритмически неразрешимая проблема.
- Добавил в систему: Марченков Сергей Серафимович