Coдepжaниe зaнятий Введение. Основные понятия и проблемы теории алгоритмов. Необходимость уточнения понятия алгоритма

Массовые проблемы и алгоритмы в математике. Интуитивное понятие алгоритма. Свойства алгоритмов. Необходимость уточнения понятия алгоритма в математике. Суть направлений уточнения понятия алгоритма. Связь между понятием функции и алгоритма. Вычислимые функции. Разрешимые множества.

Примитивно-рекурсивные функции и рекурсивно-перечислимые множества

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

Универсальные функции и неразрешимость. Нумерации

Универсальная общерекурсивная функция. Диагональная конструкция. Перечислимое неразрешимое множество.

Нумерация частично рекурсивных функций. Главные универсальные нумерации. Теорема о невозможности (примитивно) рекурсивной функции, универсальной для класса всех n-местных (примитивно) рекурсивной функции. Частично рекурсивная функция, универсальная для класса всех n-местных частично рекурсивных функций. Пример частично рекурсивной функции, не продолжаемой до рекурсивной функции. Пример всюду определенной не рекурсивной функции. Множество номеров рекурсивных функций как пример не рекурсивного перечислимого множества.

Пример рекурсивного перечислимого, но не рекурсивного множества. Пример множества не являющегося рекурсивно перечислимым. Теоремы о представлении произвольного рекурсивного перечислимого множества, как области определения и как области значения частично рекурсивной функции.

Главные универсальные множества. Свойства главных нумераций. Теорема Успенского-Райса. Изоморфизм главных нумераций.

Машины Тьюринга

Машины Тьюринга: элементарные действия, шаг работы, команды, программа машины Тьюринга. Понятия машины Тьюринга как математическое уточнение интуитивного понятия алгоритма. Вычислимые по Тьюрингу функции. Тезис Тьюринга. Операции над машинами Тьюринга: композиция. Ветвление. Зацикливание. Правильно вычислимые по Тьюрингу функции. Элементарные машины. Правильная вычислимость частично рекурсивных и вычислимых по Тьюрингу функций.