markov_teorija_algorifmov (522344), страница 27
Текст из файла (страница 27)
Формулы подстановок (9 25.2], являющиеся членами г., мы будем называть формулами иодстаногок алгорифма Й (они, как мы помним, бывают простые и заключительные). Исходными данными для работы алгорифма Й будут служить слова в алфавите А. Применить алгорифм й к слову Р в алфавите А означает применить к Р схему алгорнфма Й, т. е. схему Я. Таков наш замысел. Детали определения мы оставляем до п. 4. 3. Алфавит а()у, как мы видим, играет здесь вспомогательную роль. Его буквы являются как бы „знаками препинания" в схеме: у отделяет друг от друга формулы подстановок, а а и (» отделяют левые части этих формул от их правых частей, одновременно указывая иа тиа формулы подстановки (а у простых формул, р у заключительных). Буквы эти можно раз и навсегда каким-либо образом зафиксировать, потребовав, чтобы в дальнейшем рассматривались только алфавиты А, не ! содержащие этих букв.
Тогда всякий нормальный алгорифм, по существу, будет определяться указанием двух объектов: алфавита, в котором он действует, и некоторой схемы — схемы этого алгорифма. Нормальный алгорифм, алфавитом которого является алфавит А, мы будем называть нормальным алгорифмом в алфазитг А. Таким образом, при фиксированном алфавите А всякий нормальный алгорифм в А будет определяться указанием одной лишь его схемы.
Это обстоятельство позволяет нам в известном смысле отождествить нормальные алгорифмы с определяющими их схемами и перенести на нормальные алгорифмы всю терминологию и все обозначения, разработанные для схем в 9 25. Так, например, если Й вЂ” нормальный злгорифм, определяемый схемой Я, то записи й:Р)=9, Й:Р~= 9, й:Р(, Й:Р~Ц, 1Й (Р), (Й: Р) будут означать то же самое, что и записи <гл.
Рн НОРМАЛЬНЫЕ АЛГОРИФМЫ )4! НОРМАЛЬНЫЕ АЛГОРИФМЫ $27! )4О соответственно. Сходным образом будут пониматься н другие аналогичные записи. В разного рода словесных формулировках мы вместо «схем» часто будем говорить о «нормальных алгорнфмах», всякий раз производя необходимые грамматические согласования. Сказанное касается н методов индукции, обоснованных в пп. 9 и 10 Э 25. В дальнейшем ссылки на э 25 следует понимать с учетом данного замечания. 4. Теперь дадим подробное определение нормального алгорифма. Всякий нормальный алгорифм представляет собой предписание, однозначно определяемое объектами, указанными в п.
1, и в свою очередь однозначно определяющее течение некоторых конструктивных процессов специального типа. При фиксации нормального злгорнфма Я каждый нз этих процессов определяется выбором начального слова, в качестве которого может быть взято любое слово Р в алфавите А. На первом шаге процесса, определяемого нормальным алгорифмом Я в алфавите А и словом Р в этом 'алфавите, берется само слово Р. Если на некотором шаге процесса было взято слово [;) и если Я: !') [- !х для некоторого 1?, то на следующем шаге берется слово )? и процесс продолжается. Если же Я: !г ) нлн Я: !') [- Я для некоторого Я, то процесс обрывается и в первом случае результатом его Я(Р) считается слово !',), а во втором — слово Е, Описанный процесс мы будем кратко называть процессом применения Я к Р*). Читатель без труда убедится, что справедливы следующие два высказывания: 4.1.
Процесс применения Я к Р обрывается тогда и только тогда, когда !Я(Р) )'4 25.71. 4.2. Если !Я(Р), то Я: Р~Я(Р) !э" 25.7.41. 5. В дальнейшем мы, как правило, будем пользоваться другим, нелинейным способом записи схем нормальных алгорифмов. Способ этот закрепился в литературе и имеет определенные методические преимущества. Состоит он в следующем. Формулы подстановок, составляющие схему нормального алго- э) Некоторые естественные обобщения определения нормзльнога элгорифмэ были рассмотрены в работе Н. М. Н з г о р н о г о [3!.
Одно из них зэключэется в том, что элгорифм определяетея нес«од»кили схемзми и нз кэждом шэге процесса применения вырабатывается чкэзэние того, какая из схем должна быть применена нэ следующем шаге. В другом обобщении таких схем „бесконечно много" — онн порождэются некоторым нормальным нлгорифмом. В третьем „бесконечны" (в указанном смысле слова) и сами схемы.'В этой же работе было покэээно, что эти „обобщения" определений не приводят к рэсшнрению соответствующих понятий: каждый нз „обобщенных" элгорифчов моделируется некоторым нормальным. рифма, выписываются „в столбик": сначала пишется первая формула подстановки (ядро первого элемента схемы [$ 24.7, Э 24Я), под ней — вторая и т.
д. вплоть до последней. Затем а в простых формулах подстановок и [1 в заключительных заменяются соответственно буквами -+ и-~- ° (при этом мы, конечно, должны условиться, что эти буквы не входят в алфавит алгорифма). Для большей отчетливости формулы, образующие схему, объединяются слева фигурной скобкой. В целяхединообразия скобку мы будем ставить даже тогда, когда формула подстановки будет всего одна. Так, схема уаЬаЬауасосауаруоау в алфавите аЬс, состоящая из четырех формул подстановок аЬОЬа, асеева, ар, аа, идущих в указанном порядке, при этом запишется в виде аЬ' Ьа ас — са а — ° а.
Мы хотели бы подчеркнуть, что такой способ записи схем нормальных алгорифмов не представляет собой самостоятельного их определения, а является лишь средством, делающим обращение с ними наглядным и удобным. Читатель должен помнить, что у-схемы в алфавите Аа[) суть слова в алфавите Аару [$ 25) н все высказывания о них должны пониматься как высказывания о словах определенного типа. 6.
Как мы увидим далее, понятие нормального алгорифма обладает большой степенью общности. Ввиду этого естественно возникает вопрос: в какой мере точное понятие нормального алгорифма соответствует более общему, но менее точному понятию вербального алгорифма в некотором алфавите [э 25)? Этот несколько неопределенно поставленный вопрос должен быть уточнен. Какого соответствия можно здесь ожидать? Конечно, алгорифмы вообще значительно разнообразнее нормальных алгорифмов. Естественно, однако, спросить, нельзя ли заменить всякий вербальный алгорифм в алфавите А нормальным алгорифмом, вполне эквивалентным ему относительно А [й 25.5). Мы полагаем, что на этот вопрос следует ответить утвердительно, и формулируем следующий п р и н ц и п нормализации алгорифмов: !гл.
142 НОРМАЛЬНЬ1Е АЛГОРНФМЫ Всякий вербальный а горифм в алфавите А вполне эквивалентен относительно А некоторому нормальному алгорифму над А. Условимся говорить о вербальном алгорифме в алфавите А, что он нормализуем, если он вполне эквивалентен относительно А некоторому нормальному алгорифму над А.
Принцип нормализации можно тогда формулировать следующим образом: Всякий вербальный алгорифм нормализуем. Формулированный сейчас принцип нормализации требует пояснений. Прежде всего, это не есть математическая теорема, подлежащая доказательству.
Такого характера принцип нормализации не имеет уже потому, что одно из понятий, о которых идет речь в этом принципе,— общее понятие вербального алгорифма— не является точным математическим понятием. Принцип именно н выражает уточнение этого понятия в понятии нормального алгорифма. Содержание принципа, однако, не ограничивается простым уточнением понятия вербального алгорифма. Принцип утверждает также пригодность этого уточнения. Хотя общее понятие алгорифма и не является достаточно четким, тем не менее это— сложившееся и употребляемое понятие.
Обычно не вызывает затруднений решение вопроса о том, считать ли алгорифмом такое-то конкретное предписание. Принцип утверждает, что всякий раз, когда такого рода вопрос будет решаться положительно — «да, это есть вербальный алгорифм в данном алфавите»,— будет возможно нормализовать предписание, т. е. заменить его эквивалентным относительно этого алфавита нормальным алгорифмом. Формулируя принцип нормализации, мы тем самым делаем большой ряд предсказаний о нормализуемости алгорифмов, построение которых осуществится в будущем.
В этом отношении принцип нормализации подобен физическому закону. Всякий физический закон тоже ведь является основанием для огромного ряда предсказаний о будущих явлениях. Например, закон сохранения энергии предсказывает сохранение общего количества энергии во всякой замкнутой физической системе. В отрицательной форме он утверждает невозможность изобретения регре1ццш шоЬ[[е — физической системы, неограниченно производя1цей работу без притока энергии извне. Аналогично этому принцип нормализации предсказывает нормализуемость всякого вербального злгорифма, который будет изобретен, и, значит, невозможность изобретения ненормализуемого вербального алгорифма. 4»»1 НОРМАЛЬНЫЕ АЛГОРНФМЫ 143 На чем же может быть основана уверенность в справедливости принципа нормализации алгорифмов, т. е.
в правильности тех предсказаний, которые делаются на его основании. В не- В малой степени на том же самом, на чем Основана наша уверенность в правильности известных нам физических законов,— на опыте. А опыт, подтверждающий принцип нормализации, огромен. Ведь математикой люди занимаются довольно долго — не менее 4000 лет. За это время было придумано немало различных алгорифмов. И среди них не известно ни одного ненормализуемого. Как-никак, а это веский довод в пользу принципа нормализации. Не менее веский, чем, скажем, опытное подтверждение закона сохранения энергии. другим важным доводом в пользу принципа нормализации является следующи й.
Известно много способов сочетания алгорифмов — построения новых алгорифмов по нескольким заданным. Все эти способы дают нормализуемые алгорифмы, если исходные алгорифмы были нормализуемы. В отношении важнейших способов сочетания этот факт будет установлен в дальнейших параграфах. Он показывает, что для построения ненормализуемого вербального алгорифма — если такое построение вопреки принципу нормализации все-таки возможно — необходимо привлечение каких-то совсем новых конструктивных средств таких, какие и не представляются современному математику.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
