лекции по математической логике и теории алгоритмов

PDF 159 стр. 1,1 МБ Бесплатная загрузка

159 стр.

FaylHub.uz

Скачать через Telegram

Размер 1,1 МБ

Тип файла PDF

Страницы 159

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1 / 159

лекции по математической логике и теории алгоритмов н. к. верещагин, а. шень вычислимые функции издание четвёртое, исправленное москва издательство мцнмо, 2012 удк 510.5 ббк 22.12 в31 верещагин н.к., шень а. в31 лекции по математической логике и теории алгоритмов. часть 3. вычислимые функции. — 4-е изд., исправленное. — м.: мцнмо, 2012. — 160 c. isbn 978-5-4439-0014-8 книга написана по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата мгу. в ней рассказы- вается об основных понятиях общей теории вычислимых функций (вычис- лимость, разрешимость, перечислимость, универсальные функции, нуме- рации и их свойства, m-полнота, теорема о неподвижной точке, арифме- тическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины тьюринга, рекурсивные функции). изложение рассчитано на учеников математических школ, сту- дентов-математиков и всех интересующихся основами теории алгоритмов. книга содержит около 100 задач различной трудности. предыдущее издание книги вышло в 2008 г. ббк 22.12 тексты, составляющие книгу, являются свободно распространяемыми …

2 / 159

ста . . . . . . . . . 21 3. нумерации и операции 23 3.1. главные универсальные функции . . . . . . . . . . . . . 23 3.2. вычислимые последовательности функций . . . . . . . 26 3.3. главные универсальные множества . . . . . . . . . . . . 27 4. свойства главных нумераций 30 4.1. множества номеров . . . . . . . . . . . . . . . . . . . . . 30 4.2. однозначные нумерации . . . . . . . . . . . . . . . . . . 33 4.3. новые номера старых функций . . . . . . . . . . . . . . 37 4.4. изоморфизм главных нумераций . . . . . . . . . . . …

3 / 159

n . . . . . . . . . . . . . . . . . . . . . . . 91 8.2. универсальные множества в σn и πn . . . . . . . . . . 93 8.3. операция скачка . . . . . . . . . . . . . . . . . . . . . . . 95 8.4. классификация множеств в иерархии . . . . . . . . . . 100 9. машины тьюринга 103 9.1. зачем нужны простые вычислительные модели? . . . . 103 9.2. машины тьюринга: определение . . . . . . . . . . . . . 103 9.3. машины тьюринга: обсуждение . . . . . . . . . . . . . 105 9.4. ассоциативные исчисления . . . . . . . . . . …

4 / 159

исчис- ления».) теория вычислимых (с помощью компьютеров) функций появи- лась в 1930-е годы, когда никаких компьютеров ещё не было. первые компьютеры были разработаны в 1940-х годах, и среди их разработ- чиков был английский математик алан тьюринг, один из создателей теории вычислимых функций. в 1936 году он описал абстрактные машины, которые теперь называют машинами тьюринга, и можно полагать, что идея хранимой в памяти компьютера программы была подсказана доказательством теоремы о существовании универсаль- ной машины тьюринга. уже поэтому основные понятия теории вычислимости (или, как говорят, общей теории алгоритмов) достойны внимания математи- ков и программистов. но эта теория имеет и более широкий куль- турный аспект. один из её основателей, американский математик эмиль пост, писал в 1944 году, что «формулировка этого понятия [вычислимости] может сыграть в истории дискретной математики роль, уступающую по значению лишь формулировке понятия нату- рального числа». пожалуй, сейчас это высказывание поста выглядит преувели- чением: за последние десятилетия стало ясно, что различие …

5 / 159

мы указываем на с. 150 некоторые изданные на русском языке книги. авторы пользуются случаем поблагодарить своего учителя, вла- димира андреевича успенского, лекции, тексты и высказывания ко- торого повлияли на них (и на содержание этой книги), вероятно, даже в большей степени, чем авторы это осознают. при подготовке текста использованы записи а. евфимьевского и а. ромащенко (который также прочёл предварительный вариант книги и нашёл там немало ошибок). оригинал-макет первого издания книги подготовлен в.в. шува- ловым; без его настойчивости (вплоть до готовности разделить от- ветственность за ошибки) оригинал-макет вряд ли появился бы к какому-либо сроку. авторы признательны école normale supérieure de lyon (фран- ция) за поддержку и гостеприимство во время написания этой книги. первое издание книги стало возможным благодаря российскому фонду фундаментальных исследований, а также и.в.ященко, ко- торый уговорил авторов подать туда заявку. во втором издании ис- правлены замеченные опечатки (увы, многочисленные) и добавлено несколько задач. в третьем издании был дополнен именной указа- …

Хотите читать дальше?

Скачайте все 159 страниц бесплатно через Telegram.

Скачать полный файл

О "лекции по математической логике и теории алгоритмов"

лекции по математической логике и теории алгоритмов н. к. верещагин, а. шень вычислимые функции издание четвёртое, исправленное москва издательство мцнмо, 2012 удк 510.5 ббк 22.12 в31 верещагин н.к., шень а. в31 лекции по математической логике и теории алгоритмов. часть 3. вычислимые функции. — 4-е изд., исправленное. — м.: мцнмо, 2012. — 160 c. isbn 978-5-4439-0014-8 книга написана по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата мгу. в ней рассказы- вается об основных понятиях общей теории вычислимых функций (вычис- лимость, разрешимость, перечислимость, универсальные функции, нуме- рации и их свойства, m-полнота, теорема о неподвижной точке, арифме- тическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительны...

Этот файл содержит 159 стр. в формате PDF (1,1 МБ). Чтобы скачать "лекции по математической логике и теории алгоритмов", нажмите кнопку Telegram слева.

Теги: лекции по математической логике… PDF 159 стр. Бесплатная загрузка Telegram