Книга посвящена доказательству существования невычислимых функций и алгоритмически неразрешимых задач. Обсуждаются проблемы оценки сложности вычислений и алгоритмов (Рекурсивные функции и алгоритмы. Диофантовы множества и алгоритмическая неразрешимость. Сложность и случайность. Формальные языки и вычислимость. Теорема Геделя. Рекурсивные группы) (Подробнее)
