Невычислимость, неразрешимость, недоказуемость
Сосинский А.Б.
Занятия (на которых будут в основном решаться задачи) посвящены результатам, показывающим принципиальные дефекты формализации математики: существование(1) (очень простых!) функций из N в N, которые ни один компьютер не может сосчитать (невычислимость);(2) подмножеств натуральных чисел, принадлежность к которым не может определить ни одна машина (неразрешимость);(3) математических утверждений о натуральных числах, которые нельзя вывести из аксиом в данной формальной системе, хотя они заведомо верны (недоказуемость, или замечательная теорема Гёделя о неполноте).
