Джозеф Шенфилд

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

В настоящее время интерес к математической логике и теории алгоритмов непрерывно растет. Все большее число высших учебных заведений включает в обязательную программу обучения курсы математической логики, теории алгоритмов или их фрагменты. Специалисты в области ЭВМ начинают осознавать, что эти разделы математики являются фундаментом для построения настоятельно необходимой сейчас хорошей теории мат...