\chapter*{Предисловие}
\addcontentsline{toc}{schapter}{Предисловие}
\markboth{Предисловие}{Предисловие}

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

Теория вычислимых (с помощью компьютеров) функций появилась в
1930\д е годы, когда никаких компьютеров ещё не было. Первые
компьютеры были разработаны в 1940\д х годах, и среди их
разработчиков был английский математик Алан Тьюринг, один из
создателей теории вычислимых функций. В 1936 году он описал
абстрактные машины, которые теперь называют \emph{машинами
Тьюринга},
         \index{Машина!Тьюринга}%
         \index{Тьюринга машина}%
         \glossary{Тьюринг@\Тьюринг}%
и можно полагать, что идея хранимой в памяти
компьютера программы была подсказана доказательством теоремы о
существовании универсальной машины Тьюринга.

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

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

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

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

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

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

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

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

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

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

Просим сообщать о всех ошибках и опечатках авторам (электронные
адреса \texttt{ver@mccme.ru}, \texttt{shen@mccme.ru}; почтовый
адрес: Москва, 121002, Большой Власьевский пер., 11, Московский
центр непрерывного математического образования).

\begin{flushright}
        %
\textit{Н.\,К.\,Верещагин, А.\,Шень}
        %
\end{flushright}


