Цель миникурса – познакомить слушателей с некоторыми понятиями, результатами, методами и приложениями теории вычислимости, теории сложности вычислений и теории автоматов. Теория вычислимости будет проиллюстрирована примерами разрешимых и неразрешимых проблем в математике (в частности, будут кратко обсуждены 10-я проблема Гильберта и арифметика Пеано). Сложность вычислений будет проиллюстрирована теорией NP-полноты и теоремами Тарского о разрешимости в теории полей. Теорию автоматов проиллюстрируем автоматами Бюхи и применениями к задаче верификации систем с конечным числом состояний.

Хотя обсуждаемый материал носит теоретический характер, он тесно связан с практическими вопросами информатики. Для иллюстрации этого рассмотрим связь этих результатов с системами автоматического доказательства теорем, системами компьютерной алгебры, SAT-решателями и верификаторами.