Первый день: диагональный метод. Сначала мы познакомимся с понятиями разрешимого и перечислимого множества, изучим их основные свойства. Затем при помощи диагонального метода мы докажем существование перечислимых, но неразрешимых задач. Наиболее известной такой задачей является проблема остановки: остановится ли программа на данном входе? Наконец, при помощи техники m-сводимости мы докажем, что ни множество программ, которые останавливаются всюду, ни дополнение этого множества, не являются перечислимыми.