В лекции подробно рассматривается проблема остановки, проблема распознавания языка. Вводятся понятия вычислимых, полувычислимых и перечислимых языков. Обсуждаются возможности алгоритмического доказательства теорем и возникающие при этом проблемы. Приводятся примеры.