Тип: курс по выбору студента

Лектор: Носов Михаил Васильевич

Для: 3-6 курсов, магистрантов

Время: ср 16.45 - 18.20

Начиная с: 01.10.2025

Машины Тьюринга. Основные понятия. Тезис Тьюринга. Вычислимые (по
Тьюрингу) функции. Примеры машин Тьюринга.
Проблема самоприменимости. Проблема применимости.
Универсальные машины Тьюринга.
Классы вычислимых и рекурсивных функций. Операции суперпозиции,
примитивной рекурсии, минимизации. Тезис Чёрча. Примеры.
Некоторые теоремы теории рекурсивных функций. Функция Аккермана.
Теорема о совпадении класса вычислимых по Тьюрингу функций и класса
частично рекурсивных функций (Кв=Кчр).
Нормальные алгоритмы Маркова. Теорема о совпадении класса нормально
вычислимых функций с классами Кв, Кчр.
Разрешимость и перечислимость множеств. Теорема Райса.
О теореме Гёделя о неполноте.

Материалы:

[1] Мальцев А.И. Алгоритмы и рекурсивные функции.
[2] Мендельсон Э. Введение в математическую логику.
[3] Яблонский С.В. Введение в дискретную математику.
[4] Гаврила Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной
математики.