What Can Be Computed? A Practical Guide to the Theory of Computation

Книга представляет собой практическое введение в теорию вычислений, охватывающее ключевые концепции вычислимости и сложности. Автор, Джон МакКормик, использует Python для иллюстрации фундаментальных идей, таких как неразрешимые проблемы, машины Тьюринга и универсальные программы.

Первая часть посвящена теории вычислимости, включая доказательства невозможности некоторых программ (например, проблемы остановки) и формальное определение вычислительных задач. Вторая часть переходит к теории сложности, рассматривая трактабельные и интрактабельные проблемы.

Книга предназначена для студентов и специалистов, желающих понять границы вычислимости и практические аспекты теории. Она сочетает строгие математические основы с примерами на Python, делая абстрактные концепции доступными.

Особое внимание уделяется историческому контексту и практическим приложениям, что отличает её от традиционных учебников. Включает упражнения для закрепления материала.