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