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

Скачать

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

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