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