markov_teorija_algorifmov (Марков - Теория алгоритмов), страница 76

Если Я (хи, р) = О, то х»г, и = О и, значит, й не применим к Р !З.Ц. Если же Я(хк, и) ~»О, то неверно, что Я не применим к Р 13,Ц. Таким образом, «) В смысле 4!.6, т. е. полое шсло или „дробь" вида МУМ, где гн— целое, в М вЂ” иатуральнос число, огличипс от нули. мы разработали алгорифм, решающий для Я проблеглу распознавания неприменимости к словам в его алфавите. Этот алгорифм, разумеется, может быть нормализован, и так как й — произвольный нормальный алгорифм, то это дает противоречие с теоремой й 48.2.3.

Таким образом, нормальный алгорифм Я, удовлетворяющий условиям, сформулированным в начале этого пункта, невозможен. Но тогда нет оснований рассчитывать и на существование какого-либо алгори4»ма вообще, т. е. единого общего метода, с этими свойствами. !!осле этого замечания мы предлагаем читателю самому ответить на вопрос: верно ли, что всякое псевдорациональное конструктивное действительное число рационально? 7. Рассмотрение чисел хи, р дает удобный повод отметить еще одно любопытное обстоятельство. Условимся говорить, что число й;6В; мажорируегп число )(;б)В;, если для люоого натурального А( имеет место неравенство Я, (эВ, (Ж)) — й, (9, (Ф)) ) — 2-<" — ' >.

Для обозначения этого отношения, являющегося аналогом обычного нестрогого порядка в множестве действительных чисел, мы по традиции будем пользоваться привычным знаком «>», употребляя знак «(» в естественном смысле. После этого обычным образом может быть введено отношение «>» ), Разумеется, в случае любых двух конструктивных действительных чисел х и у имеет место импликация «если х>у или х= — у, то х)~у». Исследуем вопрос о том, насколько справедлива обратная импликация.

(Подчеркнем, что знак мажорирования и здесь понимается в смысле только что сформулированного определения и а рпоп нет никаких оснований рассматривать его как дизъюнкцию «больше или равно».) Из определения мажорировапия очевидным образом вытекает, что 7.!. Каково бы ни было Р в А, хи, р О**). Допустим теперь, что имеется нормальный алгорифм ьс, пригленимый ко всякому конструктивному действительному *) Оио может быть введено и свмостоятельио — например, следую. щим образом: 2(,'ба»,' > ч(!ба, 'о»качает, что сушесгвует натуральное М такое, что юг (й1(М)) — 21»(8»(М)) > 2 тм ". "») Звпись хем г (х > г) мы, естественно, будем понимать квк хЗ г(х>г).

410 АлГОРНФмы и мАтемАтический АИАлиз 1гл,!х 41! $651 РАСПОЗНАВАНИЕ МАЖОРИРЭВАНИЯ числу х, мажорирующему О, и такой, что х > О, если 6(х)в.Л, и х=О, если 6(х) ф'Л, Возьмем произвольное слово Р в А, построим число хе р и применим к нему алгорифм 6. Если 6(хи р) тЛ, то хк, р > 0 и, значит, Й применим к Р [3.11. Если 6(ха, р) ~СЛ, то хя,р=О и, значит, Й не применим к Р 13.1!. Таким образом, мы получили алгорифм, распознающий применимость нормального алгорифма Й к словам в своем алфавите.

Нормализовав этот алгорифм — что, разумеется, возможно,— мы получим ввиду произвольности Й противоречие с теоремой $ 48.2.4, Итак, мы доказали, что 7.2. Невозможен нормальный алгорифм 6, применимый ко всякому конструктивному действительному числу х, мажорирующему О, и такой, что х > О, если 6(х),е Л, и х=О, если 6(х) ~Г Л. Ввиду принципа нормализации остается мало надежд на получение какого-либо другого (не нормального) алгорифма со свойствами, перечисленными в формулировке теоремы 7.2.

Мы теперь предоставляем читателю самому решить вопрос о том, насколько правомерно дизъюнктивное понимание отношения мажорирования. 8. Основываясь на определениях отношений равенства и мажорирования, нетрудно показать, что имеет место следующее утверждение: 8.1. Каковы бы ни были конструктивные действительные числа х и у, х — — у тогда и только тогда, когда х' .у и у>х. й 66. Распознавание мажорирования.

Арифметические действия. Кусочное задание функций 1. Пусть х — произвольное конструктивное действительное число. Рассмотрим дизъюнкцию (1) «х~0 или х>0». Нетрудно показать, что ни прн каком х оба члена этой дизъюнкции не могут быть неверными. Возникает поэтому проблема разыскания алгорифма, который позволял бы находить по х верный член дизъюнкции (!).

(Заметим, что, в отличие от дизъюнкции э 64.1 (1), верными могут оказаться оба члена рассматриваемой дизъюнкции.) 2. Прежде чем перейти к непосредственному решению сформулированной проблемы, мы проведем следующее построение. Фа. Р(М+1) = (' Юя, Р (М + 1) если Юи,1 (М+ 1) эь Жа, Р (М), если 6з, р (М+1) =*Фл, Р (М) и Й(Р) м.а, если Эв, р(М+1) =*Юз. Р'.(М) и Й(Р)ХЬ. — Е,, Р(М+1), ея, Р(М+1) Независимо от того, каково Р, нормальный алгорифм 3 такой, что 3(М) в'М+1, является регулятором сходимости для фк, р, н потому слово,Я р63' представляет собой конструктивное действительное число. Мы условимся обозначать зто число символом уэ,р.

Принцип нормализации подсказывает нам, что может быть построен нормальный алгорифм (6 такой, что Я'(Й'5КР) тг утс р. Это действительно так, и в дальнейшем мь1 будем считать это построение выполненным. 3. Предположим теперь, что имеется нормальный алгорифм 6, применимый ко всякому конструктивному действительному числу х и такой, что если 6(х)м.Л, то х(0, и если 6(х) 1СЛ, то х>0. Зададим следующий алгорифм 9 в алфавите А,. Предписывается взять произвольное слово Р в А„при помощи алгорифма й из п.

2 построить число и г к р и применить к нему алгорифм 6. Если окажется, что (уи г)хЛ, то положить В(Р) — а. Если же 6(уи, Р) будет отлично от Л, положить В (Р) = Ь. Учитывая принцип нормализации, мы будем считать алгорифм В нормализованным, Зафиксируем какой-либо нормальный алгорифм Й над алфавитом А, такой, что всякий раз, когда он применим к какому-либо слову Р в алфавите А„он перерабатывает его либо в а, либо в Ь. Пусть Р— произвольное слово в алфавите алгорифма Й.

Способом, указанным в э 64.3, построим сначала нормальный алгорифм 5М Р, а затем конструктивную последовательность рациональных чисел 15)в, . Из условий, которым удовлетворяет алгорифм )уя, р'1см. 3 64.21, легко усматривается, что равенство Ее, Р(М+1)= =Фи,, (М) для какого-либо М имеет место тогда и только тогда, когда Й применйм к Р. Построим теперь конструктивную последовательность рациональных чисел 9в р так, чтобы выполнялись равенства 0...(о)=е,,(о) ллгогнемы и млтвмлтичзскнп хнллиз [гл. 1х 4!2 4 мл Рхспознлзлн ие млжОРИРОВлния 413 т.

е. будем считать, что он есть нормальный алгорнфм над А,. Из описания В усматривается, что он применим ко всякому слову Р в А, и что 2(Р) есть либо а, либо Ь. Покажем, что В является пополнением Й относительно А,. В самом деле, пусть Р— произвольное слово в А, и пусть Я применим к Р. Тогда Й (Р) з а или Й (Р) и Ь. В первом случае уч, р= — 2-<к:г>, т. е. дч, р < О. Но тогда б(ук,г) мЛ, так как из 6(дя р) 3«Л следовало бы, что уя г »О. Значит, тогда В(Р) о а.

Таким образом, в этом случае В(Р) ХЙ (Р). Во втором случае Й (Р) мЬ, и потому у, р =2 ппе>, т. е. уь, р) О. Но тогда 6(уэ р)-д Л и, значит, В (Р) ХЬ. Таким образом, и в этом случае В(Р) м.Й (Р). Итак, в обоих случаях В(Р)м.Й(Р), и, значит, В действительно является пополнением Й относительно А,. Итог нашего рассмотрения состоит в том, что если существует нормальный алгорифм 6 со свойствами, указанными в начале данного пункта, то всякий нормальный алгорифм Й со свойствами, перечисленными в начале п. 2, пополним относительно А„что противоречит теореме 3 63.1,1. Итак, мы доказали, что имеет место следующее утверждение (Г.

С. Цейт и н [31): 3.1. Невозможен нормальный алгорифм (ч, применимый ко всякому конструктивному действительному числу х и такой, что х ( О, если Хь. (х) ~ Л, и х ) О, если [з (х) ф' Л. 4. В дальнейшем нам понадобится ряд обычных арифметических действий над конструктивными действительными числами, К их определению мы сейчас и перейдем. Пусть й;69; и Й[6В',— два конструктивных действительных числа. Конструктивные последовательности рациональных чисел Й„Й, и Я, мы будем называть соответственно суммой, разностью и произведением последовательностей Й, и Й„если для любого натурального М имеют место равенства Й, (М) =Й, (М)+ Я,(М), Й, (М) = Я, (М) — Й, (М), Й,(М)=Й,(М) Й,(М).

Легко показать, что последовательности Я„ Я, и Й, являются фундаментальными. Именно, нормальный алгорифм 5 в Р+ такой, что для любого натурального М 9(М) шах(64(М+1), й)»(М+1)), является регулятором сходичостн для последовательностей 31, и Й,. Если, далее, Л[ †натуральн число такое, что [Й,(М)[ < 2м и [Я,(Л')/ ( 2»', то нормальный алгорифм (Х в Р+ такой, что для любого М «г(М)=шах(В,(М+ЛХ+1), М,(М+64+1)), является регулятором сходимости для последовательности Й, Таким образом, слова Й16З' 31»65' и Й166' суть конструктивные действительные числа.