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

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

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

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

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-97060-
010-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) для того, чтобы помочь решить проблему 
математической логики. В качестве побочного продукта Тьюринг 
создал новое поле исследований, известное как теория вычислений 
или вычислимость, которая изучает возможности и ограничения 
компью теров. 
Хотя машина Тьюринга – довольно неправдоподобный компьютер, 
она полезна тем, что является чрезвычайно простой. Элементарная 
машина Тьюринга выполняет лишь несколько простых операций. 
Если бы эта машина делала чуть меньше, чем она делает, она не 
делала бы вообще ничего. Однако за счет комбинаций этих простых 
операций машина Тьюринга может выполнить любое вычисление, на 
которое способен современный цифровой компьютер. 
Разобрав компьютер до оснований, мы можем лучше понять его 
возможности и, что немаловажно, его ограничения. Задолго до того, 
как было показано, что может компьютер, Тьюринг доказал, чего он 
никогда не сможет сделать. 
Машина Тьюринга остается популярной темой для суждений 
и толкований. (Попробуйте набрать «машина Тьюринга» в вашем 
любимом поисковике в Интернете.) Однако я подозреваю, что оригинальная 
статья Алана Тьюринга, описывающая его изобретение, 
читается редко. Возможно, такое пренебрежение связано с ее заголовком «
О вычислимых числах применительно к Entscheidungsprob-
lem». Даже если вы можете выговорить без запинки это слово, сделав 
ударение на втором слоге и произнеся его как «шай», и знаете, что 
оно значит («проблема разрешимости»), у вас все же остается подозрение, 
что Тьюринг предполагает предварительное знакомство своего 
читателя с трудными немецкими математическими рукописями. 
Беглый просмотр статьи, где для обозначения состояний машины используется 
готический шрифт, отнюдь не помогает унять эти страхи. 
Так может ли читатель в наши дни взяться за статью, опубликованную 
70 лет назад в Трудах Лондонского математического общества, 
и остаться на плаву достаточно долго, чтобы в полной мере проникнуться 
ею и, возможно, даже получить от нее удовольствие? 

 Введение

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

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

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

1 Turing А. On Computable Numbers, with an Application to the Entscheidung-
sproblem. Proceedings of the London Mathematical Society, 2nd series, Vol. 42 
(1936), pp. 230–265. 
2 Turing А. On Computable Numbers, with an Application to the Entschei-
dungs 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.

Введение  11

 
 Часть III («Entscheidungsproblem») начинается совсем коротким 
введением в математическую логику и продолжается разбором 
оставшейся части статьи Тьюринга. 
 
 В части IV («И далее») обсуждается, как случилось, что машина 
Тьюринга стала важным инструментом для понимания 
компью теров, человеческого сознания и самой вселенной. 
Математическое содержание части III, конечно, гораздо сложнее, 
чем в предыдущих главах, и излагается в более быстром темпе. Те, 
кто не очень интересуется значением статьи Тьюринга для математической 
логики, могли бы даже при желании пропустить пять глав 
части III и перейти сразу к части IV. 
Эта книга затрагивает несколько больших разделов математики, 
включая вычислимость и математическую логику. Я выбрал и предпочел 
только наиболее важные для понимания статьи Тьюринга темы 
и понятия. Многие детали опущены, и эта книга не заменит глубины 
и строгости, которую вы найдете в книгах, специально посвященных 
вычислимости и логике. Те читатели, которые намерены глубже покопаться 
в этих захватывающих областях исследований, могут руководствоваться 
библиографией. 
За всю свою жизнь Алан Тьюринг опубликовал около 30 работ и ста-
тей1, но не написал ни одной книги. Две статьи Тьюринга стали причиной 
его неугасающей известности. Конечно же, первая из них – «О вычислимых 
числах». Вторая – гораздо менее техническая статья под 
названием «Вычислительные машины и интеллект» (опуб ликована 
в 1950 году), где Тьюринг придумал то, что теперь в искусственном интеллекте 
называется тестом Тьюринга. Суть его в том, что если машина 
может заставить нас поверить, что она – человек, то мы с большой вероятностью 
должны считать, что она обладает интел лектом. 
Машина Тьюринга и тест Тьюринга – это две заявки Алана Тьюринга 
на литературное и культурное бессмертие. На первый взгляд, 
они могут казаться двумя совершенно разными понятиями, но это 
не так. Машина Тьюринга – это, в сущности, попытка описать чисто 
механически действия человека, выполняющего математический ал-

1 Эти и другие документы доступны в четырехтомнике The Collected Works of 
A. M. Turing (Amsterdam: Elsevier, 1992, 2001). Большая часть очень ценного 
материала была собрана Б. Джеком Коуплендом (B. Jack Copeland) в The 
Essential Turing (Oxford University Press, 2004) и в Alan Turing’s Automatic 
Computing Engine (Oxford University Press, 2005). Первая книга содержит 
работы и статьи о машине Тьюринга, а вторая – о проекте компьютера ACE 
второй половины 1940-х годов.

 Введение

горитм; тест Тьюринга – это оценка человеком действий компьютера. 
С самых ранних своих математических исследований и до самых 
поздних Тьюринг изучал связь между человеческим разумом и вычислительной 
машиной способом, который продолжает оставаться 
захватывающим и побуждающим. 
Можно обсуждать работы Тьюринга, ничего не говоря о Тьюринге-
человеке, и многие учебники по вычислимости не утруждают себя 
подробностями его биографии. Я не счел это возможным здесь. Секретная 
работа Тьюринга по криптоанализу во время Второй мировой 
войны, его участие в перспективных компьютерных проектах, его размышления 
об искусственном интеллекте, его сексуальная ориентация, 
его арест и судебное преследование за преступление в «грязной 
непристойности» и его ранняя смерть в результате явного самоубийства 
в возрасте 41 года – все это заслуживает внимания. 
Моя работа по изложению основных фактов жизни Тьюринга была 
очень облегчена замечательной биографией Алан Тьюринг: Загадка 
(Simon & Schuster, 1983) английского математика Эндрю Ходжеса 
(род. 1949). Ходжес заинтересовался Тьюрингом отчасти из-за своего 
собственного участия в освободительном движении геев в 1970-х годах. 
Написанная Ходжесом биография вдохновила Хью Уайтмора на 
пьесу под названием Взлом кода (1986). На сцене и в сокращенной 
версии для телевидения в 1996 году роль Алана Тьюринга была исполнена 
Дереком Якоби. 
Подобно ранним английским математикам и компьютерным 
первопроходцам Чарльзу Бэббиджу (1791–1871) и Аде Лавлейс 
(1815–1852), Тьюринг стал символом компьютерного века. Премия 
Тьюринга – это ежегодная награда в 100 000 долларов, вручаемая Ассоциацией 
вычислительных машин (ACM) за большой вклад в вычислительную 
технику. Существуют язык программирования Тьюринг (
производный от Паскаля) и программное обеспечение «Мир 
Тьюринга» для сборки машин Тьюринга. 
Имя Тьюринга стало почти нарицательным в программировании, 
причем настолько, что А. К. Дьюдни смог озаглавить свои «Экскурсии 
по информатике» как Омнибус Тьюринга (Dewdney A. K. The Turing 
Omnibus: Excursions in Computer Science. Computer Science Press, 1989). 
Книга «Западная культура в век компьютеров» Дж. Дэвида Болтера 
называется Человек Тьюринга (Bolter J. D. Turing’s Man: Western Culture 
in the Computer Age. University of North Caroline Press, 1984), а критический 
анализ Брайена Ротмана традиционных математических 
понятий бесконечности До бесконечности получила забавный подза-