City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Неразрешимые проблемы алгебры и логики
Classical theory of computability

What: Lecture
When: Thursday, 22 September 2016, 10:10–11:40
Where: 2-й учебный корпус К(П)ФУ, ауд. 1011

Description

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