markov_teorija_algorifmov (522344), страница 74
Текст из файла (страница 74)
Нормальный алгорифм й в алфавите Р+ мы будем называть нонструнтивной последовательностью рациональных (соответственно натуральных) чисел, если он применим ко всякому натуральному числу и перерабатывает его в некоторое рациональное (соответственно натуральное) число. Число й (Ф) мы' будем называть М-м членом последовшпельности й. Пусть й †конструктивн последовательность рациональных чисел. Конструктивную последовательность натуральных чисел 9 мы будем называть регулятором сходи- мости последсвательносгпи й, если для любых натуральных Т., М и [)Г из М, М ) В(Т.) следует, что [й (М) й ()У)! С 2- . Конструктивную последовательность рациональных чисел мы называем фундаментальной, если может быть построен ее регулятор сходимости.
Конструктивным действительным числом мы будем называть всякое слово вида й'69', где й †фундаментальн конструктивная последовательность рациональных чисел, 'й) — ее регулятор сходимоаги, а 6 †разделительн знак. 2. Обращаем внимание читателя на то, что конструктивное действительное число представляет собой некоторое слово е) Том «Трудов математического института им. В. А. Стеклова АН СССР», в который входит эта статья, целиком посвящен проблемам конструктивного анализа, 400 АлгориФмы и мАтемлтический АнАлиз 1гл. 1х в алфавите аЬ6. Это слово содержит в себе информацию о двух алгорифмах, первый из которых порождает „хорошую" (вычислимую) фундаментальную последовательность рациональных чисел, а второй по заданной точности позволяет эффективно находить в этой последовательности место, начиная с которого заданная точность гарантируется.
Данное определение в общих чертах „подражает" канторовскому определению действительного числа через фундаментальную последовательность рациональных чисел, но выгодно отличается от него в отношении возможности эффективного приближения действительных чисел рациональными. Заметим (для сравнения см. 3 53.1), что понятие конструктивного дейсгпвительного числа мы определяем самостоятельно, не ссылаясь на общее понятие действительного числа. Поэтому конструктивный континуум может рассматриваться вполне самостоятельно, в отрыве от классического континуума (хотя, конечно, он естественным образом и порождает некоторое «хорошее» подмножество последнего). 3.
Два конструктивных действительных числа й;66 и й,'651 мы называем равными, если для любого натурального М 1йт (я)а (й))) — й, (6, (М)) 1( 2-1"-'1. Для отношения равенства конструктивных действительных чисел мы будем употреблять привычный знак «=ж В таком виде понятие конструктивного действительного числа было введено в литературу Н. А, Шаниным в 121. В этой работе можно найти подробное и прокомментированное изложение истории формирования этого и родственных ему понятий. 4.
Теперь мы перейдем к формулировке определения конструктивной действительной функции. Для этого мы зафиксируем какое-либо двухбуквенное расширение Д алфавита аЬуб, в котором будем записывать у-системы конструктивных действительных чисел. Две такие системы мы будем называть равными, если они имеют равное число членов и если их члены с одинаковыми номерами представляют собой равные конструктивные действительные числа.
Нормальный алгорифм й в алфавите Д мы будем называть конструктивной действительной функцией М переменных, если для любых двух равных М-членных систем 5 и Т конструктивных действительных чисел нз того, чтой (3) опре- % а21 КОНСТРУКТИННЫЕ ЧИСЛА И ФУНКЦИИ 401 делена, следует, что й(Т) также определено и что й(З) и ~ й(Т) суть равные конструктивные действительные числа. Таким образом, конструктивная действительная функция ставит системам своих аргументов в соответствие конструктивные действительные числа с соблюдением естественного требования согласованности; на двух равных системах функция определена одновременно и в случае определенности принимает равные значения.
Такое понятие конструктивной действительной функции, являющееся конструктивным аналогом восходящего к Дирихле понятия точечного отображения, было введено А. А. Марковым (1!01, 1111). Историю вопроса и разбор родственных понятий можно найти в уже упоминавшейся работе Н. А. Ш а н и н а 121. 5. Введем еще некоторые, нужные для дальнейшего понятия. Пусть г — какое-либо фиксированное рациональное число. Обозначим символом й, нормальный алгорифм в алфавите Р+ такой, что для любого натурального М й„(М) и г. Алгорифм й, является конструктивной последовательностью рациональных чисел и, как легко видеть, фуидаментальной, потому что алгорифм й, является регулятором сходимости для й,.
Таким образом, слово й;бйа представляет собой конструктивное действительное число. Мы будем называть его действигпельным образом рационального ! числа г. В качестве обозначения для этого числа лты нзберем символ г. Пусть х — конструктивное действительное число. Мы будем называть его рациональным *), если может быть указано такое рациональное г, что х=-г. Мы будем называть х иррациональным, если оно не рационально, и псевдорациональным, если оно не иррационально. В дальнейшем вместо х=г мы будем писать х=г. Легко видеть, что всякое рациональное конструктивное действительное число является псевдорациональным.
Вопрос о том, в какой мере справедливо обратное утверждение, мы рассмотрим в и. 5 следующего параграфа. г а) Обращаем внимание чктателя на то, что рациональное конструктивное действнтелмюе число не есть рациональное число в том смысле, ! как мы его определили в й 1.6. Разумеется, в классическом аналнте тоже проводится различие между рациональными н рацнональнымн действнтельнымн числами.
14 А. А. Марко», Н. М. Нагорный 403 402 АЛГОРИФМЫ И МАТЕМАТИЧЕСКИЙ АНАЛИЗ 1гл. 1х ПРИМЕР ШПЕККЕРА кэ 66 Пример Шпеккера 1. В этом параграфе мы изложим один, играющий в основаниях анализа принципиальную роль, результат Э. Ш п е кк е р а П), который проливает свет на вопрос об эффективности операции взятия верхней грани ограниченного числового множества (в рамках теоретико-множественных представлений существование этой грани, как читатель хорошо помнит из курса анализа, обеспечивается известной теоремой Вейерштрасса).
Именно, мы покажем, что 1.1. Может бить построена ограниченная неубывшощая конструктивная последовательность рацион льных чисел пиная, что невозможен ее регулял1ор сходимости. В настоящее время известно несколько различных доказательств этой теоремы. Мы приведем одно из них, близкое к первоначальному доказательству Шпеккера. Чтобы по возможности более отчетливо изложить замысел, лежащий в основе конструкции Шпеккера, мы позволим себе не строить некоторые требующиеся по ходу дела нормальные алгорифмы, а лишь сослаться на возможность их построения.
Вооружившись терпением, читатель без особых усилий восполнит пробелы, которые у иас таким образом возникнут. Итак, пусть Я вЂ” какой-либо нормальный алгорифм. Обозначим посредством А алфавит этого алгорифма. Перенумеруем каким-либо „хорошим" способом слова в А (например, упорядочим их по длине, а при равных длинах — лексикографически). Слово с номером М мы будем обозначать символом Р . Ясно, что имеются единые конструктивные методы (алгорифмы) для нахождения номера заданного слова и для восстановления слова по заданному номеру. Принцип нормализации (2 27.6) подсказывает нам, что эти алгорифмы могут быть оформлены в виде нормальных (и это действительно так, в чем читатель может убедиться самостоятельно).
Зафиксируем теперь натуральное число Е и будем применять к слову Р, алгорифм Я, вычисляя по ходу применения арифметическую функцию 1ю ш значение которой для произвольного натурального числа М определяется следующими условиями: 1) )„ с(М) =О, если процесс применения Я к Р, не закончился за число шагов, меньшее М; 2) гю А(М) 1, если процесс применения Я к Р1 закончился за число шагов, меньшее М. Легко видеть, что ь, . для вычисления значений этой всюду еи значения 0 и 1 оп еделенной, монотонной, принимающей значения и апре функции 1ь имеется я единый конструктивный метод, ал- .
П рмализации подсказывает нам, что существует тогда и нормальный алгорифм, вычисляющии значения этой функции. . В дальнейшем мы будем считать„что какой-нибудь такой нормальный алгорифм $ч с зафиксирован. Легко сообразить, что 1.2. Алгорифм Я применим к слову Р в А тогда и только тогда, когда существует натуральное число М такое, что 54, с(М)=1, где Š— номер слова Р.
Для любого натурального М положим теперь Вз, 1(Н) зв (М) ~л~, — ' 1=а Рациональнозначная функция зк определена иа любом еле и для вычисления ее значений имеется натуральном числе и нам, алгорифм. нова пр ф, С принцип нормализации подсказывает о. что этот алгорифм мо ф может быть задан в виде нормальног .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
