Сложность вычислений и алгоритмов

Затрагиваются проблемы математической логики, тесно связанные с теорией вычислительных машин. Рассматриваются модели вычислительных устройств, их классификация, классификация языков, оценки сложности вычислений и оценки сложности программ. Развивается связанный со сложностью программ подход А.Н. Колмогорова к обоснованию теории вероятностей и теории информации. Перевод ряда более ранних работ содержится в сборнике Проблемы математической логики (Мир, 1970).