Новый ум короля: О компьютерах, мышлении и законах физики - [44]

1/3 = 0,333333333333333…

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

93/74 = 1,2567567567567567…,

где последовательность 567 повторяется неограниченное число раз. Это число тоже оказывается полностью обозримым. Также обозримым является выражение

0,220002222000002222220000000222222220…

которое определяет иррациональное число (оно просто состоит из последовательностей нулей и двоек, длины которых каждый раз увеличиваются на единицу), и еще много похожих выражений. В каждом таком случае нам достаточно знать правило, по которому составлено разложение. Знание алгоритма порождения очередной цифры в разложении числа — при условии, что такой алгоритм существует — дает нам способ «увидеть» целиком все бесконечное десятичное разложение. Действительные числа с алгоритмически порождаемыми десятичными разложениями называются вычислимыми числами (см. также гл.2 «Числа, отличные от натуральных»). (При этом не важно, десятичное это разложение или двоичное. Вычислимыми в этом смысле оказываются одни и те же числа, независимо от использованного основания разложения.) Только что рассмотренные числа π и √2 представляют собой примеры вычислимых чисел. В обоих случаях подробное описание соответствующего правила — задача довольно-таки кропотливая, но, в принципе, нетрудная.

Есть, однако, действительные числа, которые не являются вычислимыми в упомянутом выше смысле. Как мы убедились в главе 2, существуют невычислимые и при этом совершенно четко определенные последовательности. В качестве примера можно рассмотреть десятичное разложение, в котором n-я цифра равна 0 или 1 в зависимости от того, останавливается или нет n-я машина Тьюринга, производящая действия над числом n. В общем случае мы потребуем лишь, чтобы для действительного числа существовало какое-нибудь бесконечное десятичное разложение. Мы не только не требуем существования алгоритма порождения n-й цифры, но нам даже не обязательно знать о существовании какого бы то ни было правила, в принципе определяющего n-ю цифру[59]. Заметим, что вычислимые числа неудобны в работе. Невозможно обойтись одними лишь вычислимыми операциями, даже оперируя вычислимыми числами. Например, в общем случае вычислимым образом невозможно даже решить, равны ли два вычислимых числа друг другу! По этой причине мы будем работать со всеми действительными числами, когда десятичная последовательность может быть любой, а не только, скажем, вычислимой.

В заключение отметим также тождественность действительных чисел, чьи десятичные разложения заканчиваются бесконечной последовательностью девяток, и чисел, чьи разложения заканчиваются бесконечной последовательностью нулей. Например:

— 27,1860999999… = -27,1861000000…

Сколько же всего действительных чисел?

Давайте остановимся на минутку, чтобы оценить всю колоссальность обобщения при переходе от рациональных чисел к действительным.

Вначале может показаться, что целых чисел больше, чем натуральных, поскольку каждое натуральное число является целым, в то время как некоторые целые числа (а именно отрицательные) натуральными не являются. Аналогично может создаться впечатление, что дробей больше, чем целых чисел. Однако это не так. Согласно мощной и очень красивой теории бесконечных чисел, разработанной в конце XIX века Георгом Кантором — исключительно самобытным немецким математиком русского происхождения, — общее число дробных чисел, общее количество всех целых чисел и число всех натуральных чисел равны одному и тому же бесконечному числу, обозначаемому N₀ [60] «алеф-нуль»). (Удивительно, что похожая идея была частично предвосхищена еще за 250 лет до этого в начале XVII века великим итальянским физиком и астрономом Галилео Галилеем. Мы вспомним о некоторых других достижениях Галилея в главе 5.) Равенство количества целых чисел количеству натуральных чисел видно из следующего взаимно-однозначного соответствия:

Обратите внимание, что каждое целое число (в левом столбце) и каждое натуральное число (в правом столбце) встречаются один и только один раз в своем списке. В канторовской теории множеств именно существование такого рода взаимно-однозначного соответствия устанавливает факт равенства числа объектов в левом столбце числу объектов в правом столбце. Таким образом, число целых чисел действительно равно числу натуральных чисел. В данном случае это число бесконечно, но это не Имеет значения. (Единственное необычное свойство бесконечных чисел состоит в том, что даже если мы исключим некоторые элементы одного из списков, мы можем установить взаимно-одиозначное соответствие между элементами двух списков.) Аналогичным, хотя и несколько более сложным образом, устанавливается взаимно-однозначное соответствие между дробными и целыми числами. (Для этого можно использовать какой-либо из способов представления