Степени неразрешимости, Шенфилд Дж., 1977

Степени неразрешимости, Шенфилд Дж., 1977.

   Предлагаемая вниманию читателей книга Дж. Шенфилда посвящена изложению основных результатов о степенях неразрешимости (тьюринговых степенях). Эти результаты традиционно считаются трудными, так как в их доказательствах используются различные формы так называемого «метода приоритета». Автор книги поставил перед собой цель изложить материал в максимально простой и интуитивно оправданной форме. И нужно сказать, что это ему в основном удалось. Педагогическое мастерство автора, известного уже советскому читателю по переводу его книги «Математическая логика» («Наука», М., 1975), позволило ему создать небольшую книгу, которая содержит практически все принципиально важные результаты о рекурсивно перечислимых степенях и которая тем не менее доступна для широких кругов читателей — математиков, интересующихся современными достижениями теории алгоритмов. Стоит, однако, предупредить, что чтение книги потребует от читателя напряженного внимания.




Рекурсивные функции.
Теория рекурсии — это абстрактная теория вычислений. Все вычисления, которые мы будем рассматривать, по крайней мере теоретически, могут быть проделаны в конечное время. Это означает, что объекты, которые мы вычисляем, должны быть конечными объектами, т. е. объектами, которые могут быть заданы с помощью конечного количества информации.

Несколько примеров сделают понятно конечного объекта более ясным. Всякое натуральное число — конечный объект, так как оно может быть задано с помощью арабских цифр, входящих в обозначение этого числа. С другой стороны, действительное число, вообще говоря, не является конечным объектом, так как для его задания мы должны, например, задать каждый десятичный знак этого числа, которых бесконечно много. Каждая n-ка конечных объектов является конечным объектом, так как мы можем задать ее, задавая по порядку каждый из n объектов, Всякий конечный класс конечных объектов является конечным объектом; бесконечный класс конечных объектов, вообще говоря, не является конечным объектом. Каждая конечная последовательность конечных объектов является конечным объектом; бесконечная последовательность, в общем случае, нс является конечным объектом.

ОГЛАВЛЕНИЕ.
Предисловие редактора.
Введение.
0. Терминология и обозначения.
1. Рекурсивные функции.
2. Изоморфизмы.
3. Алгоритмы.
4. Относительная рекурсивность.
5. Рекурсивная перечислимость.
6. Степени.
7. Оценка степеней.
8. Несравнимые степени.
9. Верхние и нижние грани.
10. Операция скачка.
11. Минимальные степени.
12. Простые множества.
13. Метод приоритета.
14. Теорема о разложении.
15. Максимальные множества.
16. Бесконечные нарушения.
17. Индексные множества.
18. Ветвящиеся степени.
Дополнения.
К. Е. М. Ейтс. Три теоремы о степенях рекурсивно перечислимых множеств.
А. X. Лахлан. Решетка рекурсивно перечислимых множеств.
Л. Фейнер. Иерархии булевых алгебр.
Л. Фейнер. Гипотеза сильной однородности.
Именной указатель.
Предметный указатель.
Указатель обозначений.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Степени неразрешимости, Шенфилд Дж., 1977 - fileskachat.com, быстрое и бесплатное скачивание.

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


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




Теги: учебник по математике :: математика :: Шенфилд :: степень :: множество