24. Две теоремы из классической теории функций

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

непрерывности позволяет нам найти для каждого окрестности такие, что

Так как локализовано, мы можем решить для каждой окрестности содержится ли она в Если да, выбрасываем ее. Сделав это, найдем тот рациональный интервал для которого наибольшее из возможных. Этот интервал является окрестностью максимума на

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

Хотя мы можем вычислить максимум действительной функции на локализованном компактном множестве, может случиться, что нет конструктивной точки, в которой достигается это максимальное значение. Это было обнаружено Лакомбом [2], Заславским [1] и Шпеккером [2].

Существует действительный рекурсивный функционал который всюду определен, хотя

для любой конструктивной точки

Пусть рекурсивная последовательность рациональных интервалов, такая, что содержит все конструктивные точки, но для всех Такая последовательность была

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

Тогда

определена всюду на вещественной прямой

хотя

для любой конструктивной точки а. Это доказательство было дано Лакомбом [3].

Используя существование открытого множества, которое содержит все конструктивные точки, но не равно всему пространству, мы можем построить различные функции, области определения которых содержат все конструктивные точки, но которые тем не менее ведут себя очень плохо. Например, как показано Клини [2], функция может быть определена во всех конструктивных точках канторова пространства, не будучи равномерно непрерывной, а в этом случае она не может быть продолжена до всюду определенной функции. Чтобы усмотреть это, допустим, что дизъюнктные окрестности, покрывающие все конструктивные точки, но не покрывающие всего пространства. Положим и 1 на окрестностях соответственно, Тогда дискретнозначный частично рекурсивный функционал, принимающий только значения 0 и 1, который обладает нужными свойствами.

Другой пример классической теоремы, которая проваливается конструктивно, — это теорема о среднем значении.

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

Эта, а также следующая теорема упомянута Крайзелем [2] и доказана Цейтиным [1].

Сопоставим каждому вычислимому действительному числу а функцию, изображенную на рис. 5.

Рис. 5.

Если бы в нашем распоряжении был алгоритм со свойствами, указанными в теореме, то мы могли бы найти точку, в которой эта функция исчезает. Для этой точки можно решить или просто вычисляя ее с достаточной точностью. В первом случае а 0, во втором а 0. Таким образом, мы имели бы рекурсивный метод доказательства а 0 или а 0 для любого вычислимого действительного числа а. Однако мы знаем из что такого метода нет.

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

знак в единичном интервале, принимал ненулевое значение в любой конструктивной точке.

Действительно, допустим, что всюду определен на единичном интервале Положим и определим индуктивно

Здесь мы использовали тот факт, что если вычислимое действительное число то мы можем решить или Когда окрестность сходится к конструктивной точке, где исчезает. Мы достигли противоречия.