markov_teorija_algorifmov (522344), страница 75
Текст из файла (страница 75)
Предполагая тре ую б щееся здесь построение выполненным, мы обозначим полученный нормальный алгорифм посредством Яч. Итак, для любого натурального М имеет место равенство пк, 1(А') 1, (-=а! (М) =Х, —. а=а Значит, с41 пе 3, а перерабатывает всякое натуральное число в ациональиое. Соглас о т ореме риведеии ( считать, что Жк есть нормальный алгорифм в Р+ (см. Таким образом, ба! представляет собой конструктивную посл едовательность рациональных чисел. Простая проверка показывает, что дл ° я любого М выполняются неравенства Ок (М) С Ьз (М+ 1) и я о< С„(М) с~~',—, С2. 1 =а 21 установим теперь, что дова- 1.3.
Если существует регулятор сходимости после овательнос1ни Едк, тв у разрешима проблема распознавания применимости алгорифма Я к словам в алфавите А. ~ «« АлГОРНФмы и мхтемАтичгскип АнАлиз !Гл. !х пРОВлем« РАспОзнАВАния РАВенстВА чисел 405 В самом деле, пусть Ь' — регулятор сходимости О«. Построим нормальный алгорифм 6 в алфавите Р+ так, чтобы для любого У выполнялось равенство 6(У) тг шах (У„М) (У)) (детали построения мы снова оставляем читателю).
Так как для любого У 6(У) ) !В(У), то 6 также является регулятором сходимости для ЯВ. Возьмем теперь какое-либо слово Р в А, и пусть У— его номер. Пусть К) 6(У). Тогда 1~. (К) — !~(6(У))! <— 2'« и, так как последовательность Ы! монотонна, знак абсо лютной величины может быть снят: вк (К) — Ык(6(У)) < —. 2м Следовательно, В (м! 2. "; КВ, !(К) ~~-, !««с !(!! (А!)! =о 2' ! о г' 2А! н потому ч(Ф! 2.' .' '< —. ° 5«(к! — 5„! (6 (У)) 2! гм Все слагаемые этой суммы неотрицательны.
1(роме того, в силу выбора 6, У <6»(У). Г1оэтому О< 2А м ° а значит, и О «$«!, м(К) — $«!, м (6(У)) < 1. Вспомнив, что функция, представляемая алгорифмом $», А!, не убывает и принимает в качестве значений О и 1, мы заключаем отсюда, что для любого К) 6(У) имеет место равенство 5»!.
и(К) 9»с А:(6(У)). Вычислим теперь $В, х (6 (У)). Если окажется, что (у«, А (6(У)) =1, то мы сможем утверждать, что алгорифм 6! применим к слову Р [1.2). Если же окажется, что , (К) = О для любого К: дли К =- 6 (У) — в силу только что доказанного; для К < 6 (У)— в силу монотонности фю А.
Таким образом, в этом случае не существует А4 такого, что $», р~ (гИ) 1, а потому Й не применим к слову Р !1.21. Итак, мы разработали алгорифм, позволяющий по произвольному слову Р в А выяснить, применим ли алгорифм й к Р. Оформив этот алгорифм в виде нормального, мы завершим доказательство утверждения 1.3.
Теорема 1.! теперь получается без труда. В самом деле, достаточно взять какой-либ!о нормальный алгорифм 6!! с неразрешимой проблемой распознавания применимости !$ 48.2.4! н построить соответствующую ему конструктивную последовательность рациональных чисел ЬВ. 2. Теорема 1.1 показывает, что так называемые «чистые» теоремы существования» классического математического анализа иногда могут оказываться очень ненадежным ориентиром в условиях реальной вычислительной практики. $ 64.
Проблема распознавания равенства действительных чисел 1. Математик, придерживающийся традиционной теоретико-множественной точки зрения, считает дизъюнкцию (1) «х=О или неверно, что х=О», где х — произвольное действительное число, верной автоматически. Для него она является простым следствием общего логического закона — «закона исключенного третьегом Между тем проблема фактического выяснения по х, какой именно из членов дизъюнкции (1) является верным, может оказаться трудной даже при очень благоприятных обстоятельствах. Пусть, например, х задано в виде бесконечной десятичной дроби такой, что имеется алгорифм, позволяющий вычислит» любой ее разряд (такой алгорифм, разумеется, возможен далеко не всегда).
Так как мы не'вправе требовать какой-либо ббльшей информаций, на ум йе приходит ничего другого, кроме как пытаться вычислять х с все возрастающей точностью. Но сколько бы знаков х мы ни вычислили, если все они равны нулю, мы ничего об х сказать ие в состоянии: вполне воз»южно, что следующий знак окажется отличным от нуля. Таким образом, если х=О, этот „прямой" метод к цели не ве- 406 АЛГОРИФМЫ И МАТЕМАТИЧЕСКИИ АНАЛИЗ )гл. 1х дет Мы будем стремиться показать, что никакой другой метод тоже не может решать интересующей нас задачи. И тем не менее во многих рассуждениях и вычислительных схемах анализа встречаются точки разветвления, когда предлагается „посмотреть", равно ли нулю значение такой-то величины, и в зависимости от этого рассуждать или поступать так или иначе.
Типичным примером является схема нахождения корня непрерывной знакопеременной функции «методом деления отрезка пополамм Здесь с самого начала предлагается „посмотреть", равно ли нулю значение функции в середине отрезка, и в зависимости от этого продолжить или оборвать процесс. Поскольку никакого реального способа выяснить интересующий иас в этой ситуации вопрос нет,уже первый шаг процесса в общем случае оказывается невыполнимым. К рассмотрению этого примера мы вернемся в 5 б8, а сейчас докажем следующее утверждение: 1.1.
Невозможен нормальный алгорифм, применимый ко всякому конструктивному действительному числу и перерабапинваюи(ий ато число в пустое слово тогда и только тогда, когда оно равно нулю. 2. Прежде чем непосредственно перейти к доказательству этой теоремы, мы проведем следующее рассмотрение. Зафиксируем какой-либо нормальный алгорифм Й и обозначим его алфавит буквой А.
Пусть Р†произвольн слово в А. Развернем процесс применения Й к Р и по ходу этого процесса будем вычислять арифметическую фуНКЦИЮ )чь р, ПОЛОЖИВ й/, если работа Й над Р не закончилась по прошествии А) шагов; г" Р( ) ~ (Й:Р), если работа Й над Р закончилась за число шагов, не превосходящее й(*). Как мы видим, для вычисления значений функции )и, р имеется алгорифм. Без особого труда может быть построен и соответствукаций нормальный алгорифм $и, р.
Более того, может быть построен нормальный алгорифм, который пару, состоящую из записи Й и слова Р, перерабатывает в запись Яи, р. С учетом принципа нормализации мы будем считать это построение выполненным. Теперь нетрудно убедиться, что имеет место следующее утверждение: ь) Напоминаем, что (тй:Р) означает число шагов алгорифма Я при работе иад словом Р (см.
4 27.3 и 1 25.61. $641 пРОБлемА РАспознАВАния РАВенстВА чисел 407 2.1. Алгорифм Й не применим к слову Р тогда и только тогда, когда для любого й) 5и, р(Ф)Х)ч. 3. Существует алгорифм, который всякое натуральное -5 р (н) число )ч' перерабатывает в рациональное число 2 Разумеется, этот алгорифм тоже может быть нормализован, причем в качестве алфавита результирующего нормального алгорифма может быть взят алфавит Р+.
В дальнейшем мы будем считать такой нормальный алгорифм построенным и будем обозначать его символом Фи, р. Вспоминая определение, мы видим, что этот алгорнфм представляет собой конструктивную последовательность рациональных чисел. Кроме того, каковы бы ни были М, У~а'., при любом Р*) имеет место неравенство ) ) Е,,(М) — (А)н.
Р(й))) < —, так что тождественный нормальный алгорифм 3 в алфа- вите Р+ является регулятором сходимости этой последова- тельности. Следовательно, слово Е', 83' при любом Р является конструктивным действительным числом. Мы обозначим его символом хи, р. Здесь снова построение хз, р по Й и Р может быть нормализовано, и мы будем считать эту нормализацию произведеннои. Нетрудно видеть, что 3.1. хт р=О тогда и только тогда, когда алгорифм Й не применим к Р, 4. Теперь становится ясно, что если существует нормальный алгорифм, распознающий равенство конструктивных действительных чисел нулю, то существует и нормальный алгорифм, распознающий среди слов в алфавите А те из ннх, к которым алгорифм Й не применим.
В самом деле, пусть какой-либо нормальный алгорифм б распознает равенство конструктивных действительных чисел нулю. Берем слово Р в алфавите А, строим конструктивное действительное число хи, р и применяем к нему алгорифм (4. Если оказывается, что хи, р=О, то алгорифм Й не применим к слову Р. Если же хи, рчьО, то это неверно. ') Здесь не надо отдельно разбирать случаи, когда Й применим и когда Й не применим к слову Р. 4 Яэ) 4ОЭ 40З ллгорифмы и млтемлтичвский лнллиз (гл, гх )1 ппоглгмх плспознлвлиия плпгистпл чпгшл Мы получили, таким образом, алгорифм, решающий проблему распознавания неприменимости алгорифма й к словам в своем алфавите.
Принцип нормализации подсказывает нам, что этот алгорифм может быть нормализован, и это действительно так. Но это дает противоречие с теоремой 2 48.2.3, согласно которой существует нормальный алгорифм с неразрешимой проблемой распознавания неприменимости к словам в своем алфавите. Итак, нормальный алгорифм, распознающий равенство конструктивных действительных чисел нулю, невозможен. Теорема 1.1 доказана. 5. Анализируя способ задания чисел хи е, мы видим, что они устроены достаточно просто. В самом деле, если алгорифм й не применим к слову Р, то хи, р=О (З.Ц и, значит, в этом случае хи и рационально.
Нетрудно также видеть, что если Я применим к Р и (й: Р) = и, то хк, р = 2 ', и, значит, хи р рационально и в этом случае. Таким образом, имеет место следующая импликация: (1) «если й применим к Р или й не применим к Р, то конструктивное действительное числохк, р рационально». Математик, признающий «закон исключенного третьего» универсальным логическим законом, делает отсюда вывод, что всякое число хи, р рационально. Нам, однако, кажется более осторожным следующее рассуждение: Возьмем любое из чисел хи, р и предположим, что оно иррационально, т. е, не рационально. Тогда посылка импликации (1) неверна, и, значит, неверны оба ее дизъюнктивиых члена, т. е.
1) Я не применим к Р и 2) неверно, что Я не применим к Р. Мы получили, таким образом, противоречие. Следовательно, любое из чисел хгс р не иррационально и потому, согласно определению, псевдорационально. 6. Предположим теперь, что имеется нормальный алгорифм Я, применимый ко всякому псевдорациональному конструктивному действительному числу и перерабатывающий его в рациональное число *), которому оно равно. Возьмем произвольное слово Р в А, построим число хи, р и применим к нему алгорифм Я.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
