Степени неразрешимости

Abstract

Из предисловия редактора:Книга Шенфилда посвящена изложению основных результатов о степенях неразрешимости (тьюринговых степенях). Эти результаты традиционно считаются трудными, так как в их доказательствах используются различные формы так называемого ''метода приоритета''. Автор книги поставил перед собой цель изложить материал в максимально простой и интуитивно оправданной форме. И нужно сказать, что это ему в основном удалось. Педагогическое мастерство автора позволило ему создать небольшую книгу, которая содержит практически все принципиально важные результаты о рекурсивно перечислимых степенях и которая тем не менее доступна для широких кругов читателей - математиков, интересующихся современными достижениями теории алгоритмов. Стоит, однако, предупредить, что чтение книги потребует от читателя напряженного внимания.