Читаем Тьюринга [Чарльз Петцольд] (pdf) читать онлайн

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

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

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

8

 Введение

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

2

3

Turing А. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2nd series, Vol. 42
(1936), pp. 230–265.
Turing А. On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction, Proceedings of the London Mathematical Society,
2nd series, Vol. 43 (1937), pp. 544–546.
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. Вычислительные машины
2. Определения
3. Примеры вычислительных машин
4. Сокращенные таблицы
5. Перечисление вычислимых последовательностей
6. Универсальная вычислительная машина
7. Подробное описание универсальной машины
8. Применение диагонального процесса
9. Пространство вычислимых чисел
10. Примеры больших классов вычислимых чисел
11. Применение к Entscheidungsproblem
Приложение

68
72
79
113
131
143
149
173
190
235
260
290

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

10  Введение
ний в математической логике. Нахождение этого «общего процесса»
было известно как 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-х годов.

12  Введение
горитм; тест Тьюринга – это оценка человеком действий компьютера. С самых ранних своих математических исследований и до самых
поздних Тьюринг изучал связь между человеческим разумом и вычислительной машиной способом, который продолжает оставаться
захватывающим и побуждающим.
Можно обсуждать работы Тьюринга, ничего не говоря о Тьюринге-человеке, и многие учебники по вычислимости не утруждают себя
подробностями его биографии. Я не счел это возможным здесь. Секретная работа Тьюринга по криптоанализу во время Второй мировой
войны, его участие в перспективных компьютерных проектах, его размышления об искусственном интеллекте, его сексуальная ориентация, его арест и судебное преследование за преступление в «грязной
непристойности» и его ранняя смерть в результате явного самоубийства в возрасте 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), а критический анализ Брайена Ротмана традиционных математических
понятий бесконечности До бесконечности получила забавный подза-

Введение  13
головок «Призрак в машине Тьюринга» (Rotman В. Ad Infinitum: The
Ghost in Turing’s Machine. Stanford University Press, 1993).
Алан Тьюринг вызывал некоторый научный интерес и за пределами
математики и информатики. Сборник Новый взгляд: Странные толкования в фантастике (Novel Gazing: Queer Readings in Fiction, Duke
University Press, 1997) содержит эссе Тайлера Кертина под заглавием
«'Дурман' машин: Neuromancer, интернет-сексуальность и тест Тьюринга» (Tyler Curtain. The ‘Sinister Fruitiness’ of Machines: Neuromancer,
Internet Sexuality, and the Turing Test). Заголовок доктора Кертина
ссылается на известный «киберпанк»-роман Уильяма Гибсона Neuromancer (Gibson W. Neuromancer. Ace, 1984), в котором полиция Тьюринга помогает убедиться в том, что существа с искусственным интеллектом не стремятся повысить свой собственный интеллект.
Тьюринг появлялся в названиях еще нескольких романов. Марвин
Минский (известный исследователь MIT в области искусственного
интеллекта) сотрудничал с писателем-фантастом Гарри Харрисоном в Варианте Тьюринга (Harry Harrison, Marvin Minsky. The Turing
Option. Warner Books, 1992), а профессор информатики из Беркли
Христос Х. Пападимитриу разрешился сочинением Тьюринг (Роман
о вычислении) (Christos H. Papadimitriou. Turing (A Novel About Computation. MIT Press, 2003).
В Бреде Тьюринга боливийского романиста Эдмундо Пас Сольдена (Solda' n Edmundo Paz. Turing’s Delirium. Trans. Lisa Carter. Houghton Mifflin, 2006) криптоаналитик по прозвищу Тьюринг вскрывает
опасности использования его навыков для коррумпированного правительства. В романе Жанны Левин Сумасшедшие мечты машин Тьюринга (Levin Janna. A Madman Dreams of Turing Machines. Knopf, 2006)
вымышленные жизни Алана Тьюринга и Курта Гёделя странно взаимодействуют в пространстве и времени.
Алан Тьюринг – персонаж книг Криптономикон Нила Стефенсона
(Stephenson Neal. Cryptonomicon. Avon, 1999), Загадка Роберта Харриса
(Harris Robert. Enigma. Hutchinson, 1995), Кембриджский Квинтет: Работа научного предположения Джона Л. Касти (Casti John L. The Cambridge Quintet: A Work of Scientific Speculation. Perseus Books, 1998) и,
конечно, Гёдель, Эшер, Бах Дугласа Хофштадтера (Hofstadter Douglas.
..
Gоdel, Escher, Bach. Basic Books, 1979). От лица Алана Тьюринга ведется рассказ в новелле «Доктор Кто» Пола Леонарда – одной из частей
Теста Тьюринга (Leonard Paul. Dr. Who. The Turing Test, BBC, 2000).
Хоть и приятно, что Алан Тьюринг почитается такими разными
способами, существует опасность, что настоящая работа Тьюринга

14  Введение
окажется забытой. Даже тех, кто изучал теорию вычислений и полагает, что знает о машинах Тьюринга все, ждет, я надеюсь, несколько
сюрпризов при знакомстве с самой первой машиной Тьюринга, построенной самим автором.
***
Эта книга была задумана в 1999 году. Потом в течение следующих
пяти лет я писал понемногу и нерегулярно. Первые одиннадцать глав
в основном были закончены в 2004 и 2005 годах. Последние семь глав
я написал в 2007 и 2008 годах, прервав работу лишь для того, чтобы
жениться (наконец!) на моей давней лучшей подруге и любви моей
жизни Дирдре Синнотт.
Большое спасибо Лондонскому математическому обществу за
разрешение перепечатать в полном объеме статью Алана Тьюринга
«О вычислимых числах применительно к Entscheidungsproblem».
Уолтер Вильямс и Ларри Смит прочли ранние черновики этой
книги, обнаружив ряд ошибок и предложив несколько полезных
улучшений.
Людям из Wiley я вечно благодарен за их работу по превращению
этого любимого моего проекта в реально изданную книгу. Крис Вебб
продвигал книгу, исполняющий редактор Кристофер Ривера и производственный редактор Анджела Смит решили множество конструктивных и типографских проблем, а технический редактор Питер
Бонфэнти помог мне приложить чуть больше усердия к техническим
материалам. Многие из Wiley работали бескорыстно, помогая сделать
эту книгу как можно лучше. Все остальные недостатки, недочеты или
ужасные ошибки можно отнести только к автору.
Любой автор стоит на плечах тех, кто пришел раньше. В избранной библиографии перечислены лишь несколько из множества книг,
которые помогали мне при написании этой книги. Кроме того, я хотел бы поблагодарить персонал Публичной библиотеки Нью-Йорка и
особенно Библиотеку по науке, промышленности и бизнесу (Science,
Industry, and Business Library, SIBL). Для получения оригинальных
статей я широко пользовался JSTOR и обнаружил, что Wikipedia,
Google Book Search и MathWorld Уолфрэма тоже полезны.
***
Информацию и ресурсы, относящиеся к этой книге, можно найти
на веб-сайте www.TheAnnotatedTuring.com.
Чарльз Петцольд,
Нью-Йорк Сити и Роско, Нью-Йорк
Май, 2008

Часть

I
Основы

Глава

1
Прах Диофанта
покоится
в этой могиле

Много веков назад в древней Александрии старик должен был хоронить своего сына. Убитый горем, он утешал себя составлением большого сборника алгебраических задач с решениями в книге, названной им Арифметика (Arithmetica). Вот, пожалуй, и все, что известно
о Диофанте из Александрии, и большая часть этого исходит от загадки, которая, как полагают, была написана его близким другом вскоре
после его смерти1:
Прах Диофанта покоится в этой могиле. И она, о чудо, искусно поведает
нам, сколь долог был его век. Шестую часть жизни Бог одарил его детством; когда минула еще одна двенадцатая часть, пушком покрылись его
щеки; спустя седьмую долю жизни, Он зажег его брачную свечу, а на пятом году его брака Он послал ему сына. Увы, поздний и слабый ребенок,
достигнув половины жизни отца своего, был забран холодной могилой.
Еще четыре года горе свое утешал он наукой о числах, и тут конца жизни
своей он достиг2.

Эпитафия немного неоднозначна в отношении смерти сына Диофанта. Как в ней сказано, тот умер, «достигнув половины жизни отца
своего», но что значит эта половина жизни отца – половина возраста
Диофанта – момент смерти его сына или на момент его собственной
смерти? Задачу можно решать любым способом, но вторая версия –
сын Диофанта прожил половину лет, которые в итоге прожил сам
1

2

Thomas L. Heath, Diophantus of Alexandria: A Study in the History of Greek
Algebra, second edition (Cambridge University Press, 1910; Dover Publications,
1964), 3.
Greek Mathematical Works II: Aristarchus to Pappus of Alexandria (Loeb Classical
Library No. 362), translated by Ivor Thomas (Harvard University Press, 1941),
512–3.

Глава 1. Прах Диофанта покоится в этой могиле 

17

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

Наименьшее общее кратное знаменателей этих дробей – 84, поэтому умножим на него все члены уравнения слева и справа:
14x + 7x + 12x + 420 + 42x + 336 = 84x.
Собрав множители x в левой части, а константы – в правой, получим:
84x – 14x – 7x – 12x – 42x = 420 + 336.
Или:
9x = 756.
А само решение:
x = 84.
Итак, до 14 лет Диофант был мальчиком, а через 7 лет смог, наконец, отрастить бороду. Спустя двенадцать лет, в возрасте 33 года, он женился, а через 5 лет у него родился сын. Сын умер в возрасте 42 года, когда Диофанту было 80, а сам Диофант умер 4 года
спустя.
На самом деле есть более быстрый способ решения этой загадки: если задуматься глубже, то можно понять, что у автора загадки
нет намерения утруждать нас дробными числами. «Двенадцатая
часть» и «седьмая часть» жизни Диофанта должны быть целыми
числами, поэтому возраст в год его смерти делится одинаково и
на 12, и на 7 (и еще на 6 и на 2). Вот и умножьте 12 на 7, чтобы
получить 84. Для зрелого возраста это близко к истине и потому,
наверно, правильно.
Возможно, Диофант умер в 84 года, но крайне важный исторический вопрос – когда? Когда-то оценки периода жизни Диофанта

18  Часть I. Основы
колебались от 150 года до н. э. до 280 года н. э.1 Это довольно расплывчатый диапазон: он определенно ставит Диофанта после таких
ранних александрийских математиков, как Евклид (блистал ок. 295 г.
до н. э.2) и Эратосфен (ок. 276–195 г. до н. э.), но может сделать его
современником Герона Александрийского (известного и как Герой и
блиставшего в 62 г. н. э.), который написал книги по механике, пневматике и автоматах и, видимо, изобрел прообраз парового двигателя.
Возможно, Диофант знал и александрийского астронома Птолемея
(ок. 100–170 г. н. э.), известного главным образом по Альмагесту,
содержавшему первую тригонометрическую таблицу и заложившему основы математики движения небесных тел, которая не была
убедительно опровергнута вплоть до революции Коперника в XVI–
XVII веках.
К сожалению, у Диофанта, видимо, не было контактов с другими
александрийскими математиками и учеными. В последние примерно
сто лет исследователи сходятся во мнении, что Диофант творил около 250 года н. э., и его самый главный труд Арифметика датируется,
скорее всего, этим временем. Так что время рождения Диофанта приходится примерно на время смерти Птолемея. Пол Теннери, который
редактировал каноническое греческое издание Арифметики (издано
в 1893–1895 гг.), отмечал, что работа была посвящена «уважаемому
Дионисию». Несмотря на распространенное имя, Теннери догадался,
что это был тот самый Дионисий, который был главой школы Катехизиса в Александрии в 232–247 годах, а затем Епископом Александрийским в 248–265 годах. Таким образом, Диофант мог быть христианином3. Если это так, то можно усмотреть злую иронию в том, что
один из ранних (но потерянных) комментариев к Арифметике был
написан Ипатией (Hypatia) (ок. 370–415 гг.), дочерью Теона (Theon)
и последней из великих александрийских математиков, которая была
забита толпой христиан, настроенной против ее «языческой» философии.
Математика Древней Греции была традиционно сильнейшей в геометрии и астрономии. Диофант был этническим греком, но его отли1

2
3

Эти даты до сих пор сохраняются в Simon Hornblower and Antony Sprawforth, eds., Oxford Classical Dictionary, revised third edition (Oxford University
Press, 2003), 483.
Все остальные даты александрийских математиков – из Charles Coulston
Gillispie, ed., Dictionary of Scientific Biography (Scribners, 1970).
Heath, Diophantus of Alexandria, 2, note 2. Сам же автор этой книги, похоже,
сомневается в этом.

Глава 1. Прах Диофанта покоится в этой могиле 

19

чало то, что он утешал свое горе после смерти сына «наукой о числах»,
или, как мы теперь ее называем, алгеброй. Видимо, от него исходит
несколько алгебраических новшеств, включая использование символов и сокращений, означавших переход от словесной формулировки
задачи к современной алгебраической нотации.
Шесть книг Арифметики (считается, что изначально их было 13)
представляют собой задачи нарастающей сложности, большинство из
которых едва ли труднее, чем загадка о возрасте Диофанта. Нередко
задачи Диофанта имеют много неизвестных. Некоторые из его задач
неопределенны, то есть имеют более одного решения. Все, кроме одной, задачи из Арифметики абстрактны в том смысле, что они строго
числовые и не относятся к объектам реального мира.
Еще один элемент абстракции у Диофанта – возведение в степень.
До того времени математикам были известны степени 2 и 3. Квадраты
были нужны для вычисления площадей, а кубы – для вычисления
объемов тел. Но Диофант допускал в своих задачах и более высокие
степени: степень 4 (которую он назвал «квадрат квадрата»), 5 («квадрат куба») и 6 («куб куба»). Такие степени не имели физической аналогии в мире, который был известен Диофанту, и указывали на то,
что Диофант не очень беспокоился о практичности своей математики. Это была просто занимательная математика без цели, но для развития ума.
Вот первая задача из Книги IV1. Диофант формулирует ее сначала
общими словами:
Разделить заданное число на два куба так, чтобы сумма их сторон была
равна другому заданному числу.

Затем он задает эти два числа:
Заданное число – 370, заданная сумма сторон – 10.

Геометрически он имеет дело с двумя кубами разных размеров. Как
современные алгебраисты, мы с вами могли бы обозначить стороны
двух кубов x и y:

1

Heath, Diophantus of Alexandria, 168.

20  Часть I. Основы
Эти две стороны (x и y) составляют в сумме 10. Объемы двух кубов
(x3 и y3) в сумме дают 370. Теперь запишем два уравнения:
x + y = 10;
x3 + y3 = 370.
Из первого уравнения следует, что y равно (10 – x), и его можно
подставить во второе уравнение:
x3 + (10 – x)3 = 370.
Теперь трижды перемножаем (10 – x) и уповаем, чтобы кубы в конечном счете сократились:
x3 + (1000 + 30x2 – 300x – x3) = 370.
К счастью, так и происходит, и после небольших группировок получаем:
30x2 – 300x + 630 = 0.
Коэффициенты в левой части имеют общий множитель, поэтому
желательно сократить обе части на 30:
x2 – 10x + 21 = 0.
Теперь все почти готово. У нас есть два варианта. Если вспомнить
формулы квадратных уравнений1, то можно применить их. Или если
еще свеж опыт решения подобных уравнений, можно, пристально
взглянув на него и подумав некоторое время, разложить его, как по
волшебству, следующим образом:
(x – 7) (x – 3) = 0.
Таким образом, длины двух сторон – 7 и 3. В сумме они дают 10,
а их кубы – 343 и 27 – дают в сумме 370.
Диофант решает задачу совсем не так, как мы с вами. В сущности,
он этого просто не может сделать. Хотя часто в задачах Диофанта
много неизвестных, его система обозначений позволяет ему представлять только одно неизвестное. Однако он очень изобретательно восполняет данный недостаток. Вместо того чтобы обозначать стороны
двух кубов как x и y, он говорит, что эти две стороны равны (5 + x) и
(5 – x). Две эти стороны выражаются посредством одного неизвест1

Для ax2 + bx + c = 0 решение x =

Глава 1. Прах Диофанта покоится в этой могиле 

21

ного x, и они на самом деле дают в сумме 10. Тогда он может возвести
их в куб и приравнять сумму к 370:
(5 + x)3 + (5 – x)3 = 370.
Теперь это выглядит хуже того, с чем мы уже сталкивались, но стоит только развернуть кубические скобки, как члены уравнения начинают сокращаться, как сумасшедшие, и у нас остается лишь:
30x2 + 250 = 370.
После некоторых простейших перегруппировок и последующего
деления на 30 оно сводится к
x2 = 4.
Или x равняется 2. Так как стороны – это (5 + x) и (5 – x), то их
величины – 7 и 3.
Умение Диофанта решать такие задачи с меньшими, чем современный студент, усилиями – результат его потрясающей способности выражать должным образом две величины посредством одной
переменной. Сработает ли этот метод в следующей задаче? Может,
да. А может, нет. Разработка общих методов решения алгебраических
уравнений – это то, чего у Диофанта, по сути дела, нет вообще. Как
заметил один математик, «каждый вопрос требует весьма специфического метода, который зачастую не пригоден даже для очень близких
задач. Именно поэтому современному математику даже после изучения ста диофантовых задач будет трудно решить сто первую»1.
Понятно, что когда Диофант предлагает задачу с суммой кубов
370 и суммой сторон 10, он, конечно же, берет числа не с потолка. Он
знает, что эти условия приводят к решению в целых числах. Действительно, термин диофантово уравнение появился для обозначения
алгебраического уравнения, где допустимы только целочисленные
решения. Диофантовы уравнения могут иметь множество неизвестных, и эти неизвестные могут возводиться в целочисленные степени,
однако решения (если они есть) – всегда целочисленные. Несмотря
на то что при формулировке своих задач Диофант часто использует
вычитание, его решения никогда не содержат отрицательных чисел.
«Очевидно, что об отрицательных величинах как таковых, то есть без
1

Это цитата Германа Ганкеля (Hermann Hankel) (1874) из книги Heath,
Diophantus of Alexandria, 54–55. Другие математики обнаружили общие подходы в методах Диофанта. См. Bashmakova I. G. Diophantus and
Diophantine Equations (Mathematical Association of America, 1997), ch. 4.

22  Часть I. Основы
некоего положительного значения, которое вычитается из чего-то,
Диофант понятия не имел»1. Так же, как не было у него ни одной задачи с нулевым решением. Ноль у древних греков не считался числом.
Современные читатели Диофанта – особенно те, кто уже знают,
что диофантовы уравнения имеют лишь целочисленные решения, –
могут слегка удивиться, обнаружив у Диофанта рациональные числа.
Рациональными их называют не потому, что они логичны или разумны в некотором смысле, а потому, что их можно представить как отношение (ratio) двух целых чисел. Например,

– рациональное число.
Рациональные числа появляются лишь в одной задаче Арифметики, которая содержит настоящие объекты реального мира, особенно
такие вечно любимые, как вино и деньги. В условии задачи рациональных чисел будто бы нет, но они потребуются при ее решении:
Человек покупает некоторое количество мер вина: одно вино – по 8, другое – по 5 драхм за меру. Он платит за них квадратное число драхм; а если
мы добавим к этому числу 60, то получим квадрат, сторона которого есть
целое число мер. Определите, сколько мер он купил по каждой цене2.

Под «квадратным числом» Диофант понимает результат умножения некоторого числа на себя. Например, 25 – это квадратное число,
так как оно равно 5 раз по 5.
После страницы расчетов3 оказывается, что количество мер по
5 драхм – это рациональное число

а количество мер по 8 драхм – это рациональное число

Давайте проверим эти результаты. (Проверить решение гораздо
легче, чем найти его.) Если умножить 5 драхм на 79/12 и добавить
к этому произведение 8 драхм на 59/12, получится, что человек за1
2
3

Heath, Diophantus of Alexandria, 52–53.
Heath, Diophantus of Alexandria, 224.
Heath, Diophantus of Alexandria, 225.

Глава 1. Прах Диофанта покоится в этой могиле 

23

платил в общей сложности 721/4 драхмы. Диофант утверждает, что
человек заплатил «квадратное число драхм», то есть плата должна
быть квадратом чего-то. Довольно любопытно, что Диофант считает
721/4 квадратным числом, раз оно может быть выражено отношением

где и числитель, и знаменатель – квадраты 17 и 2 соответственно. Таким образом, 721/4 – квадрат 17/2, или 81/2. Дальше Диофант говорит,
что «если мы добавим к этому числу 60, то получим квадрат, сторона
которого есть целое число мер». И здесь «целое число мер» не связано
с целыми числами. Диофант (или, точнее, его английский переводчик
сэр Томас Хит (Thomas Heath)) подразумевает под этим общее число мер. Добавление 60 к 721/4 дает в результате рациональное число
1321/4, или

И снова Диофант считает, что это квадрат, потому что и числитель,
и знаменатель – квадраты 23 и 2 соответственно. Таким образом, общее число купленных мер – 23/2, или 111/2, что можно также получить сложением 79/12 и 59/12.
Наверное, самая известная задача в Арифметике – это задача 8 из
Книги II: «Разбить заданное квадратное число на два квадрата», то
есть найти такие x, y и z, что
x2 + y2 = z2.
У этой задачи есть геометрическая интерпретация, связанная с теоремой Пифагора о соотношении сторон прямоугольного треугольника:

24  Часть I. Основы
Задача имеет множество решений в целых числах, например x, y и
z могут быть равны 3, 4 и 5 соответственно. (Сумма квадратов 9 и 16
дает 25.) Такое простое решение, видимо, не привлекает Диофанта,
и он, приняв «заданное квадратное число» (то есть z2) за 16, получает две другие величины в виде рациональных чисел 144/25 и 256/25.
Для Диофанта обе они – конечно же, квадраты. Первая – квадрат
12/5, вторая – квадрат 16/5, а сумма – квадрат 4:

На самом деле не имеет значения, что Диофант допускает решение
в рациональных числах, потому что оно равносильно решению в целых числах. Просто умножьте обе части уравнения на 52, или на 25:
122 + 162 = 202.
Или 144 плюс 256 равняется 400. Это, в сущности, то же самое решение, потому что это всего лишь другой способ измерения сторон.
В решении Диофанта гипотенуза равна 4. Это могли быть, скажем,
4 дюйма. Теперь воспользуемся другой линейкой с делениями в одну
пятую дюйма, и гипотенуза станет равной 20, а стороны – 12 и 16.
Целые числа появились, когда люди начали считать предметы. Рациональные числа, по всей видимости, появились, когда люди начали
измерять предметы. Если длина одной моркови – три пальца, а другой – четыре, то длина первой моркови – 3/4 длины второй.
Рациональные величины иногда называют соизмеримыми, потому
что два объекта с длинами, выраженными рациональными числами,
всегда могут быть перемерены в целых единицах. Нужно только сделать новую единицу измерения достаточно малой.
Диофант писал Арифметику на греческом языке. Какие-то части
его труда были переведены на арабский. Сначала, в 1575 году, их перевели на латынь, а затем, в 1621 году, они вышли в улучшенной редакции, когда к ним проявили интерес европейские математики. Пьер де
Ферма (1601–1665) имел собственную копию латинского перевода
1621 года, поля которой он испещрил своими обширными заметками.
В 1670 году сын Ферма издал эти заметки вместе с латинской Арифметикой. Одной такой заметкой сопровождалась и только что приведенная задача. Ферма писал:
С другой стороны, невозможно разделить куб на два куба, либо биквадрат
[степень 4] на два биквадрата, либо вообще любую степень, кроме квад-

Глава 1. Прах Диофанта покоится в этой могиле 

25

рата, – на две с тем же показателем степени. Я нашел этому поистине
изумительное доказательство, для которого, однако, поля не достаточно
велики1.

Ферма утверждает, например, что
x3 + y3 = z3
не имеет решений в целых числах, как не имеет их ни одно подобное
уравнение со степенями 4, 5, 6 и т. д. Вообще говоря, это не очевидно.
Уравнение
x3 + y3 + 1 = z3
очень и очень близко к
x3 + y3 = z3,
но оно имеет множество решений в целых числах, например когда x,
y и z равны 6, 8 и 9 соответственно. Уравнение
x3 + y3 – 1 = z3
тоже весьма похоже, но и оно имеет множество решений в целых числах, например 9, 10 и 12. Почему же эти два уравнения имеют решения в целых числах, а уравнение
x3 + y3 = z3
их не имеет?
Все задачи из Арифметики Диофанта имеют решения, но многие
диофантовы уравнения, как у Ферма, видимо, их не имеют. Вскоре
математикам стало интереснее не столько решать диофантовы уравнения, сколько определять, имеет ли вообще частное диофантово
уравнение решение в целых числах.
Несуществующее доказательство Ферма стало известно как Великая теорема Ферма (или Большая теорема Ферма), и долгие годы
было принято считать: что бы ни думал Ферма о своем доказательстве,
оно, скорее всего, неверно. Только в 1995 году Теорема Ферма была
доказана английским математиком Эндрю Уайлсом (род. в 1953 г.),
который интересовался этой проблемой с десяти лет. (Для многих
частных случаев, когда, например, показатель степени равен 3, отсутствие решения было установлено много раньше.)
Очевидно, доказательство того, что у некоторого диофантова уравнения нет приемлемого решения, гораздо привлекательнее, чем по1

Heath, Diophantus of Alexandria, 144, note 3.

26  Часть I. Основы
иск решения, когда известно, что оно есть. Если известно, что у частного диофантова уравнения есть решение, можно просто проверить
все возможности. Допустимые решения – только целочисленные,
поэтому начинаем пробовать 1, затем 2, 3 и т. д. Если же столь утомительная работа вам уже невмоготу, просто напишите компьютерную
программу, которая проверит за вас все возможности. Рано или поздно она найдет решение.
Но если неизвестно, что решение существует, компьютерный подход с позиций грубой силы совершенно не годится. Его можно начать,
но как узнать, когда его закончить? Как убедиться, что все последующие проверяемые наборы чисел будут совсем не тем, что мы ищем?
Всё проклятие чисел – в их бесконечности.

Глава

2

Иррациональные
и трансцендентные числа
Начав считать 1, 2, 3, мы можем продолжать настолько долго, насколько захотим. Такие числа известны как счетные, целые, кардинальные,
натуральные, и они, конечно, кажутся достаточно естественными и
интуитивно понятными, потому что вселенная содержит очень много
объектов, которые мы можем посчитать. Натуральные числа были,
вероятно, первыми математическими объектами, постигнутыми первобытными людьми. У некоторых животных, видимо, тоже есть понимание чисел, пока они не становятся слишком большими.
Нуль веками не входил в натуральный ряд чисел, и даже теперь здесь
нет твердого согласия. (Учебники по теории чисел обычно предупреждают на первой странице, включает ли автор нуль в натуральный ряд
чисел.) По другую сторону нуля – отрицательные целые числа. Ко
всем положительным и отрицательным целым числам, как и к нулю,
больше всего подходит слово целое (или целочисленное). Целые числа
уходят в бесконечность в двух противоположных направлениях:
… –3 –2 –1 0 1 2 3 …
Для обозначения только положительных целых чисел, начинающихся с 1, лучше всего подходит термин положительные целые. Для
положительных чисел, начинающихся с нуля (то есть 0, 1, 2, 3...),
однозначным и не слишком многословным будет термин неотрицательные целые.
Рациональные числа – это числа, которые могут быть выражены
отношением целых чисел (дробью), за исключением знаменателя 0.
Например,

– рациональное число, обычно записываемое и в десятичной форме:
0,6.

28  Часть I. Основы
Рациональные числа включают и все целые числа, потому что любое целое число (скажем, 47) может быть записано дробью со знаменателем 1:

Любое число с конечным числом десятичных разрядов – тоже рациональное. Например,
–23,45678
может быть представлено отношением:

Некоторые рациональные числа, например

требуют для представления в десятичной форме бесконечного количества цифр:
0,3333333333…
Это – все еще рациональное число, потому что оно – дробь. Более
того, любое число с повторяющимся набором цифр где-то после десятичной запятой – это рациональное число. Число
0,234562345623456…
– рациональное, если набор цифр 23456 повторяется бесконечно.
Чтобы показать, что оно – рациональное, давайте приравняем его к x:
x = 0,234562345623456...
Теперь умножим обе части равенства на 100 000:
100 000 x = 23 456,23456234562346…
Хорошо известно, что если вычесть одну и ту же величину из обеих
частей равенства, то равенство сохранится. Это значит, что можно вычесть из второго равенства первое: вычитаем x из 100 000x и 0,23456…
из 23 456,23456…, и десятичнаячасть исчезает:
99 999x = 23 456.

Глава 2. Иррациональные и трансцендентные числа 

29

Таким образом:

Это – отношение, а значит, рациональное число.
Только на первый взгляд кажется, что рациональные числа обладают совершенной полнотой. Если сложить два рациональных числа,
получится другое рациональное число. Вычитание, умножение или
деление рациональных чисел также дает в результате рациональное
число.
Можно было бы предположить (как многие годы считали люди),
что все числа – рациональные, но рассмотрим гипотенузу этого простого прямоугольного треугольника:

Согласно Теореме Пифагора,
x2 = 12 + 12,
или
x2 = 2,
или

Cуществует ли отношение двух целых чисел, которое, будучи
умноженным на себя, дает в результате 2? Конечно, можно поискать и
найти много рациональных чисел, которые дадут очень близкий к искомому результат. Одно из них:

30  Часть I. Основы
Правда, оно чуть меньше. Умноженное на себя, оно дает примерно
1,99995. Если мы продолжим поиски, то, возможно, найдем точное
решение.
Или мы зря тратим свое время?
Трудно доказывать, что чего-то не существует, но математики
придумали вид доказательства, которое часто подходит в подобных
случаях. Оно называется косвенным доказательством, или доказательством от противного, на латыни – reductio ad absurdum («сведение к нелепости»). Вы начинаете с предположения. Затем из этого
предположения вы делаете логические выводы, пока не «упираетесь»
в противоречие. Это противоречие означает, что первоначальное
предположение было неверным.
Доказательства reductio ad absurdum похожи на окольный путь, но
они, судя по всему, чаще, чем мы думаем, распространены в обычной
жизни. Алиби – разновидность reductio ad absurdum. Если ответчик
был на месте преступления и в доме своей матери, это значит, что он
был сразу в двух разных местах одновременно. Абсурд!
Давайте начнем с предположения, что квадратный корень из 2 –
рациональное число. А раз так, то существуют такие целые числа a и
b, что:

Являются ли a и b оба четными? Если да, разделим их оба на 2 и
заменим их половинами. Если и они – все еще четные, делим их тоже
на 2 и продолжим так до тех пор, пока или a, или b (или они оба) не
станет нечетным.
Возведем обе части уравнения в квадрат:

Или:
a2 = 2b2.
Заметим, что квадрат a вдвое больше квадрата b. Это означает, что
квадрат a четен, а это возможно лишь тогда, когда само число a – четное. Ранее мы установили, что a и b не могут быть оба четными, таким
образом, теперь мы знаем, что нечетно число b.
Если a – четное, то оно вдвое больше некоторого целого числа, которое мы обозначим c:

Глава 2. Иррациональные и трансцендентные числа 

31

(2c)2 = 2b2.
Или:
4c2 = 2b2.
Или:
2c2 = b2.
Это значит, что квадрат b – четное число, а раз так, то и b – тоже
четное, как и a, что противоречит первоначальному предположению
о том, что a и b не могут быть оба четными.
Следовательно, исходное предположение о том, что квадратный
корень 2 – рациональное число, неверно. Квадратный корень 2 – бесспорно, иррациональное число. В десятичной форме его цифры следуют без видимых повторов цепочек цифр:
1,4142135623730950488016887242097…
Это число невозможно записать точно, не имея бесконечных запасов бумаги, чернил и времени. Можно лишь приближаться к нему, и
многоточие – признание нашего поражения. Ближе всего можно подойти к этому числу с помощью алгоритма его вычисления. (Именно
это я и сделаю в главе 6.)
Как ни странно, есть причина, почему используемые нами термины – рациональный и иррациональный – выносят приговор здравомыслию чисел. Иногда иррациональные числа называют также несоизмеримыми (surds), с тем же корнем, что в слове абсурд (absurd).
Иррациональные числа были известны древним грекам, но те им
очень не нравились. Согласно преданию (но не достоверной истории), иррациональность квадратного корня из 2 установил в VI веке
до н. э. ученик Пифагора Гиппазий. Далее легенда гласит, что это открытие настолько возмутило логичных и рациональных греков, что
Пифагор и его последователи попытались погасить возмущение,
сбросив Гиппазия в Средиземное море. Им, конечно же, хотелось,
чтобы иррациональных чисел не было. Отказываясь в своих задачах
от иррациональных чисел, Диофант следовал древней традиции: иррациональные числа были ему совсем не по вкусу.
В десятичной записи, которая есть у нас (но которой не было
у древних греков), легко создавать числа, явно иррациональные. Достаточно лишь написать что-нибудь пикантное без повторений цифровых шаблонов. Вот, например, число с ненормальным, в некотором

32  Часть I. Основы
роде, шаблоном из десятичных цифр, который определенно не повторяется:
0,0010110111011110111110111111…
После десятичной запятой идут 00 и 1, потом – 0 и две 1, потом – 0
и три 1 и т. д. Это не рациональное число! Его нельзя представить отношением двух целых чисел. Поэтому оно иррационально.
Квадратный корень из 2 – это решение следующего уравнения:
x2 – 2 = 0.
Это то же уравнение, что было раньше, с разницей лишь в том, что
2 перенесено в левую его часть. Кубический корень из 17 (тоже иррациональный) – это решение следующего уравнения:
x3 – 17 = 0.
Оба эти уравнения называются алгебраическими уравнениями. Вот
другое алгебраическое уравнение:
–12x5 + 27x4 – 2x2 + 8x – 4 = 0.
В алгебраическом уравнении – одна переменная, обычно называемая x. (Алгебраические уравнения – это не диофантовы уравнения,
потому что диофантовы уравнения могут иметь много переменных.)
В алгебраическом уравнении – ряд членов (в последнем примере –
5), сумма которых равна нулю. Каждый член содержит переменную
в степени – целой или нулевой. (Поскольку нечто в нулевой степени
равняется 1, пятый член можно понимать как произведение –4 на нулевую степень x.) Каждая возведенная в степень переменная умножается на целочисленный коэффициент, в этом примере –12, 27, –2, 8
и –4. Коэффициенты могут быть нулевыми, что имеет место с «пропавшим» членом x3.
К алгебраическим уравнениям сводятся многие реальные задачи,
поэтому они считаются весьма важными. Общий вид алгебраического уравнения:
aNxN + aN–1xN–1 + … + a2x2 + a1x + a0 = 0,
где N – положительное целое число и аi – целые числа. Можно записать его короче в виде суммы:

Глава 2. Иррациональные и трансцендентные числа 

33

В приведенном выше уравнении
–12x5 + 27x4 – 2x2 + 8x – 4 = 0
N = 5 (это самый высокий показатель степени, называемый степенью многочлена), a5 = –12, a4 = 27, a3 = 0 и т. д.
Решения алгебраического уравнения (называемые также корнями
уравнения) называются алгебраическими числами. Многочлен степени N имеет не более N различных решений. Алгебраическое уравнение из главы 1
x2 – 10x + 21 = 0
подходит к этому определению. Оно имеет решения 3 и 7.
Квадратный корень из 2 – одно из решений алгебраического уравнения
x2 – 2 = 0.
Отрицательный квадратный корень из 2 – второе его решение.
Алгебраические числа включают в себя все целые и все рациональные числа. Например, целое число 5 является решением алгебраического уравнения
x – 5 = 0,
а 3/7 – решением уравнения
7x – 3 = 0.
Некоторые алгебраические уравнения имеют своим решением
квадратные корни из отрицательных чисел:
x2 + 5 = 0.
Это уравнение кажется неразрешимым, потому что любое умноженное на себя число – положительное, и добавление к нему 5 никогда не даст в результате нуль. Квадратные корни из отрицательных
чисел называются мнимыми (комплексными) числами. (Квадратному
корню из –1 для удобства назначен символ i.) Вопреки своему названию мнимые числа очень полезны и имеют практическое применение
в реальности, но их не будет ни в статье Тьюринга, ни в этой книге.
Примерно в XVIII веке в противовес мнимым числам математики
заговорили о вещественных (действительных) числах. По определению, вещественные числа включают все числа, кроме квадратных
корней из отрицательных чисел.

34  Часть I. Основы
Вещественные числа имеют также отношение к континууму, потому что вещественные числа можно представить как все точки непрерывной прямой:

На этой прямой отмечены некоторые целые числа, но очевидно,
что сами они не могут образовать непрерывную прямую.
Как не могут этого и рациональные числа. Конечно, рациональные числа заполняют прямую довольно плотно. Между любыми двумя рациональными числами, скажем, a и b, можно вставить другое
рациональное число – среднее арифметическое этих двух:

Однако между рациональными числами еще существуют промежутки, где обитают иррациональные числа. Например, один из таких
промежутков содержит квадратный корень из 2.
Теперь перейдем к теме классификации чисел с двух сторон. С одной стороны, мы определили класс алгебраических чисел, которые
являются решениями алгебраических уравнений. Этот класс чисел
включает целые, рациональные и многие иррациональные числа, такие как квадратные и кубические корни. С другой стороны, мы определили класс вещественных чисел, то есть всех чисел, которые не являются квадратными корнями из отрицательных чисел. Теперь сам
собой напрашивается следующий вопрос:
Являются ли все вещественные числа также алгебраическими? Или:
есть ли такие вещественные числа, которые не являются решениями
алгебраических уравнений?
В 1740-х годах Леонард Эйлер (1707–1783) – неутомимый швейцарский математик, чье имя произносится «Ойлер», – предположил, что неалгебраические числа действительно существуют, и
назвал их трансцендентными (от лат. transcendentis – запредельный. – прим. перев.) числами, потому что они выходят за пределы
алгебраических. Доказать существование трансцендентных чисел
было трудно. Как доказать, что конкретное число не является решением некоторого довольно длинного и замысловатого алгебраического уравнения?
Вопрос о существовании трансцендентных чисел оставался открытым вплоть до 1844 года, когда французский математик Жозеф Лиу-

Глава 2. Иррациональные и трансцендентные числа 

35

вилль (1809–1882) придумал число и смог доказать, что оно – неалгебраическое. Вот первые 30 десятичных разрядов числа Лиувилля:
0,110001000000000000000001000000…
Правда, этот фрагмент совсем не раскрывает всего числа. Лиувилль строит это «сумасшедшее» число с помощью факториалов.
Факториал числа – это произведение числа и всех положительных
целых чисел, не превышающих его самого, которое обозначается восклицательным знаком:
1! = 1
2! = 1  2 = 2
3! = 1  2  3 = 6
4! = 1  2  3  4 = 24
5! = 1  2  3  4  5 = 120
и т. д. Число Лиувилля (как его иногда называют) содержит 1 в разрядах с номерами 1, 2, 6, 24, 120 и т. д. Лиувилль создал это число именно
для того, чтобы доказать, что оно не является решением какого-либо
алгебраического уравнения. Нарастающее расстояние между ненулевыми цифрами числа – ключ к доказательству1.
В 1882 году немецкий математик Фердинанд Линдеман (1852–
1939) доказал, что одно из самых известных иррациональных чисел
всех времен – тоже трансцендентное. Это число  – отношение длины
окружности к ее диаметру:
 = 3,1415926535897932384626433832795…
Линдеман показал, что  не является решением алгебраического
уравнения, что позволило понять очень старую задачу: больше двух
тысячелетий математики, и не только они, бились над «квадратурой
круга». Задача ставится просто: дан круг; с помощью линейки и циркуля построить квадрат той же площади, что и круг. (Похожая задача
выпрямления окружности требует построения отрезка прямой линии
с длиной, равной длине окружности.) Люди так исступленно бились
над этой задачей, что древние греки даже окрестили эту навязчивую
идею словом , буквально тетрагония (tetragonize)2.
1

2

Доказательство обсуждается в Edward B. Burger and Robert Tubbs, Making
Transcendence Transparent: An Intuitive Approach to Classical Transcendental
Number Theory (Springer, 2004), 9–26.
Hobson E. W. Squaring the Circle: A History of the Problem (Cambridge University Press, 1913), 3.

36  Часть I. Основы
Использование линейки и циркуля для построения геометрических фигур равносильно решению алгебраических уравнений определенного вида. Поскольку  не является решением алгебраического
уравнения, его невозможно получить с помощью геометрических построений. Добиться квадратуры круга с помощью линейки и циркуля
невозможно.
Другое знаменитое трансцендентное число обозначается буквой e
(в честь Эйлера). Если вычислять это число по формуле

увеличивая значение N, можно получить следующее его приближение:
e = 2,7182818284590452353602874713527…
Можно также вычислить e, суммируя бесконечный ряд, содержащий факториалы:

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

На этой диаграмме не соблюден масштаб.

Глава 2. Иррациональные и трансцендентные числа 

37

Погодите, сейчас объясню, что я имею в виду.
Все эти классы чисел бесконечны. Верно? Есть бесконечное число
целых чисел, бесконечное число дробей, бесконечное число иррациональных чисел. Верно? Бесконечность – это бесконечность. Верно?
Но бесконечности не могут быть разного размера, не так ли? Разве
может быть одна бесконечность больше другой бесконечности?
Верно?
Тема бесконечности никогда не была простой, независимо от того,
с каких позиций – философских, теологических или математических – ее рассматривали. Однако в математике обойти стороной бесконечность вряд ли возможно. Мы вынуждены исследовать это понятие со всей смелостью, на какую только способны.
Бесконечное стремление натуральных чисел быть все больше и
больше, кажется, лежит в самом основании нашего понимания бесконечно большого. Досчитав до некоторого числа, мы всегда можем добавить к нему еще одну единицу. Конечно, вещественные числа тоже
могут становиться бесконечно большими, но лишь потому, что следуют по пятам натуральных чисел. Вещественные числа позволяют нам
задуматься и о бесконечно малых, когда мы делим континуум на все
меньшие и меньшие части.
Похожи ли в чем-то эти две бесконечности – бесконечность никогда не заканчивающихся натуральных чисел и бесконечность плотности континуума? Или же они совсем разные?
Последующее обсуждение будет несколько проще, если мы примем на вооружение некоторые элементы теории множеств. Множество – это совокупность объектов, которые называются элементами
множества. Множество обычно заключается в пару фигурных скобок.
Например,
{1, 2, 3, 4}
– множество из первых четырех положительных целых чисел. Элементы множества уникальны. Так, две четверки в одном и том же множестве недопустимы. Порядок следования элементов множества не
имеет значения. Множество
{4, 1, 3, 2}
равно предыдущему. Количество элементов множества называется
кардиналом, или мощностью, множества. Мощность конечного множества, приведенного выше, равна 4. Говорят, что множества одинаковой мощности равносильны (или равномощны. – прим. перев.).

38  Часть I. Основы
Одни множества имеют конечную мощность, другие – бесконечную. Рассмотрим множество положительных целых чисел:
{1, 2, 3...}.
Его мощность, определенно, бесконечна. То же самое верно для
множества положительных четных целых чисел:
{2, 4, 6...}.
Каково отношение между мощностями этих двух множеств?
Возможно, наше чутье подсказывает нам, что первое множество
содержит вдвое больше элементов, чем второе, потому что во втором
множестве отсутствуют все нечетные числа.
Конечно, это лишь одно из мнений, и оно было бы верно, если бы
два множества были конечными. Но можно ли говорить о том, что
одно множество «вдвое больше» другого, если оба они бесконечны?
Давайте попробуем посчитать элементы второго множества. Что на
самом деле значит посчитать? Это значит установить соответствие
между элементами множества и натуральным рядом чисел: водя носом по предметам, мы говорим «номер 1, номер 2, номер 3…».
Мы можем посчитать положительные четные целые числа в бесконечном множестве, соотнося каждому из них натуральное число:

Каждому положительному целому числу соответствует четное
число. Каждому четному числу соответствует положительное целое
число. При таком взгляде теперь выходит, что два множества имеют
одинаковые размеры, что означает их равносильность. Что это – парадокс или нет? (На самом деле эта странная особенность бесконечных множеств была замечена Галилеем еще в 1638 году1 и иногда называется парадоксом Галилея.)
Казалось, этот парадокс никого и нисколько не беспокоил до тех
пор, пока в схватку с ним не вступил Георг Кантор (1845–1918).
1

Galileo Galilei, Two New Sciences, second edition, trans. Stillman Drake (Wall &
Emerson, 2000), 40–41. Перевод основан на Opere di Galileo Galilei (Florence,
1898), VIII, 78–79. Вероятно, Галилей был не первым, кто обратил внимание на этот парадокс: дополнительно см. Stephen Cole Kleene, Mathematical
Logic (Wiley, 1967; Dover, 2002), с. 176, сноска 121.

Глава 2. Иррациональные и трансцендентные числа 

39

Кантор – математик, внесший огромный вклад в основы теории
множеств, – родился в Санкт-Петербурге. Его отец был торговцем,
который наставлял сына так, чтобы тот превзошел его в том, чем он
сам занимался. Мать Кантора была из семьи музыкантов Бём. Кантор
проявил свои таланты и в искусстве, и в музыке, но в 17 лет решил
«посвятить свою жизнь математике»1. Он посещал Политехникум
(Polytechnicum) в Цюрихе и университет в Берлине. В 1869 году
Кантор получил место преподавателя в университете города Галле,
где оставался до конца жизни.
В 1873 году в письме математику Рихарду Дедекинду (1831–1916)
Кантор, размышляя о соответствии вроде соответствия между натуральными и четными числами, задавался вопросом об установлении
подобного соответствия между натуральными и вещественными числами. Он подозревал, что его нет, но не знал, почему. «Я не могу найти объяснения, которого ищу; возможно, оно очень простое», – писал
Кантор2. Знаменитые последние слова.
Говорят, что множество, чьи элементы образуют паросочетания
с натуральными числами, – перечислимое (или иногда – нумерованное или счетное). Множество перечислимо, если его элементы можно
некоторым образом упорядочить или перечислить списком, а всякий
список может быть пронумерован, то есть сопоставлен натуральному
ряду 1, 2, 3 и т. д. Все конечные множества – безусловно, перечислимые. Настоящая проблема – в бесконечных множествах.
Рассмотрим, например, целые числа, включающие отрицательные,
положительные и нуль. Перечислимо ли такое множество? Да, потому что мы можем перечислить все целые числа, начиная с нуля:
–0
–1
–1
–2
–2
–3
–3
...
1
2

Joseph Warren Dauben, Georg Cantor: His Mathematics and Philosophy of the
Infinite (Harvard University Press, 1979; Princeton University Press, 1990), 277.
Georg Cantor, letter of November 29, 1873, in From Kant to Hilbert: A Source
Book in the Foundations of Mathematics (Oxford University Press, 1996), Vol. II,
844.

40  Часть I. Основы
Обычно целые числа перечисляются не так, но этот пример ясно
показывает, что единым списком охвачены все целые числа.
Довольно интересно, что рациональные числа тоже перечислимы.
Давайте начнем с положительных рациональных чисел и не будем
беспокоиться о том, что в списке есть повторы:
1/1
1/2
2/1
1/3
2/2
3/1
1/4
2/3
3/2
4/1
...
Видите закономерность? У первого элемента списка сумма числителя и знаменателя равна 2. У следующих двух элементов списка суммы числителя и знаменателя дают 3. Следующие три элемента списка имеют числители и знаменатели, которые в сумме дают 4. И так
далее. Продолжив подобным образом дальше, получим список всех
положительных рациональных чисел. Отрицательные рациональные
числа можно включить в список, чередуя их с положительными. Следовательно, рациональные числа перечислимы.
В опубликованной в 1874 году статье «О свойстве множества вещественных алгебраических чисел»1 Кантор показал, что даже алгебраические числа перечислимы. Если помните, алгебраические числа – это решения алгебраических уравнений общего вида
aNxN + aN–1xN–1 + ... + a2x2 + a1x + a0 = 0,
где N – положительное целое число и аi – целые числа. Для любого
частного алгебраического уравнения давайте сложим все коэффициенты (значения аi) и само N. Назовем это число высотой уравнения. Для заданной высоты (например, 5) существует конечное число
алгебраических уравнений. Каждое уравнение имеет не более N решений. Таким образом, все алгебраические числа могут быть перечислены в порядке их высот и решений. Следовательно, алгебраические
числа перечислимы.
1

Более доступно изложено в From Kant to Hilbert, Vol. II, 839–843.

Глава 2. Иррациональные и трансцендентные числа 

41

А трансцендентные числа? Можно ли их как-то посчитать? Вряд
ли! Ведь нет даже общей процедуры определения трансцендентности
некоторого числа!
А вещественные числа, которые включают в себя алгебраические и
трансцендентные числа? Их можно посчитать?
В той же статье 1874 года, где Кантор показал перечислимость алгебраических чисел, он показал также, что вещественные числа не
перечислимы.
Кантор начал свое доказательство с предположения, что вещественные числа перечислимы. Он предположил, что есть некий способ
перечислить вещественные числа и что их перечислили в следующем
списке, элементы которого обозначены как  с индексом:
1 2 3 4 5 6 …
Кантор собирается показать, что этот список неполон, что независимо от того, как он был построен, он просто не может содержать все
вещественные числа.
Выберем любое число  (альфа) и большее число  (бета). Их можно представить на числовой оси таким образом:

Теперь начнем двигаться по нашему перечислимому списку вещественных чисел, пока не найдем первые два вещественных числа,
попадающих между  и . Эти два числа больше  и меньше . Назовем меньшее из них , а большее – :

Продолжаем двигаться по списку вещественных чисел дальше,
пока не найдем два новых числа между  и . Назовем их  и .

И еще раз:

Очевидно, что этот процесс должен продолжаться бесконечно.
У нас всегда будет возможность найти еще два числа между последними двумя числами.

42  Часть I. Основы
Как это узнать? Легко! Предположим, мы находимся в таком положении:

где верхний индекс (v) задает количество v штрихов (миллион, миллиард, триллион или еще больше), но обязательно конечное. Теперь,
независимо от того, как долго продолжается поиск по списку перечислимых вещественных чисел, невозможно найти еще одну пару
чисел, которая попадает между (v) и (v). Тогда очевидно, что список
действительных чисел неполон. В списке пропущены все числа между (v) и (v). Например, число посередине между (v) и (v) – это их
среднее арифметическое, или:

И это – только начало. В списке пропущено много других чисел.
И этот процесс, как известно, может продолжаться бесконечно.
Значения  продолжают расти, а значения  продолжают уменьшаться, но наибольшее  не станет больше наименьшего . (Найдя
новую пару чисел, попадающих внутрь последней пары  и , меньшее – всегда , а большее – всегда .) Как , так и  имеют границу – предел, – который Кантор обозначает символом бесконечности
в верхнем индексе:  и .
Возможно ли, чтобы  было меньше ? Обратите внимание:

Нет, это невозможно. Если  никогда не становятся больше ,
а  никогда не становятся меньше , то в списке вещественных чисел
пропущены все числа между  и , например:

В конце концов, должно случиться так, что  станет равным .
Кантор называет этот предел  (греческая буква «эта»):

Глава 2. Иррациональные и трансцендентные числа 

43

Поскольку данный процесс бесконечен (мы уже установили, что
он не может остановиться ни в одной так ли точке), , как и  тоже,
никогда не достигают . Теперь мы знаем, что это означает, не? Это
означает, что значения  нет в первоначальном списке вещественных
чисел!
Если бы значение  было в списке, оно появилось бы когда-нибудь
при поиске следующих  и , но рассмотрим  и , которые появились
списке прямо перед :

Теперь в списке вещественных чисел между (v) и (v) пропущены
все числа, кроме .
Все варианты исчерпаны. Ни один не работает, ни один не имеет
смысла, и все это – из-за ошибочности исходного предположения
о том, что вещественные числа можно пронумеровать. Стало быть,
мы не можем этого сделать.
Целые числа перечислимы. Рациональные числа перечислимы.
Даже алгебраические числа перечислимы. А вот вещественные – нет.
Кантор полагал, что неперечислимость вещественных чисел – новое доказательство существования трансцендентных чисел. (Если
трансцендентных чисел нет, то вещественные числа – это то же, что
алгебраические, и, следовательно, они перечислимы.) В итоге Кантор
понял то, что существует по крайней мере два вида бесконечности –
перечислимая и неперечислимая, бесконечность натуральных чисел
и бесконечность континуума. Бесконечные множества натуральных,
рациональных и даже алгебраических чисел – перечислимые. Как
только мы добавляем трансцендентность, мы вдруг оказываемся
в совершенно ином мире. Мы обнаруживаем разные мощности двух
разных бесконечностей: одна мощность относится к натуральным, рациональным и алгебраическим числам; другая мощность – это мощность вещественных чисел и континуума.
Работа Кантора была спорной в своё время и не вполне свободна
от этого и теперь. Но после Кантора не было математика, который
не думал бы о бесконечности почти так же. Кроме того, разделение
бесконечности на перечислимую и неперечислимую оказалось чрезвычайно полезным в условиях, когда воображение одной лишь бесконечности простого типа еще пугало человеческий разум.
Известен миф о том, что длительным созерцанием бесконечности
Кантор довел себя до безумия. Действительно, последние примерно

44  Часть I. Основы
20 лет своей жизни Кантор проводил в психиатрических больницах,
но это была, скорее всего, разновидность депрессии, которая проявлялась вне зависимости от рода его занятий1. И все же обострения
у Кантора приступов психической болезни, видимо, были вызваны
усталостью и напряжением, а напряжение, наверное, было обусловлено неприятием его необычной математической теории. В периоды
выздоровления Кантор проявлял отличные от математических интересы. Он занимался философией, богословием, метафизикой и гипотезой о том, что пьесы, приписываемые Уильяму Шекспиру, писал
Фрэнсис Бэкон.
У конечных и бесконечных множеств довольно много различий.
Одно серьезное различие – в собственных подмножествах, то есть
подмножествах, не совпадающих с самим множеством. Мощность
собственного подмножества конечного множества всегда меньше
мощности самого множества. Это более чем очевидно. Мощность
собственного подмножества бесконечного множества тоже может
быть меньше мощности самого множества. (Например, множество
натуральных чисел – это собственное подмножество множества вещественных чисел, их мощности различны.) Однако в некоторых случаях мощность собственного подмножества бесконечного множества
равна мощности самого множества. Это возможно только для бесконечных множеств. Множество натуральных чисел – собственное
подмножество множества целых чисел, которое является собственным подмножеством множества рациональных чисел, которое является собственным подмножеством множества алгебраических чисел.
У всех этих бесконечных множеств одинаковая мощность. Они равносильны.
Также верно и то, что различные собственные подмножества вещественных чисел равносильны друг другу. Рассмотрим множество
вещественных чисел от 0 до 1. Можно установить взаимно-однозначное соответствие между ним и множеством вещественных чисел,
больших 1. Стоит только поделить 1 на каждое число из множества.
Например, 0,5 соответствует 2; 0,25 – 4; 0,1 – 10, а 0,0001 – 10 000.
Этот простой факт оказывается очень полезным: он означает, что
можно изучать свойства вещественных чисел, ограничившись диапазоном от 0 до 1, и всё, что мы обнаружим, будет применимо ко всем
вещественным числам. (Тьюринг, как и Кантор, тоже пользуется этим
свойством в своей статье.)
1

Dauben, Georg Cantor, 285.

Глава 2. Иррациональные и трансцендентные числа 

45

Изучая бесконечные множества, Кантор сделал и другие удивительные открытия: он обнаружил, что можно установить взаимнооднозначное соответствие между континуумом – вещественными
числами на прямой – и точками двумерной плоскости и даже точками
любого N-мерного пространства.
Давайте ограничимся, например, участком плоскости с координатами x и y, заключенными между 0 и 1. Каждая точка на плоскости
может быть представлена парой чисел (x, y), и каждое из этих двух
чисел может иметь бесконечное число цифр после десятичной запятой. В следующем выражении каждая цифра числа x после десятичной запятой обозначается буквой a с индексом:
x = 0, a1 a2 a3 a4 ...
То же для y:
y = 0, b1 b2 b3 b4…
Теперь возьмем эти цепочки цифр и «сплетём» из них новое число:
0, a1 b1 a2 b2 a3 b3 a4 b4...
Получилось одно вещественное число, заключающее в себе два
вещественных числа. Каждая двумерная точка соответствует одному
вещественному числу континуума. Следовательно, множество точек
плоскости обладает той же мощностью, что и множество вещественных чисел прямой. Кантор был так поражен этим открытием, что изменил своему немецкому. «Je le vois, mais je ne le crois pa», – писал он
Дедекинду1. «Я вижу это, но я этому не верю».
В 1891 году Кантор опубликовал другое доказательство неперечислимости вещественных чисел2, и с тех пор оно так и осталось в умах
людей. Доказательство Кантора имело дело не с числами, а с множествами и было более общим, чем пример, который я собираюсь привести, но идея та же. По причинам, которые станут вполне понятными,
оно получило название диагонального доказательства, или диагонального процесса, или диагонального аргумента, или диагонализации.
Но как бы оно ни называлось, в его название входит слово диагональ.
Давайте ограничимся вещественными числами от 0 до 1. Предположим, что мы изобрели некий способ перечисления всех веществен1
2

Письмо от 29 июня 1877 года в From Kant to Hilbert, Vol. II, 860.
Georg Cantor, «On an Elementary Question in the Theory of Manifolds», From
Kant to Hilbert, Vol. II, 920–922.

46  Часть I. Основы
ных чисел. (Как можно догадаться, что это еще одно доказательство
от противного.) Допустим, список начинается как-то так:
0,1234567890…
0,2500000000…
0,3333333333…
0,3141592653…
0,0010110111…
0,4857290283…
0,0000000000…
0,9999999999…
0,7788778812…
0,2718281828…
...
Кажется, мы избежали хорошего начала. Список включает 0, 1/4,
1/3, /10, e/10, то странное иррациональное число с меняющимся
числом единиц, которое я приводил раньше, и некоторые другие, не
вполне узнаваемые числа. Каждое число в списке имеет бесконечное
количество десятичных разрядов (даже если они только нулевые), и
в нем – бесконечное количество чисел.
Хотя этот список бесконечен, мы можем убедиться, что в нем коечего нет. Посмотрим на цифры, образующие диагональ списка от левого верхнего угла к нижнему правому. Эти цифры выделены жирным шрифтом:
0,1234567890…
0,2500000000…
0,3333333333…
0,3141592653…
0,0010110111…
0,4857290283…
0,0000000000…
0,9999999999…
0,7788778812…
0,2718281828…
...
Теперь составим число из этих выделенных цифр:
0,1531190918…
Поскольку список вещественных чисел бесконечен и количество
цифр в каждом из них тоже бесконечно, у этого числа – бесконечное

Глава 2. Иррациональные и трансцендентные числа 

47

число цифр. Теперь увеличим каждую отдельную цифру этого числа
на 1 (цифра 9 меняется на 0):
0,26422010259…
Есть ли это новое число в исходном списке? Давайте действовать
последовательно: является ли это новое число первым в списке? Нет,
это не так, потому что первая цифра первого числа в списке – 1, а первая цифра нового числа – 2.
Является ли оно вторым числом в списке? И снова нет, потому что
вторая цифра второго числа в списке – 5, а вторая цифра нового числа – 6.
Является ли оно третьим числом в списке? Нет, потому что третья
цифра третьего числа в списке – 3, а третья цифра нового числа – 4.
И так далее. Новое число не может быть N-ым числом в списке, потому что N-ая цифра N-го числа в списке не равна N-ой цифре нового
числа.
Таким образом, список неполон, и наше исходное предположение
неверно. Невозможно перечислить вещественные числа от 0 до 1. Мы
еще раз убедились, что вещественные числа неперечислимы.
Что будет, если провести такой же эксперимент со списком алгебраических чисел? Мы уже знаем, как пронумеровать алгебраические
числа, так что это не проблема. Построив диагональ и изменив все ее
цифры, мы получим число не из списка. Это значит, что полученное
число не алгебраическое. Оно – трансцендентное.
По-разному упорядочивая список алгебраических чисел и устанавливая разные правила выделения в нем уникальной диагонали, мы
каждый раз будем получать еще одно трансцендентное число.
Для обозначения мощности множества натуральных чисел (и, следовательно, всякого перечислимого бесконечного множества) Кантор в 1895 году выбрал первую букву еврейского алфавита с нулевым
нижним индексом – ‫אּ‬0 (произносится как «алеф нуль»). Кантор назвал его первым трансфинитным числом. Он объединил его с другими трансфинитными числами (‫אּ‬1, ‫אּ‬2, ‫אּ‬3 и т. д.), чтобы создать целостную трансфинитную математику.
Если мощность перечислимых множеств – ‫אּ‬0, то какова мощность
неперечислимого множества вещественных чисел? Можно ли хотя
бы представить такую мощность?
Можно. Давайте начнем с примера конечных множеств. Вот множество всего из трех элементов:
{a, b, c}.

48  Часть I. Основы
Сколько всего подмножеств у этого множества? (Множество всех
подмножеств множества называется степенью множества.) Попробуем сделать это вручную, не забывая только о пустом множестве и
самом множестве из трех элементов:
{}
{a}
{b}
{c}

{a, b}
{a, c}
{b, c}
{a, b, c}

У множества из трех элементов – восемь подмножеств, и не случайно:
23 = 8.
Показатель степени – число элементов исходного множества. Результат – число подмножеств этого множества. Множество из 4 элементов имеет 16, или 24, подмножеств. У множества из 5 элементов –
32 подмножества.
Существует более систематический способ подсчета этих подмножеств, который лучше раскрывает данное соотношение. Давайте составим таблицу, столбцы которой – это 3 элемента исходного множества, а цифры 0 и 1 в столбцах – признак вхождения этого элемента
в подмножество:
a
0
0
0
0
1
1
1
1

b
0
0
1
1
0
0
1
1

c
0
1
0
1
0
1
0
1

Подмножество
{}
{c}
{b}
{b, c}
{a}
{a, c}
{a, b}
{a, b, c}

Наборы из 0 и 1 в трех первых столбцах – это те же двоичные числа
от 0 до 7. Три бита порождают 8 двоичных чисел, а общее правило:
Мощность степени множества = 2мощность исходного множества.
Степень множества из 10 элементов состоит из 1024 элементов.
Степень множества из 100 элементов состоит из 1 267 650 600 228 22
9 401 496 703 205 376 элементов.

Глава 2. Иррациональные и трансцендентные числа 

49

Теперь рассмотрим натуральный ряд, включающий для этой цели
также 0:
{0, 1, 2, 3, 4, 5,…}.
Мощность этого множества – ‫אּ‬0. Сколько у него подмножеств?
Иными словами, какова мощность его степени? По аналогии она
должна быть
2‫אּ‬0.
Наверное, нужны дополнительные разъяснения. Давайте построим таблицу, как для конечного множества (но, конечно, не такую полную). Над столбцами – все элементы множества натуральных чисел.
В столбце – признак (0 или 1) вхождения натурального числа в конкретное подмножество, указанное справа:
0
0
1
0
1
0
1
0
1
…

1
0
0
1
1
0
0
1
1
…

2
0
0
0
0
1
1
1
1
…

3
0
0
0
0
0
0
0
0
…

4
0
0
0
0
0
0
0
0
…

5
0
0
0
0
0
0
0
0
…

…
…
…
…
…
…
…
…
…
…

Подмножество
{}
{0}
{1}
{0, 1}
{2}
{0, 2}
{1, 2}
{0, 1, 2}
…

То, чего мы, в сущности, добиваемся, – это список всевозможных бесконечных комбинаций из 0 и 1. Давайте поместим десятичную запятую (и нуль. – прим. перев.) перед каждой цепочкой цифр
списка:
0,000000…
0,100000…
0,010000…
0,110000…
0,001000…
0,101000…
0,011000…
0,111000…
…

50  Часть I. Основы
Тогда все они – двоичные числа в диапазоне от 0 до 1, причем (судя
по способу их создания) все двоичные числа от 0 до 1 и, следовательно, все вещественные числа от 0 до 11. Ранее было показано, что вещественные числа из диапазона от 0 до 1 могут быть поставлены
в соответствие всем вещественным числам, что означает, что вещественные числа могут быть поставлены в соответствие элементам степени множества натуральных чисел. Поэтому эта степень множества
имеет ту же мощность, что континуум.
Таким образом, мощность континуума
2‫אּ‬0,
где ‫אּ‬0 – мощность множества натуральных чисел.
Кантор доказал, что невозможно установить взаимно-однозначное
соответствие между элементами любого непустого множества и элементами его степени, что очевидно для конечных множеств, но не так
очевидно для бесконечных. Теперь этот факт известен как теорема
Кантора, и он был главным результатом его статьи 1891 года, в которой предложен метод диагонализации. Как и то, что множество может
иметь степень множества, a степень множества – свою собственную
степень множества и т. д. Все эти множества имеют разные мощности.
Кантор выяснил, что мощность континуума – это следующее за ‫אּ‬0
трансфинитное число, которое он назвал ‫אּ‬1. Это предположение называют континуум-гипотезой Кантора, и оно может быть выражено
математически так:

‫אּ‬1 = 2‫ אּ‬.
0

Кантор изо всех сил пытался доказать свою гипотезу, но так никогда и не смог этого сделать. Проблема заключалась в том, что между ‫אּ‬0
и мощностью континуума могло быть какое-то другое трансфинитное число2.
1

2

Может также показаться, что мы наткнулись на метод перечисления всех
вещественных чисел от 0 до 1. Закономерность уже понятна – первая цифра после запятой меняется с 0 на 1, вторая цифра меняется со скоростью,
вдвое меньшей, и т. д. – и мы могли бы легко продолжать этот список настолько долго, насколько пожелаем. Однако ошибка в том, что список никогда не будет содержать трансцендентное число. Каждое число в списке
имеет конечное число ненулевых цифр после запятой.
Существование множества этой промежуточной мощности – это так называмая континуум-гипотеза – первая из 23 проблем Гильберта, о которых
он доложил на II Математическом конгрессе в 1900 году. В 1940 году Гёдель
доказал, что отрицание континуум-гипотезы недоказуемо, а в 1963 году
Коэн доказал недоказуемость континуум-гипотезы. – прим. перев.

Глава 2. Иррациональные и трансцендентные числа 

51

Несмотря ни на что, глубокий смысл всего этого состоит в том, что
мощность перечислимых множеств не просто меньше мощности континуума

‫אּ‬0 < 2‫ אּ‬,
0

а много, много, много, много, много меньше:

‫אּ‬0