Сложность вычислений на регистровых машинах со счётчиками Савицкий Игорь Владимирович

Короткий опис

Савицкий, Игорь Владимирович.
Сложность вычислений на регистровых машинах со счётчиками : диссертация ... кандидата физико-математических наук : 01.01.09 / Савицкий Игорь Владимирович; [Место защиты: ФГАОУ ВО «Казанский (Приволжский) федеральный университет»]. - Москва, 2021. - 144 с.
Оглавление диссертациикандидат наук Савицкий Игорь Владимирович
Введение
Краткий обзор результатов по теме диссертации
Общая характеристика работы
Основные понятия
Формулировка основных результатов
Глава 1. Вычисления на регистровых машинах со счётчиками
§1.1. Основные понятия
§1.2. Вычисление простых арифметических функций
§1.3. Моделирование ЯС-машин с константами
§1.4. Стековые регистровые машины
§1.5. Универсальность ЯС-машин
§ 1.6. Класс функций, строго вычислимых на ЯС-машинах
Глава 2. Алгоритмические проблемы, связанные с ИС-машинами
§2.1. ЯС-машины без ограничений на переходы
§ 2.2. Нумерации и сводимость
§ 2.3. Проблема абсолютной эквивалентности
§ 2.4. Слабая проблема эквивалентности
§ 2.5. Сильная проблема эквивалентности и проблема строгой вычислимости
§ 2.6. Проблемы, связанные с определением рекурсивности вычисляемой КС-машиной функции
Глава 3. Упрощение ИС-машин и их арифметизация
§3.1. Вычисления с ограничением на число программ или счётчиков
§3.2. ЯС-машины без неравенств
§3.3. ЯС-машины с ограниченным числом сравнений
§3.4. Арифметизация ЯС-машин
Глава 4. Счётчиковые машины с сумматором
§4.1. Определение счётчиковой машины с сумматором
§ 4.2. Вычисление простых арифметических функций
§ 4.3. Моделирование СБ-машин с константами
§ 4.4. Универсальность СБ-машин
Заключение
Литература