Посвящается одному из актуальных и бурно развивающихся разделов математической логики - теории алгоритмов, а также важнейшим ее связям с другими разделами математики. Является одним из лучших пособий для знакомства с основными направлениями, идеями и методами теории алгоритмов.

Настоящая книга возникла в результате обработки конспектов лекций по математиеской логике, теории алгоритмов и их приложений, читавшихся автором в 1956-1960 гг. Целиком за пределами книги остались теория автоматов, приложения теории алгоритмов к формальным теориям, теория степеней неразрешимости. Сколько-нибудь подробное изложение этих разделов в настоящее время требует специальных монографий.

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