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

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

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

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

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

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

Существуют ли множества, не являющиеся счетными? Несмотря на расширение натуральной системы чисел сначала целыми, а затем и рациональными числами, общее число рассматриваемых объектов не увеличилось. Как мы убедились, число объектов во всех случаях осталось счетным. У читателя теперь может создаться впечатление, что все бесконечные множества счетны. Это не так, поскольку ситуация меняется коренным образом при переходе к действительным числам. Одним из замечательных достижений Кантора явилось доказательство того, что действительных чисел больше, чем натуральных. При этом Кантор применил так называемый диагональный процесс, который упоминался в главе 2 и который Тьюринг использовал в своем доказательстве неразрешимости проблемы остановки Для машин Тьюринга. Доказательство Кантора, как и более позднее доказательство Тьюринга, — это доказательство от противного. Предположим, что утверждение, справедливость которого мы хотим установить, на самом деле ложно, то есть множество действительных чисел счетно. Тогда множество действительных чисел в интервале от 0 до 1 должно быть заведомо счетным и должен существовать какой-нибудь список, устанавливающий взаимно-однозначное соответствие между рассматриваемым множеством действительных чисел и множеством натуральных чисел, наподобие вот этого:

Жирным шрифтом выделены диагональные десятичные знаки. В данном случае эти цифры равны:

1, 4, 1, 0, 0, 3, 1, 4, 8, 5, 1…..

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

0,21211121112…

Это действительное число не может быть в списке, поскольку оно отличается от первого числа в первом десятичном разряде (после десятичной запятой), от второго числа — во втором разряде, от третьего числа — в третьем разряде и т. д. Таким образом, мы приходим к противоречию, поскольку полагали, что рассматриваемый список содержит все действительные числа в интервале от 0 до 1. Из этого противоречия следует истинность утверждения, которое нам требовалось доказать, — а именно, что не существует взаимно-однозначного соответствия между множеством действительных чисел и множеством натуральных чисел и, соответственно, что число действительных чисел больше числа рациональных чисел и не является счетным.

Число действительных чисел равно бесконечному числу, обозначаемому С. (Здесь С является сокращенным обозначением слова континуум — другого названия системы действительных чисел.) Может возникнуть вопрос, почему мы не обозначаем это число, например, N₁. Символ N₁ на самом деле обозначает следующее за N₀ бесконечное число, а вопрос о том, верно ли утверждение С = N₁ — это так называемая континуум-гипотеза, — представляет собой знаменитую и пока что нерешенную проблему.

При этом следует отметить, что множество вычислимых чисел счетно. Пересчитать их можно просто перечислив по порядку машины Тьюринга, порождающие действительные числа (то есть машины, последовательно порождающие цифры каждого разряда действительных чисел). При этом можно исключить из списка любую машину Тьюринга, порождающую действительное число, которое уже встречалось ранее в списке. Поскольку множество машин Тьюринга счетно, то, следовательно, счетным также должно быть и множество вычислимых действительных чисел. Почему же нельзя применить диагональный процесс к этому списку с тем, чтобы породить новое не включенное в список вычислимое число? Ответ состоит в том, что в общем случае невозможно с помощью вычислений решить, следует ли ту или иную машину Тьюринга включать в список, поскольку для этого мы должны были бы иметь возможность решить проблему остановки. Некоторые машины Тьюринга, начав порождение цифр действительного числа, могут зависнуть и оказаться уже не в состоянии выдать очередную цифру (поскольку они «не остановятся»). Не существует вычислимого способа, который позволил бы решить, какие именно машины Тьюринга зависнут таким образом. Это, в сущности, и есть проблема остановки. Значит, хотя метод диагонального процесса и породит некоторое действительное число, последнее не будет вычислимым. На самом деле, это рассуждение может использоваться для доказательства существования невычислимых чисел. Именно в этом ключе выдержано описанное в предыдущей главе тьюринговское доказательство существования классов алгоритмически неразрешимых задач. Другие области применения диагонального процесса будут рассмотрены дальше.

Оглавление книги