|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Регистровые машины со счетчиками: устранение неравенств и невычислимые функциидипломная работа (Магистр)
- Научный руководитель: Марченков Сергей Серафимович
- Автор: Савицкий Игорь Владимирович
- Тип: Магистр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2018
- Аннотация: Рассматриваются вопросы вычисления функций на регистровых машинах со счетчиками (RC-машины). Доказано, что без потери вычислительных возможностей в определении RC-машины можно обойтись только отношениями равенства/неравенства между регистрами и счетчиками. Установлено, что на RC-машинах можно строго вычислять нерекурсивные функции, характеризуемые классом Дельта_2 иерархии Клини-Мостовского. Определено точное положение в иерархии Клини-Мостовского (класс Сигма_3)трех алгоритмических проблем, относящихся к вычислению рекурсивных функций на RC-машинах.
- Добавил в систему: Марченков Сергей Серафимович