ВкЭ 2017 МЛиТА 4ПИ заочн
.doc
Вопросы для подготовки к экзамену
-
Интуитивное определение алгоритма и вычислимой функции
-
Частично и примитивно рекурсивные функции
-
Вычислимость рекурсивных функций. Тезис Черча
-
Определение оператора подстановки, примеры применения
-
Определение оператора примитивной рекурсии, примеры применения
-
Определение оператора минимизации, примеры применения
-
Построение одноместных рекурсивных функций
-
Построение двухместных рекурсивных функций
-
Машины Тьюринга. Команды в виде четверок и в виде пятерок
-
Функции, вычислимые по Тьюрингу. Тезис Тьюринга
-
Одноместные функции, вычислимые по Тьюрингу
-
Двухместные функции, вычислимые по Тьюрингу
-
Машины с неограниченными регистрами
-
Нормальные алгоритмы Маркова
-
Машины Поста. Функции, вычислимые по Посту
-
Нумерация множества упорядоченных пар натуральных чисел
-
Нумерация машин Тьюринга и вычислимых функций
-
Существование функции, невычислимой по Тьюрингу
-
Разрешимые отношения: определение и примеры
-
Свойства дополнения, объединения и пересечения разрешимых функций
-
Неразрешимость проблемы остановки
-
Универсальные функции
-
Теорема о параметризации
-
Меры сложности алгоритмов