Описание:В рамках курса "Элементы теории вычислимости" изучаются основные идеи и понятия теории вычислимости, как дисциплины, появившейся на стыке логики, математики и теоретической информатики. Наибольшее внимание уделяется формализму рекурсивных функций и понятию вычислимых по Тьюрингу функций, тезису Черча-Тьюринга. Рассматриваются некоторые неразрешимые проблемы. В частности, доказывается теорема Черча о неразрешимости проблемы выполнимости для формул языка логики предикатов первого порядка.