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