Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Вторник, 20 сентября 2016, 10:10–11:40
Где: 2-й учебный корпус К(П)ФУ, ауд. 1011

Описание

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