В лекции вводится понятие искусственного интеллекта, обсуждаются требования к нему. Описываеся тест Тьюринга, в качестве контаргумента к нему рассматривается эксперимент "китайская комната". Рассказывается о различных точках зрения на возможности осмысления у машины. Даются понятия программы, языка, алгоритма.

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

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