Основы вычислимости и теории сложности. Лекция 2

Вычислимые функции

Неразрешимость разных задач, сведение по Карпу, NP-полнота задачи об ограниченной остановке. Вычислимые функции, вычислимость функции и перечислимость ее графика, пример числа, которое является пределом вычислимой последовательности, но не приближается алгоритмически, диагональная функция и то, что ее нельзя продолжить до всюду определенной, главные нумерации вычислимых функций. Теорема Успенского-Райса. другие примеры неразрешимых множеств. Последовательность Шпеккера. Теорема Успенского-Райса.

Страница лекции на сайте Computer Science Center​​​​​​​