Обзор книги Петцольда “Читаем Тьюринга”

На самом деле книга называется “Читаем Тьюринга. Путешествие по исторической статье Тьюринга о вычислимости и машинах Тьюринга” и вышла она у нас в серии “Классика программирования”. Книга очень интересна и одновременно крайне сложна для восприятия:)

Рис.1 “Обложка книги”

На самом деле Тьюринг за свою жизнь опубликовал около 30 работ, причем это все были статьи и ни одной книги. Две статьи стали классическими:

• “О вычислимых числах” — здесь была введена машина Тьюринга для решения одной из проблем Гильберта относительно общего процесса доказуемости произвольных утверждений в математической логике
• “Вычислительные машины и интеллект” — здесь появился знаменитый тест Тьюринга, в котором наличие интеллекта у машины проверяется общением с человеком — если человек не может отличить машину от человека, то считаем что у нее есть интеллект. Я кратко рассказывал про это в статье “Тьюринг, Камбербэтч и Игра в имитацию”

В книге “Читаем Тьюринга” Чарльз Петцольд сначала готовит читателей к восприятию статьи Тьюринга “О вычислимых числах”, в которой основное место уделено вычислимым числам, т.е. тем числам, которые могут быть вычислены машиной. В рамках этой подготовки автор вспоминает про натуральные, целые, рациональные, иррациональные числа, алгебраические и трансцендентные числа, которые относятся к вещественным числам.

Дальше он вводит исторический контекст, в котором упоминаются:

• Гильберт с постановкой изначальной проблемы относительно разрешимости
• Бертран Рассел с логической системой и монументальным трудом “Principia Mathematica”
• Курт Гедель с теоремой о неполноте
• и собственно сам Тьюринг с решением проблемы неразрешимости, заодно с Алонсо Чёрчем, который ее решил на пару месяцев раньше и другим способом через разработку теории лямбда-исчислений

Во второй части Чарльз Петцольд переходит к оригинальной работе Алана Тьюринга, которую он приводит полностью. 35-страничную статья Тьюринга сопровождается очень подробными и глубокими комментариями, которые позволяют успевать за мыслью великого математика. Вся вторая часть книги посвящена вычислимым числам.

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

В четвертой части книги Чарльз подводит итоги и делает далеко идущие выводы из этой эпохальной работы Тьюринга. Для понимания масштаба можно просто привести названия двух глав, из которых состоит эта часть:

• “Весь мир — машина Тьюринга?”
• “Долгий сон Диофанта” — тут идет циклическая отсылка к началу книги, в котором речь шла о Диофанте и его уравнениях, а также о том, что гораздо интереснее не просто их решать, а определять имеет ли вообще частное диофантово уравнение решение в частных числах

P.S.

Книга определенно хороша и ее полезно почитать современным разработчикам, т.к. наши текущие компьютеры по возможностям эквивалентны машинам Тьюринга:)

Правда есть одно но — она точно не зайдет широкому кругу читателей, т.к. требует вдумчивого чтения и широкого кругозора