Электронная библиотека учебников » Математика » Лекции по математической логике и теории алгоритмов. Вычислимые функции - Н.К. Верещагин, А. Шень

Лекции по математической логике и теории алгоритмов. Вычислимые функции - Н.К. Верещагин, А. Шень

 
Название: Лекции по математической логике и теории алгоритмов. Вычислимые функции
Автор: Н.К. Верещагин, А. Шень
Категория: Математика
Тип: Книга
Дата: 11.01.2009 19:11:08
Скачано: 632
Оценка:
Описание: Предлагаемая вашему вниманию книга написана по материалам лекций для младшекурсников, которые читались авторами в разные годы на механико-математическом факультете МГУ. (В этой серии уже вышла книга «Начала теории множеств»; готовится к печати книга «Языки и исчисления».) Теория вычислимых (с помощью компьютеров) функций появилась в 1930-е годы, когда никаких компьютеров ещё не было. Первые компьютеры были разработаны в 1940-х годах, и среди их разработчиков был английский математик Алан Тьюринг, один из создателей теории вычислимых функций. В 1936 году он описал абстрактные машины, которые теперь называют машинами Тьюринга, и можно полагать, что идея хранимой в памяти компьютера программы была подсказана доказательством теоремы о существовании универсальной машины Тьюринга. Уже поэтому основные понятия теории вычислимости (или, как говорят, общей теории алгоритмов) достойны внимания математиков и программистов. Но эта теория имеет и более широкий культурный аспект. Один из её основателей, американский математик Эмиль Пост, писал в 1944 году, что «формулировка этого понятия [вычислимости] может сыграть в истории дискретной математики роль, уступающую по значению лишь формулировке понятия натурального числа». Пожалуй, сейчас это высказывание Поста выглядит преувеличением: за последние десятилетия стало ясно, что различие между быстро и долго решаемыми задачами не менее философски важно, чем различие между алгоритмически разрешимыми и неразрешимыми, и теория сложности вычислений стала одной из центральных в логике (и вообще в математике). Мы сознательно не касаемся теории сложности вычислений — это большая и отдельная тема. Вместо этого мы попытались отобрать центральные понятия и факты общей теории алгоритмов и изложить их понятно, стараясь не заслонять простые общие идеи техническими де-
Файл: 451.3 КБ
Скачать