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

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

Читаем Тьюринга

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

The Annotated Turing

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

Charles Petzold

Читаем Тьюринга

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

Москва, 2023

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

2-е издание, электронное

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

П29
Петцольд, Чарльз.
Читаем Тьюринга. Путешествие по исторической статье Тьюринга о вычислимости и машинах Тьюринга / Ч. Петцольд ; пер. с англ. Е. В. Борисова, 
Л. Н. Чернышова. — 2-е изд., эл. — 1 файл pdf : 442 с. — Москва : ДМК Пресс, 
2023. — Систем. требования: Adobe Reader XI либо Adobe Digital Editions 
4.5 ; экран 10". — Текст : электронный.
ISBN 978-5-89818-307-3
Книга, которую вы держите в руках, принадлежит перу известного американского популяризатора Чарлза Петцольда. В ней автор исследует главную работу Алана 
Тьюринга, посвященную проблеме разрешимости. Именно в этой работе впервые 
появились знаменитые машины Тьюринга, ставшие на многие годы универсальной 
теоретической концепцией computer science.
Автор тонко и деликатно проведет вас по самым потаенным уголкам, из которых 
родились на свет современные компьютеры и современное программное обеспечение.
Читателя ждет захватывающее путешествие в прошлое, из которого получилось 
наше настоящее и развивается будущее.

УДК 004.3.01:510.5 
ББК 32.97

Электронное издание на основе печатного издания: Читаем Тьюринга. Путешествие по исторической статье Тьюринга о вычислимости и машинах Тьюринга /  Ч. Петцольд ; пер. с англ. 
Е. В. Борисова, Л. Н. Чернышова. — Москва : ДМК Пресс, 2014. — 442 с. — ISBN 978-5-97060010-8. — Текст : непосредственный.

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

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами 
защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.

ISBN 978-5-89818-307-3
©  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

 Содержание

Часть IV. И далее ........................................................... 363

Глава 17. Весь мир – машина Тьюринга? .................... 364

Глава 18. Долгий сон Диофанта .................................. 396

Избранная библиография  ............................................ 406

Дополнение: Машины Тьюринга, их разновидности 
и моделирование (Л. Н. Чернышов) .............................. 411

Введение

Все, кто изучали историю, технологию или теорию вычислительных 
машин, вероятно, сталкивались с понятием машины Тьюринга. Машина Тьюринга – это воображаемый, не совсем даже гипотетический, 
компьютер, изобретенный в 1936 году английским математиком Аланом Тьюрингом (1912–1954) для того, чтобы помочь решить проблему математической логики. В качестве побочного продукта Тьюринг 
создал новое поле исследований, известное как теория вычислений 
или вычислимость, которая изучает возможности и ограничения 
компью теров. 
Хотя машина Тьюринга – довольно неправдоподобный компьютер, она полезна тем, что является чрезвычайно простой. Элементарная машина Тьюринга выполняет лишь несколько простых операций. Если бы эта машина делала чуть меньше, чем она делает, она не 
делала бы вообще ничего. Однако за счет комбинаций этих простых 
операций машина Тьюринга может выполнить любое вычисление, на 
которое способен современный цифровой компьютер. 
Разобрав компьютер до оснований, мы можем лучше понять его 
возможности и, что немаловажно, его ограничения. Задолго до того, 
как было показано, что может компьютер, Тьюринг доказал, чего он 
никогда не сможет сделать. 
Машина Тьюринга остается популярной темой для суждений 
и толкований. (Попробуйте набрать «машина Тьюринга» в вашем 
любимом поисковике в Интернете.) Однако я подозреваю, что оригинальная статья Алана Тьюринга, описывающая его изобретение, 
читается редко. Возможно, такое пренебрежение связано с ее заголовком «О вычислимых числах применительно к Entscheidungsproblem». Даже если вы можете выговорить без запинки это слово, сделав 
ударение на втором слоге и произнеся его как «шай», и знаете, что 
оно значит («проблема разрешимости»), у вас все же остается подозрение, что Тьюринг предполагает предварительное знакомство своего читателя с трудными немецкими математическими рукописями. 
Беглый просмотр статьи, где для обозначения состояний машины используется готический шрифт, отнюдь не помогает унять эти страхи. 
Так может ли читатель в наши дни взяться за статью, опубликованную 70 лет назад в Трудах Лондонского математического общества, 
и остаться на плаву достаточно долго, чтобы в полной мере проникнуться ею и, возможно, даже получить от нее удовольствие? 

 Введение

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

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

Мы (то есть мой издатель и я) попытались сохранить типографский набор и верстку оригинальной статьи, за исключением некоторых причуд (таких, как пробелы перед двоеточиями), которые вызывали «панику» в современных текстовых редакторах. Сохранены 
все оригинальные разрывы строк. В статье Тьюринга есть несколько 
опечаток, ошибок и пропусков. Они оставлены без изменений, но 
я обращаю на них внимание в своих комментариях. Тьюринг часто 

1 Turing А. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2nd series, Vol. 42 
(1936), pp. 230–265. 
2 Turing А. On Computable Numbers, with an Application to the Entscheidungs problem. A Correction, Proceedings of the London Mathematical Society, 
2nd series, Vol. 43 (1937), pp. 544–546. 
3 Alonzo Church, review of «On Computable Numbers, with an Application to 
the Entscheidungsproblem», The Journal of Symbolic Logic, Vol. 2, No. 1 (Mar. 
1937), 42–43.

Введение  9

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

Если буквы заменить числами, как в §5, мы получим числовое 
[243] 
описание полной конфигурации, которое можно назвать ее описательным номером. 

Это – конец одной и начало следующей страницы оригинала с ее 
номером. Мои сноски – номерные; сноски Тьюринга – символьные и 
тоже оттенены фоном. Если вы удалите страницы этой книги, вырезав и 
выбросив все, что не затенено, а потом склеите вместе остатки, у вас получится полная статья Тьюринга и один несчастный автор. Но гораздо 
интереснее, наверное, сначала прочитать эту книгу, а потом вернуться 
назад и прочитать саму статью Тьюринга без моих грубых вмешательств. 
Статья Тьюринга расположена на страницах 84–362 этой книги, 
а исправления к ней – на страницах 349–362. Статья Тьюринга делится на 11 разделов (и приложение), которые начинаются на следующих страницах книги: 

1. Вычислительные машины
68 
2. Определения
72 
3. Примеры вычислительных машин
79 
4. Сокращенные таблицы
113 
5. Перечисление вычислимых  последовательностей
131 
6. Универсальная вычислительная машина
143 
7. Подробное описание универсальной машины
149 
8. Применение диагонального процесса
173 
9. Пространство вычислимых чисел
190 
10. Примеры больших классов вычислимых чисел
235 
11. Применение к Entscheidungsproblem
260 
Приложение
290 

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

 Введение

ний в математической логике. Нахождение этого «общего процесса» 
было известно как Entscheidungsproblem (с нем. – «решаемость задачи»). Хотя побуждением к написанию статьи для Тьюринга была, 
конечно же, Entscheidungsproblem, на деле бо' льшая часть статьи – 
о вычислимых числах. По определению Тьюринга, это числа, которые 
могут быть вычислены машиной. Исследование вычислимых чисел 
составляет первые 60% статьи Тьюринга, которые могут быть прочитаны и поняты без знания работ Гильберта по математической логике 
или Entscheidungsproblem. 
Различие между вычислимыми числами и «вещественными числами» крайне важно для изложения Тьюринга. По этой причине первые 
главы данной книги представляют собой предварительную подготовку к нашей классификации чисел, охватывающей целые числа, рациональные числа, иррациональные числа, алгебраические числа и трансцендентные числа, все из которых относятся также к вещественным 
числам. Я старался не полагаться на какие-либо предварительные 
знания, более сложные, чем математика средней школы. Понимая, что 
некоторых читателей от радостей средней школы могут отделять несколько десятилетий, я попытался освежить эти воспоминания. Прошу простить, если мое педагогическое рвение привело к таким объяснениям, которые унижают или оскорбляют кого-то. 
Хотя я подозреваю, что эта книга будет читаться главным образом 
специалистами по информатике, программистами и прочими «технарями», я постарался доставить радость и непрограммистам, используя дружелюбный жаргон и терминологию из области искусства. 
Статья Тьюринга – это «один из интеллектуальных ориентиров прошедшего столетия»1, и я надеюсь, что данная книга сделает эту статью 
доступной еще более широкой аудитории. 
Чтобы угодить запросам разных читателей, я поделил эту книгу на 
четыре части: 
 
 Часть I («Основы») охватывает исторический и математический фон, который необходим, чтобы приступить к чтению 
статьи Тьюринга. 
 
 Часть II («Вычислимые числа») содержит бо' льшую часть 
статьи  Тьюринга и будет особенно полезна читателям, интересующимся машиной Тьюринга и вопросами вычислимости. 

1 John P. Burgess, предисловие к George S. Boolos, John P. Burgess, and Richard 
C. Jeffrey, Computability and Logic, fourth edition (Cambridge University Press, 
2002), xi.