15. Результаты о неразрешимости для вычислимых вещественных чисел

Тьюринг [1] сначала ввел определение вычислимого вещественного числа как такого числа, для которого на машине Тьюринга вычислимо двоичное разложение его дробной части. Но, как он скоро понял, нет способа вычислять двоичное разложение любого конструктивного вещественного числа в смысле нашего определения. Именно этот факт заставил заменить исходное определение на приведенное в предыдущем пункте и использующее налегающие интервалы вместо прилегающих. Невозможность вычисления десятичного разложения любого вещественного числа была впервые осознана Брауэром [4], и использование налегающих интервалов восходит к нему.

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

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

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

номером доказательства в символике п. 8.

Пусть 0 обозначает точку канторовского пространства, все знаки которой равны нулю, и положим

для или в зависимости от того, что имеет место: или Поэтому если бы мы могли решить для любого что имеет место или то было бы разрешимо, что дает противоречие.

Нет алгорифма, который для любого вычислимого вещественного числа а говорит нам, что имеет место: или

По аналогии с предыдущим доказательством мы полагаем

так что или в зависимости от того, или Таким образом, мы имели бы разрешающую процедуру для если бы могли доказать либо , либо для любого вычислимого вещественного числа.

Невозможен алгорифм, вычисляющий необрывающееся десятичное разложение любого вычислимого вещественного числа.

Разумеется, эта теорема, принадлежащая Тьюрингу [2], имеет место также, если выбрать любое основание системы счисления, отличное от 10. Допустим, что имеется алгорифм разложения любого вычислимого вещественного числа в десятичную дробь:

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

Теперь мы покажем, что невозможно вычисление какого бы то ни было обрывающегося или нет десятичного разложения любого вычислимого вещественного числа. Это — простое следствие теоремы, которую можно найти, например, у Цейтина [1].

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

Пусть два дизъюнктных рекурсивно перечислимых множества натуральных чисел, которые не могут быть рекурсивно отделены. Свяжем с А общерекурсивную функцию определенную соотношением

(см. скан)

Соответствующим образом В определяет общерекурсивную функцию Допустим теперь, что существует общерекурсивная процедура, упомянутая в теореме, и применим ее к вычислимым вещественным числам

Пусть состоит из тех чисел для которых мы решили, что . Тогда образуют рекурсивное отделение для так как из следует так что те Мы пришли к противоречию.

Не существует алгорифма, вычисляющего десятичное разложение любого вычислимого вещественного числа.

Если бы мы могли вычислить десятичное разложение

любого вычислимого вещественного числа а, то, определив —1 или мы могли бы доказать либо , либо . Это противоречит предыдущей теореме.

Рассмотрим следующее рассуждение, использующее закон исключенного третьего. Пусть дано произвольное вычислимое вещественное число. Если оно десятично рационально, то оно очевидным образом имеет десятичное рекурсивное разложение. Далее, если оно не является десятично рациональным, то мы можем определить любой знак его десятичного разложения, просто вычисляя его с достаточной точностью. Так как вычислимое вещественное число либо является десятично рациональным, либо не является, мы заключаем отсюда, что любое вычислимое вещественное число имеет рекурсивное десятичное разложение. С другой стороны, мы только что доказали, что это утверждение ложно, если его интерпретировать конструктивно. Это показывает, что (как было впервые отмечено в неосторожное использование закона исключенного третьего может вести к заключениям, не являющимся конструктивно истинными.

Брауэр [4] и [8] классифицировал вычислимые вещественные числа согласно возможности установить их положение относительно рациональных чисел, из которых они получены пополнением.

Вычислимое вещественное число без всякой дальнейшей информации называется элементом (пополнения) нулевого порядка.

Если, кроме того, для любого рационального числа может быть доказано либо либо то а называется элементом первого порядка.

Элемент а первого порядка, для которого а может быть доказано или опровергнуто при любом рациональном называется элементом второго порядка.

Если мы можем решить для любого рационального верно ли или то а называется элементом третьего порядка.

Наконец, если для любого рационального мы можем решить, верно ли а или то а называется элементом четвертого порядка, или, в терминологии Гейтинга [1], респектабельным вещественным числом.

Когда мы погружаем рациональное число в вычислимые вещественные числа, мы, очевидно, получаем элемент четвертого порядка. Также и иррациональное число автоматически имеет четвертый порядок.

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

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