Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Неразрешимые проблемы алгебры и логики
Классическая теория вычислимости


Что: Лекция
Когда: Четверг, 22 сентября 2016, 08:30–10:00
Где: 2-й учебный корпус К(П)ФУ, ауд. 1011

Описание

Третий день: неразрешимые проблемы алгебры и логики. Неразрешимые проблемы, связанные с работой программ, весьма умозрительны. Может быть, эта теория не имеет отношения к остальной математике? Нет, имеет! Эти проблемы можно переформулировать в терминах других областей. Так, неразрешима проблема равенства в полугруппах (в этом заключается теорема Маркова-Поста), нельзя проверить формулу первого порядка на общезначимость (это теорема Чёрча), а колмогоровская сложность слова из нулей и единиц невычислима.