markov_teorija_algorifmov (522344), страница 78
Текст из файла (страница 78)
Речь идет о доказательстве применимости нормального алгорифма к исходному данному методом «от противногоя. Для математика, стоящего на классической, теоретико-миохкественной позиыии, этот метод безусловно приемлем, так как он является простым следствием общего логического закона — «закона исключенного третьегок Для математика, разделяющего конструктивную точку зрения, этот метод представляет собой некоторую проблему, требующую во всяком случае специального обсуждения. Мы изложим сейчас свою точку зрения на этот вопрос, которую, как нам кажется, разделяет значительная группа ТЕОРЕМА КОШИ (ПРОДОЛЖЕНИЕ Ф 88) 419 418 АлГОРиемы и мАтемАтический АнАлиз 1гл.
1х 5 881 математиков, придерживающихся конструктивного направления *). 2. Теория нормальных алгорифмов строится в данной монографии в рамках абстракции потенциальной осуществимости. Слова в рассматриваемых алфавитах, нормальные алгорифмы — все зто потенциально осуществимые конструктивные объекты. Сам процесс применения нормального алгорифма к заданному слову мы рассматриваем как потенциально осуществимый конструктивный процесс. Для того чтобы удостовериться в применимости алгорифма й к слову Р, мы не считаем обязательным, чтобы процесс применения Й к Р был фактически выполнен перед нашими глазами, от начала до конца. Как же можно удостовериться в применимости алгорифма к слову? 3. Мы считаем возможным применять здесь рассуждение «от противного», т.
е. утверждать, что если предположение о неограниченной прсдолжагмости процесса применения алгорифма Й к слсву Р опровергнуто приведением к нелепости, то Й примгнйм к Р. Мы не видим разумных оснований отвергать этот способ рассуждения, так как никакого выхода за рамки конструктивного направления при этом не происходит: абстракция актуальной бесконечности не применяется, существование продолжает пониматься как потенциальная осуществимость построения. Если мы утверждаем на основании доказанной невозможности неограниченной продолжаемости детерминированного процесса, что этот процесс закончится, то при этом дается совершенно определенный способ построения: продолжать процесс до его завершения.
То обстоятельство, что при этом число шагов процесса может не быть „заранее" ограниченным, ничего здесь по существу не меняет. К тому же требование, чтобы это число было заранее ограниченным, едва ли может быть точно и объективно сформулировано. Нетрудно видеть, что рассмотренный способ доказательства применимости алгорифма дает возможность обосновать следующий способ рассуждения. (?усть для одноместного вербального предиката Чз в алфавите А имеется нормальный алгорифм, позволяющий для всякого слова Р в А выяснять, удовлетворяет ли Р предикату чз.
Если опровергнуто предположение о том, что ни одно слово нг удовлетворяет предикату цз, то сущгст- "1 Изложение в основном следует работе А. А. М в р к о в а !3!. См. также его работу !101. вугт слово, удовлетворяющее ц). Найти это слово можно тогда путем последовательного перебора слов, начиная с пустого, причем для каждого рассматриваемого слова мы выясняем, пользуясь имеющимся алгорифмом, удовлетворяет ли оно предикату чз.
В силу этого мы называем данный способ рассуждения методом конструктивного подбора, а логический принцип, провозглашающий допустимость этого метода,— принципом конструктивного подбора. 4. Принцип конструктивного подбора находит в конструктивной математике, н особенно в конструктивном анализе, важные и многообразные применения, В качестве примера докажем с его помощью следующее утверждение: 4.1. Каковы бы ни были конструктивные дгйствитгльныг числа х и у, если неверно, что х=у, то х> у или у>х. В самом деле, пусть х=й;66;, у=Я;66,'.
Рассмотрим следующий арифметический предикат с переменной М для натуральных чисел: (1) ! Й, (6, (М)) — Й, (6, (М)) ! > 2-1н- 1, Нетрудно убедиться, что существует нормальный алгорифм, распознающий те М, которые удовлетворяют этому предикату. Предположим теперь, что не существует М, удовлетворяющего (1). Тогда для любого М ! Й, (6, (М)) — Й,(9, (М)) )(2-1"-'1. Но это означает, что х=у (э 62.3), а это противоречит условию нашего утверждения.
Значит, согласно принципу конструктивного подбора, существует М, удовлетворяющее предикату (1). Для этого М имеет место одно из следующих неравенств: Й, (9, (М)) — Й, (5, (М)) > 2-1н- '1, Й, (В, (М)) — й, (6,(М)) > 2 1н В первом случае х>у, во втором у>х. Теорема 4.1 доказана.
$68. Теорема Коши о нуле зиакоперемениой непрерывной функции (продолжение й 66) 1, Перейдем теперь к доказательству теоремы 5 66.3.2, (Заметим, что утверждение ее нетривиально: можно было бы рассчитывать найти среди функций указанного типа такую, что после продолжения по непрерывности на классический континуум все ее нули окажутся неконструктивными.) 1ЕОРГМА КОШИ (ПРОДОЛЖЕНИЕ 4 661 4 66) 420 ллгоюрвмы и атателтатическии анализ (гл. ~х 421 Итак, пусть конструктивная действительная функция непрерывна на 10, 1! и меняет на этом отрезке знак (для опре- деленности будем считать, что /(0) <О, а /(1)>0).
По предпо- ложению / отлична от нуля в любой конструктивной точке х рассматриваемого отрезка. Поэтому, согласно теореме 3 67.4.1, /(х)>0 или /(х)<0, и мы располагаем нормальным алгориф- мом, выясняющим, какой именно из этих случаев имеет место. Пользуясь этим алгорифмом, мы построим нормальные алго- рифмы Х и $ в алфавите Р+ таким образом, чтобы выполня- лись равенства Х(О) =-О, ь)(О) = 1', / -', ес и / ' " <О, Х(н)+2)(/У) (Х(н)+и) (Н)) <О Х (г' +1) 1 - Х (/у)+я)1 (и)' ( Х(Ф), если /( " ) >О, ь)(/у'), если / ~ ' ) <О, 2 ~~ (й/+1) ='1 Х (у)+,.; (л) Х (м)+21 (л) 2 ' если /( 2 )>О (здесь й/ — произвольное натуральное число).
Алгорифмы Х и 2) представляюг сооой конструктивные последовательности рациональных чисел, причем, как легко видеть, фундаментальные. Простой подсчет показывает, что ! Х (й/) — Ф(й/) ~ =2-', так что, если обозначить определяемые последовательностями Х и ф конструктивные действительные числа через х и у соответственно, то х = у. Заметим также, что /(Х(У)) < 0 и /(2)(й/)) > О. Теперь, пользуясь непрерывностью /, нетрудно показать, что /(х)<0 н /(у))0, а отсюда на основании 6 64,8,1 можно заключить, что /(х) О, что противоречит условию теоремы.
2. Теперь читатель методом «деления отрезка пополам» без труда убедится в справедливости следующего утверждения: 2.1. Какова бы ни была непрерывная на [О, 1) конструктивная действительная 4>ункция, меняющая знак на этом отрезке, и каково бы ни было рациональное число е>0, может быть построено конструктивное действительное число х, лежащее между 0 и 1 и такое, что !/(х)!<е. Действительно, пусть выполнены условия теоремы, и пусть для определенности /(0)<0, а /(1)>0. Вычисляем !/(1/2)! с такой точностью, чтобы можно было указать верный член днзъюнкции «(/(1/2) ! е или (/(1/2) ! > е/2», Если окажется, что (/(1/2)(<е, то в качестве х берем 1/2 н процесс прекращаем. Если же окажется, что )/(1/2)(>е/2, то /(1/2)>е/2 или /(1/2)< — е/2.
В первом случае берем отрезок 10, 1/21, а во втором — отрезок П/2, 1) н совершаем аналогичный очередной шаг процесса. Согласно принципу конструктивного подбора этот процесс должен оборваться, так как прн неограниченном продолжении его мы получили бы конструктивное действительное число, являющееся точкой разрыва функции /, которая, по предположению, непрерывна. Нормализовав это рассуждение, мы получим доказательство теоремы 2.1. 3. Резюмируя содержание Я 66 н 68, можно утверждать, что для любой непрерывной на 10, !) зиакопеременной конструктивной действительной функции / имеет место следующая ситуация: 1) она не может оказаться не имеющей конструктивного нуля *) $66.3.21; 2) информации о самой этой функции, вообще говоря, недостаточно для фактического нахождения ее нуля 12 66.3.1); 3) функция / и заданная точность е>0 представляют собой информацию, достаточную для нахождения конструктивной точки х, в которой )/(х)!<Е12.1).
Опытный математик-вычислитель, разумеется, должен остро ощущать обрисованную здесь ситуацию. Однако нам представляется небезынтересным, что это ощущение может быть выражено в виде точных математических утверждений. *) То есть конструктивного кориа урависиия / (х) — -О.
423 ЛИТЕРАТУРА ЛИТЕРАТУРА АдянС. И. 1. Конечно-определенные группы и алгоритмы.— ДАН СССР, !957, 117, № 1, с. 9 — !2. 2. Об алгоритмических проблемах в эффективно-полвых классах групп.— ДАН СССР, !953, 123, № 1, с. 13 — !6. 3. Определяющие соотношения и алгоритмические пробяемы для групп и полугрупп.— Тр. матем.
ин-та АН СССР им. В. А. Стеклова, 85, Мл Наука, 1966. Барздннь Я.М. !. Сложность программ, распознающих принадлежность натуральных чисел, не превышающих и, рекурсивио перечислнмому множеству.— ДАН СССР, 1968, 182, № б, с. !249 — 1252, Борисов В. В. 1. Простые примеры групп с неразрешимой проблемой тождества.— Мат. заметки, !969. 6, №5, с.
52! — 532. Б р а у ар Л. Э. Я. (Вгонтчег Ь. Е. Л) 1. Пе опЬе(гошчЬаагйе(8 бег )оя!ьсйе рппс»реь.— Т!)бьсйп!1 чоог тч!!ьЬебеег1е, 1908, 2, с. 152 — !58. Б р и т тон Дж. Л. (ВпИоп Л Ь.) 1. ТЬе»чей ргоЫеш.— Апп. о( Ма(Ь., !963, 77, р. !6 — 32.
Б у н В. В. (Воопе»Ч. '»У.) 1. ТЬе ыогб ргоЫегп.— Апп, о! Ма(Ь., 1959, 70, р. 207 — 265. Гейтинг А. 1. Интуициоинзм. Введение / Пер. с англ. под ред. и с комментариями А. А. Маркова. Мл Мнр, 1965, Гедель К. (Ообе! К.) 1. ОЬег 1оппа! ппеп(ьсЬен1Ьаге 5а!хе бег Рппс(р(а МайешаНса нпб чепчапгйег 5уз1егпе!.— МопайЬ. Рйг Ма1Ь. ппб РЬуь!Ь, 1931, 38, р. 173 — 198. Гильберт Д.
и Бернайс П. 1. Основания математики. Логические исчисления н формализация арифметики ! Пер. с нем., М.: Наука, !979 (2-е изд. 1982 г.). 2. Основания математики. Теория доказательств( Пер. с нем., Мл Науна, !982. Детловс В. К. 1. Нормальные алгорифмы и рекурсивные функции.— ДАН СССР, 1953, 90, № 4, с.
723 — 725. 2. Эквивалентность нормальных алгорифмов и рекурсивных функций.— Тр. матем. ин-та АН СССР им. В. А. Стеклова, 52, М.— Лл Изд. АН СССР, 1958, с. 75 — 139. Д з и М. (Пейн М.) 1. 0Ьег ппепб!!сйе гВь)топНпйег!кйе Огнрреп.— Ма1Ь. Апп., !9!2, 71, 5. ! !6 — 144. Жаров В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
