lekcii3 (Лекции)

Х$ап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 и+№ л ° г ° (.