Ш.И._Галиев_МЛ_и_ТА_2004
.pdfупростить. Такая часть выражения называется редексам, а операция упрощения называетсяредукцией.
Процесс редукции завершается, когда выражение, преобразо ванное редукцией, не содержит больше редекоа. выражение, не со держащее релексэ, называется нормальной формой.
Например, при оценке выражения (+(/62Хх25)) сначала выби раются редексы и упрощаются соответственно до 3 и 10, Полученное выражение (+3 10) также является редуцируемым, поэтому имеем
(+3 10)-»1J.
Резулыат (оценка выражении) 13 невозможно упростить, поэтому он считается нормальной формой.
Применение функции Применение функции/к аргументу х обозначается как !р) Функция err нескольких аргументов представля ется, например, следующим образом (f{x,y,z)). Однако функцию от не скольких аргунешов можно интерпретировать как результат синтеза функций от одного аргумента. Например (+3 4) можно интерпрети ровать как (+3)4, т.е. как прибавление тройки к аргументу 4.
Ламбда-абстрахурик - это олно выражение, определяющие функцию. Например, выражение
(Xx.-hrl)
определяет функцию прибавления единицы к переменно# м. Запись
Ах показывает, что это выражение является ламбда-абстракцией, формальным параметром которой является х Выражение, которое следует за точкой (в данном случае это -4(1), является телом ламбдаабстракции.
Рассмотрим следующее лаибда-выраженнс:
<М.+ху)1.
Здесь х считается связанной переменной, 3 - значением для*.
Для оценки этого выражения необходимо, чтобы переменила у уже имела какое-либо значение. Обычно значение свободной пере менной определяепся во внешнем выражении, содержащем это выра жение.
Пусть имеем оыражеиие (лх.+*1)4, и котором записаны после довательно ламбла-абстрашшя (Хдс.ч-х1) и аргумент 4, При замен* i на 4 получим ( 1-4 1). Это правит преобразования называется ^-преобразованием.
Примеры P-преобразований: (ix +^1)4-^-^4 1; (и+ж)5-^+5 5->10; (U3)5-*3;
{Ы>.уЫЦ2 6^-(Лу./у2)6->6 2—»3; 1->4,
где (лл.+ж1) - аргументдта предыдущейлаыбда-абсгракции.
И ТА Если выракение со;»ржит несколько редексов, го возможно
одновременное их оценншак, например, се® имеем (* (+3 5) (- 5 2)Х
в виде«ледуюшегографа (рис. 6.6). Посредством параллельной ре
скорость вычислении. При этой появ ляется возможность параллельной об работки и имеются следующие преи мущества по сравнению с процедурны миязыками.
()) Графовая структура ламбдаисчисления позвшют выявить релексыдля параллельной обрабочкя.
(2) Нет необходимости в централизованной управлении опера циями редукции, которые нужноделатьд о процедурных тыков.
(3)Сп«5Ь иежду редексамк можно выпог.ннть полностью уни фицировано.
В Процедурных языках вдачи распараллеливания вычислений требуют специальных программ, в том числе и синхронизацию
262
(по зремени) этих вычислений. В языках с лаыбда-исчислением этого не нужно. Сама структура программы однозначно определяет опти мально? число параллельных вгтаей вычислений.
§ 18. Основные результаты
1. Из теорем 6.5 и 6.6, следствий ш них, а также теорем 6 1
и 6.12 следует, что клвсс частично рекурсииных функций совпадает
с классом функций частично вычислимых по Маркову и классом час тично вычислимых по Тьюрингу функций. Бол«е общее: с помощью детальных рассмотрений показано, что формализации, предложенные Тьюрингом, Марковым (нормальные алгоритмы), а также Кпинн (частично рекурсивные функции) и другими, эквивалентны, т.е. в каждом случае получается один итот же класс функций.
Всюду определенные функции, попадающие о этот класс, являются общсрекурстыыми функциями. Часткчныг функции тгого
исконной гипотезе теории алгоритмов (принцип нормализации) любой алгоритм вполне зонвалентен нермальнпму алгоритму. Тогда сово купность частично рекурсивных функций совпадает с совокупностью частичных функиий; вычислимых посредством нормальниго алго-
263
2. Изучалось обширное мноиеспю конкретных функций, интуи тивно алгоритмически* Все они оказались частично рекурсивными функциями, т о. были найдены наборы инструкций для них с какойнибуць стандартов формализации (нормальные алгоритмы или Тькзринговская схема).
3, Доказательство указанию результатов обладает слелующей общей структурой. В каждом случае тот факт, что один формалиаооанный класс функций содержится в другом, доказываете! предъявле нием и обоснованием однообразной процедуры, согласно которой для любого набора инструкцийJ одной формализацииуказывается набор инструкции J' другой формализации, приводящей к гой же функции. Эта единообразная процедура оказывается а каждом случае алго-
Еслидействоватьнебуояаь, ник чемуумапалата.
§19. Вопросы и темы для самопровсрки
1.Интуитивное понгтмеалгоритма, его свойства.
2.Алфаиит, сЛола, алгоритм в алфавите. Вполнеэквивалентные в данном алфавите алгоритмы.
3.Нормальный алгоритм (алгоритм А. А. Маркова), задание,
примеры.
4.Функциивычислимыеи частично-вычислимыепоМаркову.
5.Замыначие, распространение нормальногоалгоритма.
6. Операции над поряальными алгоритмами: композиция, со единение, разветвление, поиторение.
7.Машина Тьюринга, общееописание.
3.Задание машиныТьюринга, примеры.
5.Алгоритм Тьюринга. Вычислимостьпо Тьюрингу.
10Связь, между алгоритмами Тьюринга и нормальными алгоритмами.
11Основная гипотеда теории алгорвтхов (принцип нормализа ции или тезис Ч5рча). Доказуема ли эта гипотеза';
12.проблема amоритмической неразрешимости.
13.Знаете ли вы алгоритмически разрешимые массовые про
блемы1?
14.Примеры алгоритмически неразрешимых массовых проблем.
15.Сведения любого преобразования слов в алфавите к вычис лению значений целочисленные функций.
16.Примитивно-рекурсивные и обшерекуренвкые функции.
17.Причитивло-рекурсивность некоторых функций. Вычисле
ние значений примтиши-рекурсивных функций.
18.Частично рекурсивные функции, нх связь с пычислимоггып по Маркину иТьюрингу.
19.Какие вы знаете вычислительные модели?
20.Ламбда-исчисленке Синтаксис ламбда-исчисЛснМ.
21. p-npcofipaaoваних в ламбяа-исчислении.
§20. Упражнение
I.Применим ли нормальный алгоритм
;слову: а) Я=111; б) Р=*»; в)/*-11»; г)Р=*!*1 )Иуиьтат применения.
2. Применим ли нормальный алгоритм
к слову: а) Р- \ 1111; б)?=*111*1; в) Р='*\ г) P=U1*I. Если «да», то указатьpfiynbTa^применения.
' 3. ПустьР-ЬаЬЬЬс олово в алфав»геЛ={д,6,с]-,. нормальный плгоритм
В={ab->a.
Вкакое слою перерабатываетланный алгоритмсловоF'
4.Пусть задан алфавит^ —{i,с) н нормальный алгоритм о алфа вит А:
Применим ли алгоршм В клюбому слову и шфавте At Сели он пршенич к некоторому слову Р, тп в какое слово он его перерабаты-
5. ПустьЛ={я,6,с} иЙ “ <
Как действует данный алгоритм? Применим ли он к любому слову
валфавитеА1
6.Построить нормальный алгоритм, стирающий последнюю б кву каждого непустого слова Р в алфавите А. Яачяется яи построен ный алгоритмалгоритмомв алфавите А илинад алфавитомА'1
7Пусть А - русский алфавит. Построить нормальный алгоритм над алфавитомА, который преобразует' слова «муха» в слови «слон»,
алюбое другое слова в алфавиге А в лустов слово. При этом, если слово «муха» входит в некоторое слово Q, например <2=Черемуха, то слово Qалгоритмдолженпереработать впустоеслово.
8.Пусть А - русский алфавит. Построить нормальный алгорит над алфавитом А, который преобразует слово «слон» &слово «муха»,
алюбое другое слово в алфавете А в пустое слово. При этом, если слово «слон» входит в некоторое слово Q, например £ заслон, w
слово Qалгоритмдолжен переработатьв яуеше слово.
9. Пусть 'чаданы «лфавш А и некоторое непустое слово Q в эт едфавитг. Описатьдействие нормальных алгоритмов, задаваемых ь
дающими схемами: |
|
а) {Л-*‘Л |
б) { Л -я а |
« ( " а |
«{П а |
Д) {л -* И. |
в) [А -» •£ |
*) в - ^ а в - М б ^ ) |
з ) { х ^ ‘Л{х*А) |
[/I -» а |
|
и) \х-*а{хеА ,аеЛ )
10. Показать, что алгоритм, заданный схемой; |'са-4р
Ipa-»p(a,p«i4,a,ysi) |(5-»М
I аху -> уах
преобразует любое слово я алфавите А ц слово, образованное id же букв, но в обратном порядке.
11.Пусть А - некоторый алфавит, аеА; В,С,D - заданные сл
валфавите/!. Рассмотреть нормальный алгоритм надалфавитом ,4
Покашъ, чти э-гаг алгоряти F неимении клюбому слову а алфавите
А, причем P{P)=D,F{B)=C.
12.ПустьА={й,Ь,с) Построить нормальный алгоритм, коюрый клюбому слову с алфавитеА будет приписыватьсправаслово abb.
|
13. Пусть ЛЧ1} и |
Д1ш всякого натуральною числа п |
|
определим по индукции 0 = 1 |
и м+1 = и1. Таким образом, 1-11, |
||
2 =111 и т.д. Слова к назыиаются цифрами. Поставим теперь в соот |
|||
ветствие всякому вектору («1, |
т е |
- натуральные числа, |
|
слово |
, которое обозначим через |
(я,, .,ntj . Например, |
|
(3,1,2) обозначает слово Ш 1*11*1! 1: |
|
||
|
а) Показать, что схеме |
|
|
|
all -» а5 |
|
|
|
<х1 —*»1 |
|
|
определяет нормальный алгоритм F над алфавитах! В, применимый только к тем словам в алфавите Я, которые являются цифрами, и та кой, что f(r)= 0 для любогои.
б) Показать, что нормальным алгоритм Q над алфавитом Я, оп ределяемый схемой
применим только к тем словам в алфавите В, которые суть цифры, причем С>(и)=я+1 для любогоп.
в) Построить схему нормального алгоритма в алфавите В, пере рабатывающего (и,,и,) в
г) Построить нормальныйалгоритм умножения ни2.
14. Построить нормальный алгоритм над алфавитом 23“ (1,»| д арифметическихопераций сложения н вычитания.
26S
15.Построить нормальный алгоритм дя* умножения па фикси-
16.Пусть /(“ {1 ,*а Ь} Показать, что следующий нормальный
алгороты
£>l-»li |
*?->• |
el -»Ш |
*-»Л |
о-»Л |
Й-.1 |
производит умножение дву*. чисел п и м , записанных в алфавите
17.Построить нормальный алгоритм F над алфавитом А такой, чтодля любого слово Рв А было Л,Р)=РР.
18.Построить нормальный алгоритм для получения целой Части при делении а) на3; 6) на п.
19.Построить емму нормального алгоритма, равного компози ции нормальных алгоритмов Fи Оиалфавите
Затем применить полученный алгоритм к слову, а) |
Р=111)Ш; |
|
б) Р=*1Ш; в) Р“1*121; г) /’“**. Результат проверить, последователь |
||
но применяя к заданному слову алгоритмF, SSTCM G. |
|
|
20. |
Пусть имеем нормальный алгоритм F над алфавитом А, схе |
|
ма которого записана с использованием буи из А и произвольного |
||
конечного числа буки, не принадлежащих А. Обозначим эти буквы, |
||
не принадлежащие А, через S | , S i т.е. B=Auj SiSj |
.%,}• Тогда |
|
алгоритм F над алфавитом А можни считать задаиным в алфавиге В. I Юказать, что для рассматриваемого алгорюта F существует вполне эквивалентный ему в алфавмеА нормальный airopmw, сигма когоро-
269
го поетрэена только с использованием бука ti^aema С-ЛЫа,[) j (а,(3«В). Можно ли исключить однуиз букв а или 0, если п>[?
21. Дли каждого из приведенныхдалее алгоритмов над алфави том А~[аМ} каИти вполне эквивалентный ему нормальный алгоритм, схема которого записана только с использованиембуки а, Ь, а,р:
а Ь->Ьа
;Oi> --»В
Y-*ЬЬ
[Л->а
22. П ут. А - некоторый алфавит. Составьте нормальный алго ритм над А, позволяющий дм произвольных шов Р и Q в алфавите А пыяенять, одинаковыэти слова или нет. (Указание; рассмотрите слово Р*2(где чА> и постройте алгоритм, сравнивающий и словах У и Q буквы, стоящие первым слева и справа от *, затеи вторыми от * И-Т.Д.)
23.Пусть Л-{0,1,2,...,9). Составы? нормальный алгоритм над А, который любое число и, записанное в десгшчной системе счисле ния преобразует в п+1.
24.Будем рассматривать нормальные олгоришы в алфавете Л. До сих пор мы применяли для их задания «схемы» - столбцы формул подстановок. Однако можно задавать каждый нормальный алгоритм
ввиде одного слова, когороа поручается следующий образом. Пусть
Выпишем друг за другом в поряде очередности формулы подстановок алгоритмаF заменой стрелкимаком сц точки-знаком р и нрисоодинением после каждой подстановкизнака у. Получаемое так слово будем называть изображением алгоритмаР я обозначать симво лом Г . Алгоритм F называете# самолрименимым, если ои применим
ксвоей собственной записи, т.е. к слов) F\ и несамолрименимым »обратномслучае.