markov_teorija_algorifmov (522344), страница 26
Текст из файла (страница 26)
Действительно, пусть Р— произвольное слово в А и пус уаЯу ( ). Тогда для некоторого )т' уаЯу: Р=4»Г«, т. е. усть ухну: Р)=)«] или уаЯу: Р)=*)г. В первом случае уаО: 1=Р уаЯу: Й ], что невозможно, так как схема уаЯу Р и * у: действует на любое слово К в А [11.2]. Во втором случае существует слово 5 такое, что уа!1у: Р 1=5 1-.Й. Но уаЯу: 5~- !т невозможно, так как схема уаЯу не содер- жит заключительных формул подстановок.
Итак, предполо- жение, что !уа!еу(Р), ведет к противоречию, что н требо- валось доказать. 3 а м е ч а н и е. Это утверждение доказано нами методом «приведения к нелепости» и, стало быть, фигурирующее в нем отрицание мы должны понимать как редук14ионное (см. 3 13.4).
Однако мы могли бы понимать его и как усиленное (см. $ 12.Ц. Мы предлагаем читателю самому привести доказательство, которое соответствовало бы такому подходу к пониманию формулировки нашей теоремы. НОРМАЛЪНЫЕ АЛГОРИФМЫ: ОПРЕДЕЛЕНИЕ И ПРИМЕРЫ ф 26. Алгорифмы 1. Существенную роль в дальнейшем играют алгорифмы. Понятию алгорифма может быть дано следующее предварительное определение, которое в дальнейшем будет уточнено: 1Ф Алгорифм есть предписание, однозначно определяющее ход некоторых конструктивных процессов. 2.
Слово «предписание» в определении алгорифма указывает на наличие некоторого адресата — субъекта, о котором предполагается, что он будет выполнять это предписание. В частности, это может быть человек нли какая-нибудь его хорошая модель. Выполняя предписание, его адресат будет осуществлять некоторый процесс, однозначно определенный этим предписанием. Этот процесс будет идти в некоторой системе (например, в системе: «доска, мел, тряпка»), состояние которой будет в ходе процесса изменяться. Все эти изменения должны полностью определяться предписанием и осуществляться адресатом-исполнителем, который, разумеется, должен понимать предписание. Иногда предписание может потребовать окончания процесса.
3. В нашем определении алгорифма о процессах говорится во множественном числе. Алгорифм может, вообще говоря, определять много процессов, отличающихся друг от друга начальным состоянием системы. (В частном случае, однако, алгорифм может фиксировать начальное состояние, и тогда мы будем иметь только один процесс.) 4. Слово «однозначно» в определении алгорифма не должно пониматься слишком буквально. Для состояний системы может быть установлено то или иное отношение одинаковости. Например, для системы «доска, мел, тряпка» состояниями могут считаться слова, написанные мелом на доске. В этом случае будет естественно считать состояния одинаковыми, если одинаковы соответствующие слова. Процесс, определяемый алгорифмом при задании начального состояния системы, должен определяться однозначно лишь „с точностью до одинаковости" получаемых в его ходе со- НОРМАЛЬНЫЕ АЛГОРИФМЫ 1гл, гп стояний.
Потребовать, чтобы этот процесс был единственным, мы можем, лишь условившись естественным образом применять абстракцию отождествления [см. 2 5! к состояниям нашей системы и процессам, протекающим в ней. 5. А(ля формулировки и понимания алгорифма необходим тот или иной язык — язык данного алгорифма. Естественно потребовать, чтобы на этом языке можно было назвать любое состояние системы, с которой имеет дело алгорифм.
Состояние должно при этом однозначно определяться своим названием. Не будет существенным ограничением Общности, если мы условимся считать язык алгорифма письменным и линейным. Это означает, что язык имеет алфавит, состоящий из элементарных знаков — букв, причем выражения данного языка (высказывания, названия, предписания и т.
п.) являются «словами», т. е. линейными рядами букв. Процесс осуществления алгорифма может быть тогда промоделирован некоторым другим процессом, имеющим дело со словами — с названиями состояний. Таким образом мы сводим рассмотрение алгорифмов к рассмотрению вербальных алгорифмов. Так мы будем называть алгорифмы, работающие над словами в каком-нибудь данном алфавите.
Процесс работы вербального алгорифма в алфавите А состоит в последовательном порождении слов в алфавите А согласно сформулированному предписанию. Перед началом этого процесса выбирается некоторое исходное слово в алфавите А. Процесс может закончиться порождением некоторого слова, которое мы объявляем тогда результатом работы нашего алгорифма над исходным словом.
Мы будем также говорить, что наш алгорифм перерабатывает исходное слово в результат своей работы над ним. Мы будем говорить, что алгорифм применим к данному слову, если процесс его работы над этим словом заканчивается, т. е. если имеется результат его работы над данным словом как исходным. В дальнейшем (1) 1Й (Р) будет означать, что алгорифм й применим к слову Р; (2) й: Р»Сг будет означать, что алгорифм й перерабатывает слово Р в слово Я. Очевиден следующий закон единственности результата работы алгорифма: $261 АЛГОРИФМЫ 1зт 5.1. если Й: Р-.=>1,2, то если й: Р=-»1е, то Я х)е. 5.2.
1Й(Р) тогда и только тогда, когда существует 1г такое, что Й: Р=>Я. По определению алгорифм й в алфавите А при задании исходного слова Р в алфавите А последовательно порождает слова в алфавите А. При определении предикатов !й (Р) и й: РОД мы молчаливо предполагали, что Р— слово в алфавите А. В наших дальнейших рассмотрениях будут встречаться другие алфавиты и слова в них. Условимся в таких случаях считать алгорифм Й в алфавите А неприменимым к слову Р, если Р не есть слово в алфавите А, т. е.
если в Р входит буква, не входящая в А. Таким образом, мы в этом случае будем считать высказывание !Й (Р) ложным. Высказывание Й: Р~1г мы также будем считать тогда ложным, каково бы ни было 1,'!. 6. Рассматривая какой-либо алгорифм Й в алфавите А, мы часто будем интересоваться только результатами его работы над словами в более узком алфавите Б, составляющем часть алфавита А.
Мы будем говорить, что вербальный алгорифм й в алфавите А есть алгорифм над алфавитом Б, если А есть расширение Б, т.е. если всякая буква алфавита Б является также и буквой алфавита А. Пусть Б — алфавит, а В и 6 — вербальные алгорифмы над алфавитом Б. Мы будем говорить, что В и 6 эквивалентны относительно Б, если для любых слов Р и Я в алфавите Б имеют место импликации: а) если В: Р=„'>Я, то 6: Р=!> 9, и б) если 6: Р ~ Я, то В: Р =о Я. Будем говорить, что В и 6 сильно эквивалентны относительно Б, если они эквивалентны относительно Б, а, кроме того„ для любого слова Р в алфавите Б имеют место импликации в) если 1В(Р), то 16(Р), и г) если !6(Р), то !В(Р). Будем говорить, что В и 6 вполне эквивалентны относшпельно Б, если они сильно эквивалентны относительно Б, а, кроме того, для любого слова Р в алфавите Б соблю- даются следующие условия: 138 НОРМАЛЬНЫЕ АЛГОРИФМЫ 1гл.
Рн д) каково бы ни было слово Я в алфавите алгорифма В„ имеет место импликация Е: Р=оя, й: =оа, и е) каково бы ни было слово 1г в алфавнте алгорифма 6, имеет место импликация й: Р Е, ° й): ° Е. Из определений видно, что сформулированные нами от- ношения эквивалентности перечислены в порядке их после- довательного усиления. й 27. Нормальные азгорифмы. Принцип нормализации 1. Введенное только что понятие алгорифма в данном алфавите не является достаточно четким, чтобы дать возможность рассматривать алгорифмы как объекты математической теории. Оно для этого подлежит уточнению, к которому мы сейчас и перейдем.
Прежде всего, «общепоиятность» предписания нельзя рассматривать как вполне четкую характеристику. Постепенный переход от понятного предписания к совсем непонятному путем все большего и большего усложнения, очевидно, вполне возможен. Естественна поэтому мысль о той или иной регламентации предписания путем его расчленения на правила определенного стандартного типа, общепонятность которых не вызывала бы никаких сомнений. Процесс применения алгорифма будет тогда состоять из отдельных элементарных шагов, каждый из которых будет выполняться согласно одному из этих правил. Естественно добиваться возможно большей простоты этих шагов и правил. Процессы, ход которых определяется предписанием, разнообразны. Выяснилось, однако, что если интересоваться алгорифмами лишь с точностью до эквивалентности, то их плохо обозримое разнообразие, по-видимому, сводится к более простой идее.
2. Мы введем в рассмотрение вербальные алгорифмы специального типа — так называемые нормальные алгорифл«ы. Всякий нормальный алгорифм й будет задаваться указанием следующих трех объектов: некоторого алфавита А, некоторого трехбуквенного алфавита с«ру, не имеющего букв, общих с алфавитом А, и некоторой у-схемы Я в ал- З зт1 НОРМАЛЬНЫЕ АЛГОРИФМЫ шз фавите Ааи [9 251. Алфавит А мы будем называть алфагил«ом нормального алгорифма й. Схему Л мы будем называть схемой этого алгорифла. Разумеется, введя какую-нибудь новую букву 6, играющую роль разделительного знака, мы могли бы записать эту тройку в виде 6-системы 6Аба(17Ы6, так что в конечном счете всякий нормальный алгорифм определяется указанием одного-единственного слова.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
