lekcii3 (522347)
Текст из файла
Х$ап1ина К„описывается диаграммой Х П н К а 1м ----н1 - г ~" и а Я а+1 и+1 К 31 31*- ~с+1 Р Р к и Докажем, что машина Т, определяемая диаграммой т = .т„к.:..т,„... к,",,т,,„к, „.„„к, „„„... ки„,„,„т„ вычисляет функцнк> 1, т.е. реализует действие 3' (Ли1Ли2... Ли„(Л)Л >==~* (Л~Л~(ин ии,..., и„)(Л)Л >, где в Е .4* (А, .-- рабочий алфавит машин Т (г = 1,2,...,гп) Ть, к„1.1, к< 1 (д 1, 2,..., пг), Т; А, С А„, А, С Ар, А, С Аг) Имеем: ти (Ли1Ли2... Ли„(Л)Л >=~* (Ли1Ли~... Ли„Лд1(Л)Л >=~* тд~ ~Ли1Ли2... Ли Лд1Ли,ЛиеЛ...
Ли„(Л)Л >==~* т„„ ~Ли1Лие... Ли„Лд1 Ли1Лие... Ли„Лде(Л) Л >==~* 2.6,2 Теорема о ветвлении Теорема 2.6.2. (О ветвлении) Пусть и-местная функция ~': (А,*)" — ~ А,* определяется равенством: д1(и„и2,....,и„),если р1(и„ив,..., и„) = И де(им и2,..., и„),если р4(ипи2,...., и„) = И ,1 (и1, и2,..., и„) = д (и1, и2,..., 16,), если р„,(и1, .иг,..., и,) = И 80 (Ли,Лис... Ли Лд1Ли,Ли~... Ли„,Лд2... Ли,Ли~... Ли„Лд (Л)Л > (Ли1 Ли2... Ли„Лд, Ли1...
Ли,Лд~... Ли, Лис... Ли„Лд„,Лд1 (Л) Л > ==~* к„. = (Ли1Ли2... Ли„Лд1Ли1Ли2... Ли„,Лд2... Ли1Ли2... 7'~, Ли„Лд Лд,Лд2...Лд (Л)Л >==~' (Ли,Ли2...Ли„Лд1Ли1Ли2...Ли„Лд2... Ли1Ли2... Ли„Лд Лд1Лде... Лд,Л6(днд2,...,.д )(Л)Л >= (ЛвЛУ(ич, ие,..., и,„)(Л)Л > так как по условию 6(д1(и1, и~,... и ), д2(ими2,... и„),..., д (и~, .ие,... и„)) = ~(и1, ие,..., и„).
Теорема доказана. П где д,: (Л,")" — » Л,* (1= 1,2,..., пг) ВТ'-функции, ар;,: (Л*,.)" — » 1И,Л) (1 = 1,2,....,т) ВТ-предикаты. '1огда 1" является ВТ-функцией, причем МТ, вычисляющая функцию 1' может быть эффективно построг иа из М'1', вычисляющих у, и предикаты р; (г = 1. 2,..., Рп), 1>Пусть Тд и Т„(г = 1,2,...,гп) МТ, реализующие нормированное вычисление функций д; и предикатов р, (1, = 1.2,..., гп) соответственно (возможность эффективного построения таких МТ лля лк1бых ВТ-функций следует из теоремы 2.4.3).
Машина Т, вычислятощая функцию 1, определяется диаграммой: п , — --- -~ г ° К ° и+1 1 т.-' ° т ° ~ — 4л и Р г ° и ° .л и Р«1 Рг ~. и+1 яВ г К ° т. и+1 '3Р ',л К". т. ~ ~' л В случае, когда все р; (1, '= 1, 2,..., Рп) имеют значение Л, функция 1' не определена; поэтому в этом случае предусмотрено, чтобы машина Т никогда пе останавливалась. Проверка того, что машина Т действителыю вычисляет функцшо /, производится аналогично соответствующей проверке, проведенной при доказательстве теоремы 2.5.1.
Теорема доказана. П Зальечание. Данная теорема описывает 1п;звенное ветвление. Каждая ветвь охраняется своим предикатом. Предполагаг тся., что набор предикатов ветвления р, (1 = 1, 2,..., гп) «полон» и «непротиворечив»: при ветвлении один и только один предикат принимает значение «истина».
Считается, что набор прсдикатов полон так, .чтобы ветвление никогда ие откизыеалц В реальности программист может просто запланировать резервную ветку, охраняемую предикатом р,1 — — - ~/ рь чтобы дополнить систему предикатов. Непротив=1 воречивость же так просто не достигается. Поэтому в простейших последовательных моделях исполнения предикаты проверяются в процессе написания и ветвление выполняется по перьой же открывшейся ветке.
Сказанное означает, что к выбору набора прсдикатов для многозвешюго ветвления надо подходить очень и очень основательно. Возможна организация ветвлений па противоречивых наборах предикатов, по опа носит педетерминированный и, следовательно, неалгоритмический (в классическом гюнимании этого слова) характер. В этом случае ветвление идет по одной из открывшихся ветвей, выбираемых недетсрминированным и неалгоритмическим образом. Подчеркнем, .что даже случайный выбор ветки выполняется по некоторому вероятностному закону и, .следовательно, .детерминирован и алгоритмичен.
2.6.3 Следствие из теоремы о ветвлении Следсшвие. Пусть п-местная функция 1'; (А*,)'* — А; определяется равенством: 1г у(им и2,..., и,), если р(и~, .из,..., и„,) = И ) и(им из,,иа),ес11и р(и1.,и2,...,1ь1) =-1 где д: (Л",)"' — ~ Л,* и 6: (Л',.)" — ~ Л; ВТ-функции, а р: (Л*„)" — ~ (И,Л) ВТ- предикат, '1'огда /' является ВТ-функцией, причем М'Г, вычисляющая функцию 1", может быть эффективно построена из МТ, вычисляющих функции д и 6 и иредикат р. Г>11усть Тд, Хь, Тр МТ, реализующие нормированное вычисление функций у и 6 и предиката р соответственно.
Из теоремы 2.5.2 еле чус т, что мшпина ТГ, опредсляемая диаграм- мой и и — ю ° Г ° К е т и+1 д т . ° т ° ! Р и » Г ° к ° т и+1 и '1 1р1) > аО; е1ве ьО; 1Х р треп К е1ве Ь; 2.6.4 Пример итеративного алгоритма Многие алгоритмы сводятся к повторному выполнению более простых алгоритмов до тех пор, пока не будет выполняться некоторое условие. Один из таких алгоритмов рассмотрен в примере 2.5.2. Рассмотрим еще несколько примеров таких алгоритмов.
Пример 2.6.3. Алгоритм возведения целого положительного числа в степень. Пусть Тмгьт -- МТ, реализующая нормированное вычисление функции М1Л.Т(и,,и2) = и1и2, а Т, МТ;, реализующая нормированное вычисление предиката Тогда машина Трои , .нормированно вычисляющая функцию и' = РОЧ'(ин иэ) = п,1", может быть построена из МТ 1гипьт и 7" следующим образом: полагаем Га = 1 и с помощью МТ Хуны выполняем умножение п~ на я(2, одновременно уменьшая и2 на 1 (для этого нам понадобится МТ Тэпв, нормированно вычисляющая функцию ЯЗВ(пн и2) = и1 — и2), до тех пор, пока, из ф О.
Диаграмма машины Трои имеет вид: вычисляет функция> ) . Отметим, что это следствие более чем частный случай теоремы. Во-первых, для управления двумя ветвями используется только один предикат. Во-вторых, поскольку один щтедикат автомати вески является полным и неиротиворе 1ивым набх>1х)м, такое ветвлс— ние никогда нс отказывает. В-третьих, психологи говорят, что ветвление более чем в два места является дополнительным источником ошибок.
Это было замечено сгце в конце 60-х годов, когда Эдсгер Дейкстра предложил идею структурированного программирования с использованием ограниченного набора конструкций, среди которых было только двузвенное ветвление. Это следствие охватывает наиболее распространенные конструкции языков программирования Раэса1 и С: г ° кт к6 ° 7 муьт к5 кт т аив ° ~ ° ка. ~ ° .к.к~. ( .м. й . к~ с т,. ~ (' л Поясним работу машины 7роч~. Последовательность МТ Т» = МЙ7мпьтТ~А~Тзнв выполняет следующие действия: К7К6 [ЛсЛи»Лп»('~Ли(е»Ли( ~Л[п~(»(Л)Л >==~* [ЛвЛи»Ли(нЛп(~~Л»л~' Л[Ли2 (~Ли»Лп»(~~[А)Л > [ЛлЛи,Лп»(»1Лш(»»Ли~' Л[Ли( Ли»Лп~(~~[А)Л >=~* [А Ли,Лп»(»Лп~(»~Ли Л[Лп, ЛпнЛп»(»~ид.п»(2»[Л)Л > «;к-, [ЛхЛпн Лп»('» Ли(2»Ли2'~»Л[Ли2( ~»Ли» Лп»('»»» и»('~ [Л)Л >=~* [Л-Ли»ЛпЯЛп»(»~Ли2ЦЛ[Ли~ ~~Ли»Лп»(~~палР»Ли~~ ~Л[(Л)Л >=~* [Л-.Ли»Ли~цЛп»(~~Ли2 ~Л[ЛУРЛи»Л»»»(~1»»ал»»(~~Ли2 ~А[Ли~ » — 1(Л)Л > Таким образом, действие машины Т; состоит в [ЛсЛи»Лп»(»»Ли(2»Ли2(ЦЛ[Ли2(»(Л)Л > т, =Ф [ЛйЛ»»нЛ»»» ~Л»й Л»»2 Л[»»2 (Л)Л > где = = вЛи»Лп (»»Лп»(2»Ли~~ ~ А[Ли~~ », »и(»» = и (2», М2» = и».п»(е», и2(» = »»~~ ~, .и~ » = и( ~ — 1 Последовательность МТ ТО» 1~ Зг [ 1~ 1~ 51' »г ~ 1(2 выполняет действие [Ли»Лп2[Л)Л >=~' [Ли»Ли2+и»Л[Л[Ли2Л[Ли2ЯЛ > преобразуя исходную ситуацию машины Тров [Ли»Ли2(Л)Л > в исходную ситуацию машн- ны Тд [А~Ли,ЛпР~Льи(т»Лп~~ »А[Ли( ~1Л)Л > гдел=и,Лиф,и»' =и» =1,.и2 =и =из.
(Ц (2» (»» (2» Наконец, последовательность МТ 3 3 НОРМ г ~ № -----Ф» л. ° т' т ° ~ ° -- ° г ° т роту- О + ', лл 2 Из последней диаграммы видно, что если исключить подготовительные и заключитель- ные действия, выполняемые машинами То и Тл соответственно, то работа машины Тготтл состоит в повторном применении машины Лт до тех пор, пока предикат, вычисляемый машиной Т, имеет значение И. 2.6.5 Теорема о цикле В примере 2.6А был рассмотрен алгоритм, состоящий в повторном вычислении двумест- ных функций МП1 Т и Я, В, причем в качестве второго аргумента функции МПЕТ бралось значение этой функции, полученное при предыдущем ее вычислении, а в качестве первого аргумента функции ВПВ бралось ее предыдущее значение. Количество повторений опре- делялось предикатом — '.
Такой алгоритм мы будем называть циклом. Применение циклов при конструировании машин Тьюринга обосновывается следую- щей теоремой. Теорема 2.6.4. Пусть д: (А„*)" — А',, ВТ-функция, вычисляемая машиной Т~, а р: (А,*)" — (И, Л) - ВТспредикат, вычис:тяемый машиной Тр.
Тогда функция 1; (А*,)" — А„*, оттределяемая вычислительным ттроцессом д = дть до е- А,*. )' (тлт, и2,..., и„) = д(и,, и2,..., и т, д, и л.т,..., и„), пока р(ит, гл2,..., д,..., и„) =И, тоже является ВТ-функцией, причем МТ, вычисляющая функцию т', может быть эффек- тивно построена из машин Т и С,. 0 Машина Тл, вычисляющая функцию т', определяется диаграммой выполняет следующие действия: (Л=Лит ЛтлттттЛтлт'Ли~ОЛ1ЛО(Л)Л >==~* (Л Лит ллттттЛтлт'ттЛтл~~ ~Л1ЛОЛ(Л)Л >==т.* ~ЛлЛитЛтллтОЛитт(Л)Л > ттт м (ЛитЛиДгвЛитЛивОЛйт'(Л)Л > =~* (ЛитЛиоЛйт'(Л)Л > обеспечивая нормированное вычисление функции ВОЛлтт. Обозначения То, Тт, То позволяктт записать диаграмму машины Гроту в виде И и . " „+ 1-'г т т ° т ° к к к тт №№ в+№ 1-1 и+№ л ° г ° (.
Характеристики
Тип файла DJVU
Этот формат был создан для хранения отсканированных страниц книг в большом количестве. DJVU отлично справился с поставленной задачей, но увеличение места на всех устройствах позволили использовать вместо этого формата всё тот же PDF, хоть PDF занимает заметно больше места.
Даже здесь на студизбе мы конвертируем все файлы DJVU в PDF, чтобы Вам не пришлось думать о том, какой программой открыть ту или иную книгу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
