Искандер Калимуллин. Теоремы Гёделя и вычислимость

Вторая лекция цикла о математике прошла в Смене 5 декабря 2021 года.
Лектор: Искандер Калимуллин, профессор РАН, профессор кафедры алгебры и математической логики КФУ.
На лекции были освещены простые и не очень простые идеи, лежащие в основании математической логики. Теорема Гёделя о полноте позволяет рассматривать математическое доказательство как конструктивный алгоритмический процесс. С другой стороны, теорема Гёделя о неполноте утверждает, что в любой достаточно богатой теории существуют утверждения, которые невозможно ни доказать, ни опровергнуть. Идея доказательства этой нетривиальной теоремы связана как с парадоксами древности (парадокс лжеца), так и с богатыми выразительными возможностями алгоритмических языков.