Степени неразрешимости
Наука и образование / Литература для ВУЗов / Учебная литература
Основная информация:
Название: Степени неразрешимости
Жанр: Математика
Автор: Шенфилд Дж.
Год выпуска: 1977
Формат: PDF
Размер: 21.8 MB
ISBN: 265581150678
Язык: Русский
СКАЧАТЬ Степени неразрешимости БЕСПЛАТНО EPUB - DOC - DJVU - RTF - PDFОписание: Предлагаемая вниманию читателей книга Дж. Шенфилда посвящена изложению основных результатов о степенях неразрешимости (тьюринговых степенях). Эти результаты традиционно считаются трудными, так как в их доказательствах используются различные формы так называемого «метода приоритета». Автор книги поставил перед собой цель изложить материал в максимально простой и интуитивно оправданной форме. И нужно сказать, что это ему в основном удалось.Терминология и обозначения.Рекурсивные функции.
Изоморфизмы.
Относительная рекурсивность.
Рекурсивная перечислимость.
Степени.
Оценка степеней.
Несравнимые степени.
Верхние и нижние грани.
Операция скачка.
Минимальные степени.
Простые множества.
Метод приоритета.
Теорема о разложении.
Максимальные множества.
Бесконечные нарушения.
Индексные множества.
Ветвящиеся степени.
Дополнения.
К.Е.М. Ейтс. Три теоремы о степенях рекурсивно перечислимых множеств.
А.Х. Лахлан. Решетка рекурсивно перечислимых множеств.
Л. Фейнер. Иерархии булевых алгебр.
Л. Фейнер. Гипотеза сильной однородности.