Предисловие

Предлагаемая вашему вниманию книга написана по материалам лекций для младшекурсников, которые чи­тались авторами в разные годы на механико-математи­ческом факультете МГУ. (В этой серии уже вышла кни­га «Начала теории множеств»; готовится к печати книга «Языки и исчисления».)

Теория вычислимых (с помощью компьютеров) функ­ций появилась в 1930-е годы, когда никаких компьюте­ров ещё не было. Первые компьютеры были разработаны в 1940-х годах, и среди их разработчиков был английский математик Алан Тьюринг, один из создателей теории вы­числимых функций. В 1936 году он описал абстрактные машины, которые теперь называют машинами Тьюрин­га, и можно полагать, что идея хранимой в памяти ком­пьютера программы была подсказана доказательством теоремы о существовании универсальной машины Тью­ринга.

Уже поэтому основные понятия теории вычислимости (или, как говорят, общей теории алгоритмов) достойны внимания математиков и программистов. Но эта теория имеет и более широкий культурный аспект. Один из её основателей, американский математик Эмиль Пост, пи­сал в 1944 году, что «формулировка этого понятия [вычи­слимости] может сыграть в истории дискретной матема­тики роль, уступающую по значению лишь формулировке понятия натурального числа».

Пожалуй, сейчас это высказывание Поста выглядит преувеличением: за последние десятилетия стало ясно, что различие между быстро и долго решаемыми зада­чами не менее философски важно, чем различие между алгоритмически разрешимыми и неразрешимыми, и тео­рия сложности вычислений стала одной из центральных в логике (и вообще в математике).

Мы сознательно не касаемся теории сложности вычи­слений — это большая и отдельная тема. Вместо этого мы попытались отобрать центральные понятия и факты общей теории алгоритмов и изложить их понятно, стара­ясь не заслонять простые общие идеи техническими де­талями. Мы не предполагаем никаких специальных пред­варительных знаний, хотя рассчитываем на некоторый уровень математической культуры (и не объясняем, ска­жем, что такое множество, функция или действительное число).

Надеемся, что первое знакомство с теорией алгорит­мов доставит удовольствие. Для тех, кто захочет продол­жить знакомство с этой теорией (являющейся централь­ной частью математической логики), мы указываем на с. 166 некоторые изданные на русском языке книги.

Авторы пользуются случаем поблагодарить своего учителя, Владимира Андреевича Успенского, лекции, тексты и высказывания которого повлияли на них (и на содержание этой книги), вероятно, даже в большей степени, чем авторы это осознают.

При подготовке текста использованы записи А. Евфи-мьевского и А. Ромащенко (который также прочёл пред­варительный вариант книги и нашёл там немало оши­бок).

Оригинал-макет книги подготовлен её редактором, В.В.Шуваловым; без его настойчивости (вплоть до го­товности разделить ответственность за ошибки) ориги­нал-макет вряд ли появился бы к какому-либо сроку.

Авторы признательны Ecole Normale Superieure de Lyon (Франция) за поддержку и гостеприимство во вре­мя написания этой книги.

Издание книги стало возможным благодаря Россий­скому фонду фундаментальных исследований, а также И. В.Ященко, который уговорил авторов подать туда за­явку.

Наконец, мы благодарим сотрудников, аспирантов и студентов кафедры математической логики мехмата МГУ, а также всех участников наших лекций и семина­ров и читателей предварительных вариантов этой книги.

Просим сообщать о всех ошибках и опечатках авто­рам (электронные адреса verfimccme.ru, shenfimccme.ru; почтовый адрес: Москва, 121002, Большой Власьевский пер., 11, Московский центр непрерывного математиче­ского образования).

Н. К. Верещагин, А.Шень