Теория нумераций, Ершов Ю.Л., 1977

Теория нумераций, Ершов Ю.Л., 1977.

   Предлагаемая читателю книга представляет собой введение в проблематику и методы теории нумераций — нового развивающегося раздела теории алгоритмов. Насколько известно автору, впервые идею о систематическом изучении нумерованных множеств высказал А. Н, Колмогоров в середине пятидесятых годов. Реализацией этой идеи для вычислимых нумераций в то время занялся В, А, Успенский. Основные его результаты изложены в статье [63] и в книге [10], вышедшей в I960 году. Параллельно ряд зарубежных математиков (Райс, Деккер, Майхилл, Фридбсрг, Лахлан, Лакомб, Пур-Эль и др.) также занимались изучением различных вопросов, связанных с вычислимыми нумерациями.




О теории нумераций.
Наиболее «инвариантной» частью для всех существующих в настоящее время в математике уточнений понятия алгоритма является класс частично рекурсивных арифметических функций (под частичной арифметической функцией понимается частичное отображение из конечной декартовой степени множества натуральных чисел N в N)—тех и только тех частичных арифметических функций, которые ВЫЧИСЛИМЫ в любом из предложенных в качестве уточнения алгоритмической вычислимости смысле. По существу эта инвариантность и позволяет говорить об эквивалентности всех уточнений и укрепляет уверенность в том, что класс всех частично рекурсивных функций совпадает с классом всех частичных арифметических функций, допускающих эффективное (в интуитивном смысле) вычисление.

Поэтому представляется желательным, чтобы все исследования в теории алгоритмов и ее приложениях проводились на основе «общего знаменателя» — класса всех частично рекурсивных функции. Одним из способов такой редукции к натуральным числам и арифметическим функциям, который неоднократно с успехом использовался уже в теории алгоритмов и математической логике, является использование подходящей нумерации, т. е. отображения некоторого подмножества множества натуральных чисел N на исследуемый класс конструктивных объектов (формул, слов, матриц и т. п.). Наиболее блистательным примером использования нумерации является доказательство К. Геделем своих знаменитых теорем о неполноте.

ОГЛАВЛЕНИЕ.
Предисловие.
Введение.
§1. О теории нумераций.
§2. Предварительные сведения.
§3. Некоторые сведения из алгебры.
§4. Теоретико-категорные понятия.
Глава 1 Вычислимые нумерации.
§1. Основные понятия.
§2. Главные нумерации.
§3. Отделимые нумерации.
§4. Полурешетка L0 (R) (случай конечного.
§5. Полурешетка L0 (R) (общий случай).
§6. Минимальные нумерации.
Глава 2 Категория R нумерованных множеств.
§1. Нумерации множества и его подмножеств.
§2. Категория R нумерованных множеств и ее свойства.
§3. Подобъекты нумерованного множества.
§4. Предполно и полно нумерованные множества.
§3. Позитивно нумерованные множества.
§6. Нумерованные множества с аппроксимацией.
Глава 3 Нумерованные множества и m-сводимость.
§1. Кратная m-сводимость.
§2. Индексные множества.
§3. Полнота и m-универсальностъ.
§4. Структурные теоремы о полно нумерованных множествах.
§5. Креативность и m-универсальность для вычислимых нумераций.
§6. Совершенные эквивалентности.
Глава 4 Вычислимые функционалы.
§1. Вычислимые нумерации морфизмов.
§2. Некоторые частные случаи.
§3. Условия разрешимости проблемы Р.
§4. Теория f-пространств.
§5. Вычислимые функционалы.
§6. Всюду определенные функционалы.
Приложение I. Описание славных идеалов полурешетки рекурсивно перечислимых m-степеней.
Приложение II. Алгебраическая характеризация полурешеток нумераций конечных множеств.
Литература.
Предметный указатель.
Указатель обозначений.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теория нумераций, Ершов Ю.Л., 1977 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Ершов