Файл: Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf

16 ВВЕДЕНИЕ

связаны с разработкой тех или иных концепций в осно­

метим сразу громадные заслуги интуиционизма в фор­ мировании основных концепций конструктивного ана­ лиза. Большое значение сыграла также и уже упоминав­ шаяся книга В ей л я [1], содержащая, в частности, один из первых подходов к понятию конструктивного дей­ ствительного числа.

Весьма существенным этапом в развитии конструк­ тивного анализа явилась выработка в 30-х годах на­ шего столетия благодаря работам Эрбрана, Гёделя, Тьюринга, Поста, Черча и Клини точного понятия алгорифма (фактически было предложено несколько внешне различных концепций, оказавшихся, однако, равнообъемными). Основываясь на точных понятиях

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

нилось, что естественное на первый взгляд связывание вычислимости чисел с вычислимостью их систематичес­ ких представлений в фиксированной системе счисления имело ряд принципиальных недостатков. Укажем лишь

«предикативном анализе». В предикативном анализе рассматривае­ мые объекты вводятся посредством индивидуальных определений в рамках некоторых фиксированных средств, при этом особое вни­

на два из них: 1) не для любых двух систем счисления возможен алгорифм, позволяющий от вычислимых раз­ ложений в первой системе переходить к вычислимым разложениям во второй (см. теорему Мостовского — Успенского, § 3 гл. 4); 2) при любой фиксированной системе счисления невозможен алгорифм сложения действительных чисел, вычислимых относительно этой системы счисления. Отвлекаясь от технических деталей, можно сказать, что в своем исправленном определении Тьюринг связывает вычислимость действительного чис­ ла х с существованием вычислимой последовательности рациональных чисел 51 (т. е. алгорифма, переводящего всякое натуральное число в рациональное число) *) та­ кой, что при любом п

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

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

Изложенную концепцию конструктивного (вычисли­ мого) действительного числа (ей отвечают и конструк­ тивные числа, рассматриваемые в этой книге), повидимому, можно считать окончательной. Интересно заметить, что Тьюринг отмечает влияние на свое опре­ деление некоторых идей Брауэра.

*) Конечно, мы имеем здесь в виду алгорифм в точном смысле слова (например, машину Тьюринга). Отметим, что вычислимость последовательностей рациональных чисел очевидным образом сво­ дится к вычислимости арифметических функций (т. е. функций на­ турального аргумента с натуральными значениями).

18 ВВЕДЕНИЕ

Исследования, начатые Тьюрингом, Банахом и Мазуром, были продолжены в послевоенные годы. В 1949 г. появляется работа Ш п е к е р а [1], в которой, наряду с глубоким исследованием примитивно рекурсивно вы­

рациональных чисел, не являющейся вычислимо сходя­

несколько точнее, для последовательности Шпекера ©

| © ( 0 - S ( / ) | < 2 - r t .

Таким образом, скорость сходимости этой последова­ тельности (имеется в виду сходимость, утверждаемая известной классической теоремой) не поддается эффек­ тивной оценке.

Дальнейшему изучению различных представлений вычислимых действительных чисел были посвящены ра­

частности, чрезвычайно прозрачное построение рассмот­ ренного выше примера Шпекера.

В 1949—1950 учебном году в курсе лекций в Инсти­ туте математики Польской академии наук Мазур по­ следовательно изложил результаты по вычислимому

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

кие дроби, дедекиндовы сечения). Изучается также при­ митивно рекурсивная вычислимость.

Интуитивная вычислимость в области натуральных чисел отождествляется Мазуром с общей рекурсивностью. Весьма своеобразным является подход к опреде­ лению вычислимых объектов более сложных типов. Остановимся, например, на определении вычислимых натуральнозначных функционалов над арифметическими функциями. Функционал (в традиционном смысле — Мазур свободно использует концепции теоретико-мно­

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

g(n) = <b(f{n, т)).

(Здесь f(n,m) рассматривается как функция т при каждом фиксированном п.) В таком же порядке идей определяется и вычислимость действительной функции: функция ф вычислима, если она переводит всякую вы­ числимую последовательность вычислимых действитель­ ных чисел снова в вычислимую последовательность вы­ числимых действительных чисел. При этом вычислимые последовательности вычислимых действительных чисел трактуются при помощи двухместных вычислимых (по совокупности обоих аргументов!) аппроксимирующих рациональных функций. (Это, по существу, равносильно нашему определению последовательностей КДЧ (§ 1 гл. 3).) Одним из замечательных результатов, пред­ ставленных в монографии Мазура, является теорема не­ прерывности вычислимых (в вышеуказанном смысле) функционалов и действительных функций. Эта теорема близка к теореме Маркова о невозможности конструк­ тивных разрывов у вычислимых действительных функ­ ций (при несколько другой концепции вычислимой