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

Чарльз Петцольд

Читаем Тьюринга
Путешествие
по исторической статье Тьюринга
о вычислимости и машинах Тьюринга

Charles Petzold

The Annotated Turing
Guided Tour through Alan Turing’s
Historic Paper on Computability
and the Turing Machine

Чарльз Петцольд

Читаем Тьюринга
Путешествие
по исторической статье Тьюринга
о вычислимости и машинах Тьюринга

Москва, 2014

УДК 004.3.01:510.5
ББК 32.97
П29

Петцольд Ч.
П29 Читаем Тьюринга. Путешествие по исторической статье Тьюринга о вычислимости и машинах Тьюринга / пер. с анг. Борисова Е. В., Чернышова Л. Н. – М.: ДМК Пресс, 2014. – 440 с.: ил.
ISBN 978-5-97060-010-8
Книга, которую вы держите в руках, принадлежит перу известного
американского популяризатора Чарлза Петцольда. В ней автор исследует главную работу Алана Тьюринга, посвященную проблеме
разрешимости. Именно в этой работе впервые появились знаменитые
машины Тьюринга, ставшие на многие годы универсальной теоретической концепцией computer science.
Автор тонко и деликатно проведет вас по самым потаенным уголкам,
из которых родились на свет современные компьютеры и современное
программное обеспечение.
Читателя ждет захватывающее путешествие в прошлое, из которого
получилось наше настоящее и развивается будущее.

УДК 004.3.01:510.5
ББК 32.97
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без
письменного разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но поскольку вероятность технических ошибок все равно существует, издательство
не может гарантировать абсолютную точность и правильность приводимых
сведений. В связи с этим издательство не несет ответственности за возможные
ошибки, связанные с использованием книги.

ISBN 978-0-470-22905-7 (анг.)
ISBN 978-5-97060-010-8 (рус.)

© 2008 by Wiley Publishing, Inc.
© Оформление, перевод,
ДМК Пресс, 2014
© Перевод с анг. Борисов Е. В.,
Чернышов Л. Н., 2013

Содержание
Введение .........................................................................7
Часть I. Основы .............................................................. 15
Глава 1. Прах Диофанта покоится в этой могиле .......... 16
Глава 2. Иррациональные и трансцендентные числа .... 27
Глава 3. Столетия прогресса ........................................ 53
Часть II. Вычислимые числа ............................................ 76
Глава 4. Годы учебы ...................................................... 77
Глава 5. Машины в работе ........................................... 99
Глава 6. Сложение и умножение ................................ 117
Глава 7. Они же – подпрограммы ............................... 132
Глава 8. Всё есть число .............................................. 148
Глава 9. Универсальная машина ................................ 165
Глава 10. Вычислительные машины и вычислимость ... 186
Глава 11. О машинах и людях ..................................... 215
Часть III. Entscheidungsproblem ..................................... 227
Глава 12. Логика и вычислимость ............................... 228
Глава 13. Вычислимые функции ................................. 263
Глава 14. Главное доказательство .............................. 292
Глава 15. Лямбда-исчисление .................................... 315
Глава 16. Постижение континуума .............................. 336

6

 Содержание

Часть IV. И далее ........................................................... 363
Глава 17. Весь мир – машина Тьюринга? .................... 364
Глава 18. Долгий сон Диофанта.................................. 396
Избранная библиография ............................................ 406
Дополнение: Машины Тьюринга, их разновидности
и моделирование (Л. Н. Чернышов) .............................. 411

Введение
Все, кто изучали историю, технологию или теорию вычислительных
машин, вероятно, сталкивались с понятием машины Тьюринга. Машина Тьюринга – это воображаемый, не совсем даже гипотетический,
компьютер, изобретенный в 1936 году английским математиком Аланом Тьюрингом (1912–1954) для того, чтобы помочь решить проблему математической логики. В качестве побочного продукта Тьюринг
создал новое поле исследований, известное как теория вычислений
или вычислимость, которая изучает возможности и ограничения
компьютеров.
Хотя машина Тьюринга – довольно неправдоподобный компьютер, она полезна тем, что является чрезвычайно простой. Элементарная машина Тьюринга выполняет лишь несколько простых операций. Если бы эта машина делала чуть меньше, чем она делает, она не
делала бы вообще ничего. Однако за счет комбинаций этих простых
операций машина Тьюринга может выполнить любое вычисление, на
которое способен современный цифровой компьютер.
Разобрав компьютер до оснований, мы можем лучше понять --">