markov_teorija_algorifmov (522344), страница 28
Текст из файла (страница 28)
В настоящее время нет, однако, никаких признаков, позволяющих ожидать изобретения таких средств. А, как известно, в истории не бывает скачков, не подготовленных предшествующим развитием. Следует принять во внимание и аргументы исторического плана. В тридцатых годах нашего столетия появились основополагающие работы К.
Ге дел я Н1, А. Ч е р ч а 111. С. К. Клини [11, 121, А. М. Тьюринга [11, [21 и Э. Л. П о с т а [П, в которых были точно определены некоторые специальные виды алгорифмов. Для каждого из этих видов возникла уверенность в том, что он с точностью до эквивалентности исчерпывает все алгорифмы.
Иначе говоря, математики прониклись убеждением в том, что всякий алгорифм эквивалентен некоторому алгорифму данного вида. Эта идея стандартизации алгорифмов лежит в основе их современной теории. Вскоре после того, как были выработаны первые стандартные понятия алгорифма, удалось установить, что все предложенные стандартизации эквивалентны друг другу, и когда в дальней- 4 271 (гл. ш 144 НОРМАЛЬНЫЕ АЛГОРИФМЫ НОРМАЛЬНЫЕ АЛГОРИФМЫ 145 шем были предложены некоторые новые стандартизации *), они также оказались эквивалентными ранее Определенным.
Поэтому при рассмотрении алгорифмов „с точностью до эквивалентности" безразлично, какой именно их стандартизацией пользоваться. Мы будем использовать наиболее знакомые нам анормальные алгорифмы». Эквивалентность их рекурсивным функциям, а тем самым и другим стандартизациям, была установлена В. К. Детловсом (см. (1); подробное изложение в !21). В литературе принцип, утверждающий пригодность некоторых конкретных уточнений понятия алгорифма, называется тезисом Черна — в честь выдающегося американского математика Алонзо Черча, впервые провозгласившего этот принцип (применительно к Х-определимым функциям; см. его работу [И).
Принцип нормализации фактически представляет собой вариант тезиса Черча, относящийся к нормальным алгорифмам. Особого внимания заслуживает вариант тезиса Черча, относящийся к машинам Тьюринга. В силу специфики определения машины Тьюринга он обладает высшей степенью убедительности. В самом деле, читатель, знакомый с этим понятием, согласится, что в суи(ественном работа машины Тьюринга адекватно описывает поведение математика-вычислителя, занятого выполнением данного ему предписания: находясь в определенном „умонастроении" и концентрируя свое внимание на определенной текстовой информации, вычислитель предписанным ему образом изменяет эту информацию, „смещает" центр своего внимания и переходит в новое „умонастроение". То же самое способна делать и машина Тьюринга. То обстоятельство, что ее шаги носят гораздо более локальный характер, чем действия реального вычислителя, на самом деле не слишком существенно: каждый „интегральный" шаг работы вычислителя может быть промоделирован серией „локальных" шагов машины Тьюринга.
Приведенные соображения — с учетом эквивалентности машин Тьюринга другим известным стандартизациям понятия алгорифма — являются, быть может, самым сильным аргументом в пользу тезиса Черча, а значит, и принципа нормализации. Принимая, однако, во внимание, что читатель может не разделять уверенности авторов в правильности принципа нор- ь) Наиболее общий подход к уточнению понятия алгорифма предложил А. Н. К о л м о г о р о в (1). Относительно конкретиэапий этого подхода сн. А. Н.
Колмогоров и В. И. Успенский ((й а также А. Ш е н х а г е (1), (2). мализации, авторы отнюдь не собираются навязывать читателю этот принцип, Поэтому в дальнейшем всякие применения принципа нормализации будут делаться явно. Каковы же возможные применения принципа нормализации? Во-первых, он может быть использован для угадывания правильных формулировок тех или иных математических тзысказываний. Допустим, например, что имеется задача, для решения которой требуется построить алгорифм. Пусть эта задача „устойчива" в том смысле, что всякий алгорифм, эквивалентный решающему ее, также ее решает. Предположим, что мы нашли какой-либо алгорифм, решающий эту задачу. Тогда с уверенностью можно утверждать, что существует и решающий ее нормальный алгорифм.
Проблема сводится лишь к тому, чтобы фактически построить его. Зная принцип нормализации, мы не станем пытаться доказывать, что нормального алгорифма, решающего эту задачу, не существует. '»ч Во-вторых, в аналогичной ситуации мы, может быть, сумеем доказать теорему о том, что не существует нормального алгорифма, решающего такую „устойчивую" задачу. Скептически настроенному оппоненту, считающему этот результат „слишком узким и техническим", мы сможем тогда обьяснить, что искать какой-либо другой (ненормализуемый) алгорифм, решающий эту задачу, бесперспективно (хотя, разумеется, мы и не сможем доказать этого математически). В-третьих, принцип нормализации может быть использован для выработки точных определений тех математических понятий, которые в той или иной форме учитывают различные соображения эффективности (вычислнмости, или, как мы предпочитаем говорить, конструктивности).
Обычно в таких определениях естественно возникают ограничения, требующие наличия определенных алгорифмов. Учитывая принцип нормализации, мы говорим тогда о нормальных алгорифмах, в результате чего определение приобретает характер точной математической формулировки. В приведенной выше формулировке принципа нормализации фигурировало понятие полной эквивалентности алгорифмов.
Естественно спросить, что получится, если заменить это понятие в формулировке принципа понятием эквивалентности. На первый взгляд может показаться, что получится некоторый новый принцип, утверждающий нечто меньшее, чем принцип нормализации, а именно: Всякий вербальный алеорифм в алфавите А эквивалентен относительно А некоторому нормальному алгорифму над А.
1гл. Ри НОРМАЛЬНЫЕ АЛГОРИФМЫ Мы увидим, однако, вскоре!э 37.61, что этот „ослабленный" принцип нормализации в действительности является лишь другой формулировкой того же самого принципа. Принцип нормализации мы имеем один *). 2 28. Присоединяющие алгорифмы 1. Возьмем алфавит А такой, что буквы — и — ° не входят в А. Пусть Я вЂ” какое-либо фиксированное слово в А. Обозначим символом 21л,д нормальный алгорнфм в А со схемой В линейной записи эта схема имеет вид ур1;1у.
Ранее Ц 25.11. Ц мы показали, что 1.1. Для всякоао слова Р в алфавите А Я.,д~Р)-1)Р. 2. Пусть А — алфавит, состоящий из букв а, Ь и с; пусть в — буква, не входящая в А; пусть 1',1 — какое-либо фиксированное слово в А. Обозначим символом ВА, д нормальный алгорифм в алфавите Аз со схемой ва ае вЬ Ьв В линейной записи эта схема имеет вид узааазуаЬаЬзузсасзуер 1еуаву. До конца параграфа Р, 14 и 8 будут означать любые слова в алфавите А, а $ — любую букву этого алфавита.
Докажем 2.1. ВА, д. Р )- вР. Действительно, левая часть последней формулы подстановки (пустое слова) входит в Р, тогда как левые части всех предшествующих формул в Р не входят из-за присутствия в них буквы в. Следовательно, алгорифм ВА,д действует на Р 1225.41, причем формулой подстановки, активной на слове Р, является последняя формула схемы. Результатом *) В точности такая же ситуация сложится и в том случае, если мы волную эквивалентность заменим сильной. В вз1 ПРИСОЕДИИЯЮЩИЕ АЛГОРИФМЫ 147 действия алгорифма Вл,д на слово Р является результат действия на Р активной формулы, т. е.
результат подстановки в Р правой части этой формулы (слова е) вместо первого вхождения ж Ф Р ее левой части 1ч 23.6.21, т. е. слово вР [э 23.8.51, и, так как активная на Р формула подстановки — простая, Вюд. 'Р1- вР, что и требовалось доказать. 2.3. ВА, д . 'вРЯ ~= Рз8. Докажем это методом правой индукции по Р. При РХЛ утверждение 2,3 верно тривиальным образом.
Пусть теперь утверждение 2.3 верно для какого-либо Р при любом о. Тогда, в частности, для любой буквы д имеем ВА, д". ЗРсто )= РЕР~. Но в,силу 2.2 ВА, д:Рвьо1 Рьзо ВА, д: вРз'л ~ Рзо3 и потому что и оставалось доказать. Полагая в 2.3 ЗХЛ, получаем 2.4. ВА, дтзР~ Рв. Согласно схеме алгорифма ВА, д имеем 2.6. ВА, д."Ри) — РЯ.
Таким образом, 2.6. ВА, д.Р)= РЯ 12.1, 2.4, 2.51 и, следовательно, что и требовалось доказать. 2.2. ВА, д.' Регат 1- РКеР. В самом деле, алгорифм Вл,д действует на слово Ре$1т', так как на это слово действуют две формулы подстановки его схемы: одна из первых трех, имеющая вид е$ — зе, и последняя. Ясно, что активной на слове Рвай будет формула е$ — $в, так как она предшествует последней формуле схемы.
Имеется единственное вхождение Р ть е$ Ж Р левой части формулы е$- $е в слово РесР,. Следовательно, г оно и будет первым. Результат подстановки правой части активной формулы, т. е. слова $е, вместо этого вхождения ' есть слово РееР, и, так как активная формула подстановки престая, ВА д. 'РЕЯ )- РьсЗР„ 1гл. Ри СОКРАЩАЮЩИЕ АЛГОРИФМЫ $291 148 !49 НОРМАЛЬНЫЕ АЛГОРИФМЫ 2.7. ВА, а(Р)ХРЯ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
