markov_teorija_algorifmov (522344), страница 41
Текст из файла (страница 41)
ложение к противоречию, не проводя построения 6 („ чистое доказательство существования" методом «от противного»). Во многих случаях такие неконструктивные доказательства '~, оказываются в техническом отношении более простыми, чем ,, соответствующие конструктивные. И это понятно — в них не ;,", требуется построения. Однако это не должно вводить нас в соблази. В принципиальном отношении конструктивное доказательство существования все-таки проще: здесь не надо задумываться над тем, почему существование должно пониматься столь косвенным образом, что существующим может оказаться '1 Более подробна об этом см, $ 54,5, 219 ОБЪЕДИНЕНИЕ ДЛГОРИФЫОБ 218 СОЧЕТАНИЯ НОРМАЛЬНЫХ ЛЛГОРИФМОН 1ГЛ. Ш и объект, к разысканию которого не видно никаких подступов.
Что же касается понимания существования как потенциальной осуществимости, то оно представляется нам естественным и в принципиальном отношении — простым. Впрочем, в техническом отношении проблема нахождения конструктивного доказательства тоже может оказаться более простой, чем соответствующая проблема нахождения „чистого доказательства существования*'. Например, мы не видим, как опровергнуть предположение о несуществовании нормального алгорифма Сг из теоремы 1.1, не построив его фактически. Мы специально хотели бы обратить внимание читателя на это обстоятельство.
6 *). Покажем теперь, что принцип нормализации алгорифмов $27.6) равносилен следующему высказыванию: 6.1. Всякий алгорифм в алфавите А эквивалентен относительно А некоторому нормальному олгорифму над А. Допустим, что утверждение 6.1 верно, и рассмотрим какой-нибудь алгорифм й в алфавите А. Покажем, что 111 вполне эквивалентен некоторому нормальному алгорифму над А. Согласно 6.1 имеется нормальный алгорифм В над А, эквивалентный 91 относительно А. Обозначим через Б его алфавит. Имеем (') АсБ.
Построим нормальный алгорифм хх в Б со схемой (е й, где $ пробегает алфавит Б' А. Очевидно, что б(Р)ХР (Р— слово в А) (2) и что чь не применим ни к какому слову в Б, не являющемуся словом в А. Построим алгорифм Р как нормальную композицию алгорифмов В и (6; (3) чх -.— ((УоВ), ч) Этот пункт является естественным продолжением 4 27, Выскззывзние 6.1, кзк и принцип нормализации, не может рзссмзтрнвзться кзк имеющее точный математический смысл. То жс сзмое можно сказать и относительно утверждения о их рзвносильносзи.
Теи не менее зто последнее можно считать достаточно понятным. есть нормальный алгорифм над Б и ) 2(Р) ~СЕ(В(Р)) (Р— слово в Б) ~(3)1. Отсюда следует, что 5) В (Р) ~ В(Р), ли Р и В(Р) суть слова в А [(4), (2)~. Покажем, что В есть искомый нормальный алгорифм ад А, вполне эквивалентный Я. Ж есть алгорифм над А ввиду (1). Если алгорифм Я применим к слову Р в А, то Р и л (Р) :суть слова в А, так как Я вЂ” алгорнфм в А. Поэтому тогда 'и В применим к Р, и мы имеем 121(Р) В(Р). силу (5) отсюда следует, что (6) 111 (Р) Тз (Р). 'Таким образом, равенство (6) имеет место, коль скоро влгорифм Я применим к слову Р в А.
Допустим теперь, что алгорифм Ж применим к слову Р 'в А. Тогда и алгорифм В применим к Р 1(4)1, а алгорифм — к В(Р). Поэтому и В(Р) есть слово в А. Но тогда и лгорифм 3Т применим к Р ввиду эквивалентности алгоифмов 111 и В относительно А. Следовательно, алгорифм применим к слову Р в А, коль скоро к нему применим ' лгорифм Р. Мы доказали таким образом, что алгорифм Р~ вполне экви' алентен алгорифму й относительно алфавита А. Тем самым мы доказали, что принцип нормализации вытекает нз утверждения 6.1.
Обратное очевидно. Следовательно, принцип нормализации равносилен утверждению 6.1, что и требовалось доказать. В 36. Объединение алгорифмов 1. Часто приходится совместно рассматривать результаты аботы двух или нескольких алгорифмов над одними и теми е исходными данными. В этом случае полезным может окаться построение системы всех этих результатов. Она может, ' апример, сама служить в качестве исходного данного при аботе какого-нибудь другого алгорифма. Так, если нам уже даны алгорифмы вычисления значений нкций (х+2) и (х+3) для натуральных значений перемен- 22О сочетАния нОРмАльных АлгогиФмОВ [Гл.
Р« 881 Овъединение АлГОРиФИОЕ ной х, алгорифм вычисления значений функции (1) (х+2) х (х+3) можно построить как следующее предписание: исходя из произвольно данного натурального числа Ф, вычислить числа (%+2) и (У+3) с помощью двух данных алгорифмов, построить пару этих чисел и применить к ней алгорифм умножения. Первые два этапа этого предписания образуют алгорифм, перерабатывающий всякое натуральное число в пару чисел (7«'+2) ж (А(+3).
Композиция этого алгорифма с алгорифмом умножения составляет искомый алгорифм вычисления значений функции (1). Таким образом, если даны вербальные алгорифмы Й и 'ю', то может оказаться целесообразным построить следующее предписание: «исходя из произвольного слова Р в объединении А алфавитов этих алгорифмов, развернуть процессы применения к нему алгорифмов Й и 9. Если оба эти процесса закончатся, то построить слово Й (Р) 6 (Р) и считать его результатом».
Это предписание, как мы видим, составляет некоторый алгорифм в алфавите А †«объединение> данных алгорифмов Й и В. Естественно спросить, является ли объединение нормализуемых алгорифмов также нормализуемым алгорифмом? Принцип нормализации подсказывает утвердительный ответ на этот вопрос, и, действительно, в этом параграфе мы докажем следующую теорему: 1.1. Тео рем а объеди н ен и я. Пусть Й и Э вЂ” нормальные алгорифмы, А — объединение их алфавитов.
Тогда может быть построен такой нормалычый алгорифм 6 над А, что длл любого слова Р в А имеет место условное равенство (2) 6 (Р) ~ Й (Р))Б (Р). 2. Доказательство этой теоремы составляет главное содержание данного параграфа, Мы начнем с доказательства следующей теоремы: 2.1. Каковы бы ни были нормальные алгорифмы Й и 2) в алфавите А, может быть построен такой нормальныи алгорифм 6 иад А, что для любого слова Р в А имеет место условное равенство (1) 6(Р) Й(Р) 2) (Р). Для доказательства введем алфавит А двойников букв алфавита А, как в доказательстве теоремы 2 37.2,1. Двой- ик буквы $ будет по-прежнему обозначаться через $, двой:ник слова Р— через (Р .
Положим Б — АА. Введем следующие нормальные алгорифмы над А: алгорифм гс, побуквенного кодирования (см. 2 33.1) твой, что для любой буквы $ алфавита А «код» ее КЕ есть слово Ц: (2) КгоЦ алгорифм м', побуквенного кодирования такой, что для любой буквы $ алфавита А ' (3) КЕХ3, К1Х3; алгорифм ь«, двойного проектирования (см. 3 33.3) такой, что для любого слова Р в Б (4) В,(Р) Г " Г'; алгорифм В, двойного проектирования такой, что для любого Р в Б )м,(Р)АХР, [й (Р) ~1Р- (5) Р (р) -к ГРА [РА.
Й вЂ” нормальный алгорифм в А, схема которого получается из схемы алгорифма Й путем замены каждой буквы ее двойником; Й, †естественн распространение алгорифма Й на алфавит Б; ю', †естественн распространение алгорифма 5 на ал'фавит Б. Построим нормальный алгорифм 6 как нормальную композицию . (6) (Я»о(Й,о(В»о(6,о(В,ой,))))). % Так как уже м«есть алгорифм над А, то 6 и подавно ~,есть нормальный алгорифм над А 12 37.1.1].
Покажем, что :. для 6 имеет место условное равенство (1). Предварительно :докажем некоторые леммы. Р означает в них произволь:«ное слово в алфавите А. 2.2. В, (1Г, (Р)) Х Р (Р Сначала методом правой индукции показываем, что для любого Р в А (7) (8) 1гл. Рн СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ 81 ОБЪЕДИНЕНИЕ АЛГОРИФМОВ 223 Затем В,(Я,(Р)) ь [11 (Р)А[11 (Р) [(4)] ~ Р [Р- [(7), (8)], что и требовалось доказать. 2.3. 2),(В,(а,(р))) = З(р) [ —. В самом деле, так как В,— естественное распростране- ние ю на Б, имеем 6, (9, ф, (Р))) Б~, (Р [Р-) [2.2] 2) (р) [р- [3 35,2(1)].
2.4. О, (2), (В, (й1 (Р)))) [Р 'В (Р). В самом деле, О (щ (В (17 (р)))) О (6(р) [Р-) [2.3] [р-2) (р) [(5)]. 2.5. 21([Р ) [й (Р) Это непосредственно следует из определения алгорифма й. 25. й (В (Б (' (Я,(,)))))=[21(Р)-Е(р). В самом деле, так как '?(,— естественное распростране- ние й иа Б, имеем й, (8, (э1, (о, (й, (р))))) 21, ([р-я) (р)) [2,4] й ([Р-) э) (Р) [2 35.2(1)] = [й (р)-Е (р) [2.5], 2.7. й,(Я й) ь (~й (Я, й — слова в А) Это непосредственно следует из определения (3) алго- рифма,й,. 2.8. а,(й, (О,(4), (В, (я, (Р)))))) = й (р) Ъ(р).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
