Рецензия на книгу «Читаем Тьюринга»

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

Чарлз Петцольд «Читаем Тьюринга»

Издательство «ДМК», Москва, 2014

ISBN: 978-5-97060-010-8

http://dmkpress.com/catalog/computer/software_development/978-5-97060-010-8/

Немного истории

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

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

Однако, в первой половине 30-х годов XX века эти надежды рассыпались в прах. В 1931 году австриец Курт Гедель (1906-1978) показал, что в арифметике - самой, казалось бы знакомой и изученной области математики существуют истинные, но не доказуемые средствами самой арифметики теоремы. Оказалось, что арифметика не полна и ее методы недостаточно мощны. Забрезжил жуткий для всей математики призрак того, что арифметика может оказаться еще и противоречивой; это означало, что вся математика не имеет под собой фундамента. К счастью, немцу Герхарду Генцену (1909-1945) удалось показать, что это не так. Но по стройному зданию, возводимому Гильбертом и его школой, пошли первые трещины. Надежды на то, что entscheidungsproblem может быть положительно разрешена, стремительно таяли, но это еще нужно было доказать.

В 1936 году, практически одновременно американец Алонсо Черч (1903—1995) и англичанин Алан Тьюринг (1912-1954) доказали, что entscheidungsproblem не разрешима. Конечно, труды Гильберта не пропали даром; они по сию пору являются фундаментом оснований математики, но многое пришлось пересмотреть.

Методы Черча и Тьюринга были существенно различными, но выводы к которым они пришли четко свидетельствуют о том, что алгоритма установления истины в математике в общем случае не существует.

О книге «Читаем Тьюринга»

Книга, которой посвящена эта рецензия, принадлежит перу известного американского популяризатора Чарлза Петцольда (некоторые его книги переведены на русский язык и хорошо известны российскому читателю). Оригинальное американское издание вышло сравнительно недавно (Charles Petzold «The Annotated Turing: A Guided Tour through Alan Turing’s Historic Paper on Computability and the Turing Machine» - Wiley Publishing, Inc., 2008), но успело завоевать широкое признание. Если считать количество ссылок и индекс цитирования показателем качества научной работы, то работа Петцольда, безусловно, успешна.

Книгу отличает простой, неторопливый, ясный и местами кропотливый стиль изложения. Автор, шаг за шагом, едва ли не с микроскопом исследует главную работу Алана Тьюринга, посвященную entscheidungsproblem. Именно в этой работе (объемом менее 40 страниц) впервые появились знаменитые машины Тьюринга ставшие на многие годы универсальной теоретической концепцией (и кошмарным сном некоторых студентов) специализирующихся в computer science; следует с сожалением отметить, что эта фундаментальная работа Тьюринга так никогда и не была переведена на русский язык. Благодаря книге Петцольда, русскоязычный читатель может полностью ознакомиться как со статьей Тьюринга, так и с ее математическим «окружением».

Книга совершенно самодостаточна и все необходимые сведения из математики содержатся в ней самой. Хорошо успевающий по математике старшеклассник (готовый, разумеется, приложить определенные усилия) вполне может овладеть содержимым книги. Но оценить все значение вклада Тьюринга он вряд ли сумеет – для этого нужен немного более зрелый читатель. Во всяком случае студенты 1-2 курса не должны испытать при чтении книги особых сложностей. Я настоятельно рекомендую книгу «Читаем Тьюринга» всем настоящим программистам, кто действительно интересуется своей специальностью, кто ощущает потребность в понимании теоретических концепций, лежащих в основе программирования.

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

Следует отметить блестящую работу переводчика Л.Н.Чернышова (написавшего, кроме того, небольшое дополнение к книге). Ему удалось точно передать все нюансы оригинала и сохранить непринужденный стиль автора книги.

Чарлз Петцольд тонко и деликатно проводит читателя по самым потаенным уголкам из которых родились на свет современные компьютеры и современное программное обеспечение. Книгу можно смело отнести к лучшим образцам научной литературы для впервые изучающих тот или иной предмет. Открыв книгу от нее невозможно оторваться – настолько в ней переплетены математика, логика, программирование, история и даже жизненные интриги. Читателя ждет захватывающее путешествие в прошлое (не такое, впрочем, и далекое) из которого получилось наше настоящее и развивается будущее.