7Основы математической логики. Законы алгебры логики. Элементы теории алгоритмов

1. Интуитивное понятие алгоритма, вычислимой функции. Ансамбли конструктивных объектов. Область возможных исходных данных. Область применимости алгоритма. Примеры алгоритмов. Вычислимая функция.

2. Модели вычислений. Машины Тьюринга. Машины с неограниченными регистрами (МНР). Тезис Чёрча.

3. Разрешимость, перечислимость подмножества ансамбля конструктивных объектов. Критерий разрешимости перечислимого множества (теорема Поста). Свойства перечислимых, разрешимых множеств. Теорема о графике вычислимой функции. Теорема о проекции.

4. Универсальная вычислимая функция. Невозможность вычислимой функции, универсальной для класса всех всюду определённых вычислимых функций. Главная универсальная вычислимая функция. Теорема о трансляторе (s-m-n-теорема).

Примеры неразрешимых проблем. Неразрешимость проблемы остановки. Примеры неразрешимых перечислимых множеств.

Многозначная (m-сводимость). Свойства m-сводимости. Теорема Райса о неразрешимости нетривиальных классов в.ф. Примеры применения теоремы Райса.

Диофантовы множества. Десятая проблема Гильберта и ее отрицательное решение.