Читать онлайн «Степени неразрешимости»

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ОСНОВАНИЯ МАТЕМАТИКИ ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1977 СТЕПЕНИ НЕРАЗРЕШИМОСТИ ДЖ. ШЕНФИЛД Перевод о английского И. А. ЛАВРОВА Под редакцией Ю. Л. ЕРШОВА ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1977 517 Ш 47 УДК 519. 9 Joseph It. Shoenfield DEGREES OF UNSOLVABILITY North-Holland Publishing Company American Blsevier Publishing Company 1971 Джозеф Щепфилв СТЕПЕНИ НЕРАЗРЕШИМОСТИ Т. С. Вайсбер$ M. , 1977 г. , 192 стр. с илл. Редактор В. В. Данченко Техн. редактор Й. В. Кошелева Корректоры Г. В. Подвольская, Сдано в набор 17. 05. 1977 г. Подписано к печати 29. 08. 1977 г. Бумага 84Х108'/м Физ. печ. я. 6. Условн. печ. я. 10,08. Уч. -изд. л. 9,57. Тираж 10 000 экз. Цена книги 75 к. Терминология и обозначения И 1. Рекурсивные функции 12 2. Изоморфизмы 15 3. Алгоритмы ; . ^ , . . . 18 4. Относительная рекурсивность 20 5. Рекурсивная перечислимость 24 6. Степени 29 7. Оценка степеней 32 8. Несравнимые степени 39 9. Верхние и нижние грани 42 10. Операция скачка 44 11. Минимальные степени 46 12. Простые множества 53 13. Метод приоритета 55 14. Теорема о разложении СО 15. Максимальные множества 04 16. Бесконечные нарушения 73 17. Индексные множества 80 18. Ветвящиеся степени . . . . 85 Дополнеиия . . . 95 К. Е. М. Ейтс. Три теоремы о степенях рекурсивно лерсчисли- мых мпожеств 97 А. X. Лахлан. Решетка рекурсивно перечислимых множеств 109 Л. Фейнер. Иерархии булевых алгебр 163 Л. Фейнер. Гипотеза сильной однородности 180 Именной указатель 185 Предметный указатель 186 Указатель обозначений 191 ПРЕДИСЛОВИЕ РЕДАКТОРА Предлагаемая вниманию читателей книга Дж. Шенфил- да посвящена изложению основных результатов о степенях неразрешимости (тьюринговых степенях). Эти результаты традиционно считаются трудными, так как в их доказатель- доказательствах используются различные формы так называемого «метода приоритета». Автор книги поставил перед собой цель изложить материал в максимально простой и ин- интуитивно оправданной форме. И нужно сказать, что это ему в основном удалось. Педагогическое мастерство авто- автора, известного уже советскому читателю по переводу его книги «Математическая логика» («Наука», М. , 1975), позволило ему создать небольшую книгу, которая содер- содержит практически все принципиально важные результаты о рекурсивно перечислимых степенях и которая тем не ме- менее доступна для широких кругов читателей — математи- математиков, интересующихся современными достижениями'теории алгоритмов. Стоит, однако, предупредить, что чтение кни- книги потребует от читателя напряженного внимания.