lekcii3 (Лекции), страница 2

° а п+т т-~ №+т № № ° Ф„'"~ -. — --~- т где Т„, — МТ, записывающая значение да в ячейку, следующун> за рабочей: Т, = гдсг. Теорема доказана. Таким образом мы считаем, что в простейшем случае цикл состоит из повторяемого тела — - вычислимой функции -- и вычислимого предиката, управляющего повторением. В данном случае предикат предшествует повторению и является таким образом предусловием цикла. В частности. пикл, прсдусловие которого ложно, может не выполнитьгя ни разу.

И наоборот: если предикат находится в конце цикла, то он выполнится по крайней мере один раз. При этом в случае отказа в повторении цикла следует продолжение выполнения программы в естественном направлении - вперед, «далее по тексту». В языках Раэса1 и С циклы с пред- и постусловием выглядят так: яп11е (р () ) е() ' яп11е р с)о Я' с1о е() ' яЬ11е (р () ); гереаС К' ппС11 пот р; Заметим, что ппЫ означает «пока не», поэтому вместо предиката обычно записывается его отрицание, поскольку по-русски «отрицательность» слова ппЫ неочевидна. В отличие от цикла Мт11е, где истинность предиката означает продолжение выполнения, в цикле ппЫ истинность предиката завершает цикл.

В С оба цикла выполнены в одной логике, что более удобно как для понимания (т. к. не подразумевается неявное отрицание), так и лля перестановки места проверки условия цикла. Цикл с тождественно истинным предусловием ттЫ1е Сгпе с1о н, не зависящим от текущего состояния повторяемого тела, никогда не останавливается также, .как и тождественно ложное постусловие цикла гереаС н ппЫ Га1ве никогда не обратится в Сгпе и не позволит завершить выполнеггие цикла. Е) 2.6.6 Обобщенная теорема о цикле Теорема 2.6.5 может быть обобщена в нескольких направлениях.

Наиболее интересно обобщение, предложенное Эдсгером Дейкстрой ~1Ц, вытекающее из следующего примера: Пример 2.6.5. Алгоритм Евклида. Построим машину Тнод, реализуюшую алгоритм Евклида гля вычисления наиболыпего общего делителя двух чисел, используя машину Тэнв, рассматривающуюся в приъкре 2Л.4, и машины У< и Т>, .вычисляющие двуместныс предикаты )( И. р(иг) > р(иг) ) И, р(иг) < р(иг) '1 Л,Р(и,) < Р(иг) ' ' ), Л,,Р(пг)) Р(и,) соответственно.

Алгоритм Евклида состоит в вычитании меньшего из большего до тех пор, пока оба числа не станут равны. Можно доказать, что тогда каждое из этих чисел будет равно искомому наибольшему делителю. Машина Тнод, нормированно вычисляющая и = р ~(ПОД(р(иг), р(иг))), определяется диаграммой ~з тзпв и т с у кЗ 1з. а фт т и 2 4 50В л тнорм а, В состав машины Тнод входит цикл, определяемый двумя предикатами ) и <, Смысл использования такого цикла, становится ясным при сравнении диаграммы машины 7нод с диаграммой машины Тнод, которая тоже реализует алгоритм Евклида,.

ч г.кк т л л ~ зив т — г х з з, нод з ',л ноем Машина Г~ вычисляет прсдикат )( И, если ~р(иг) ф ~р(иг) 1 Л, если Р(иг) =;Р(иг) Машина Трюр д описана в примере 2.5.4. Следующая теорема является обоснованием применения циклов с несколькими телами и предикатами при конструировании МТ. Теорема 2.6.6.

(об обобщенном цикле, Э. Дейкстра) Пусть д,: (А,*,)" — ~ А*, (г 1,2,...,т) ВТ-функции, вычисляемые МТ То,, а р;: (А,*,)" — (И,Л) (1 = 1,2,...,пг) ВТ-предикаты, вычисляемые МТ Тр, (1 = 1,2,...,т) соответственно. Тогда функция, определяемая соотношениями: д = до, до, Е А,*, г' = 1, 2,..., т ~(и,,...,и„) = дг(ип...,пл.

пдыи, „...,и„),если рг(им....дп...,и ) = И, дг(ап..., и,, ~., дг, и,„.п.... и„), если рг(пм..., дг,..., и„) = И, д (и„..., аг и д„, и,:„, д,...., и„), если р,(им..., д„„..., и„) = И пока ~/ р = И, г=г тоже является ВТ-функцией, причем МТ, вычисляющая функцию, может быть эффективно построена из машин Т и '!р, (т, = 1, 2,..., т). С>Машина Тг, вычислЯюЩаЯ фУнкЦию 1"г опРелелЯетсЯ ДиагРаммой: г ° кл т кг;г к кл/ лм иг им гм и т 'т т ...т кг к 1.т ьг пн а ииг ~О' гл+л+1 гл+Л гл+л Р К ° 1 г ) п тм к т к к, клЬ..--- и+Г дг п«1 12 и .-г и,;г 'г ° кл т л+г Рг , л и.

' п и+г риг ', гт и Ю ',и г Лекция 12 2.7 Схемы машин Тьюринга 2.7.1 Конструирование машин Тьюринга «сверху вниз» В предыдущих разделах в качестве примеров и при доказательство теорем было рассмотрено достаточно большое количество конкретных МТ. Было показано, что если применять Машины Т „(г', = 1, 2,..., т) аналогичны машине Т„„рассмотренной при доказательстве теоремы 4.5.5. Теорема доказана. П За иечание. Данная теорема описывает цикл с тн альтернативными телами.

Также как и в случае ветвления, каждое тело охраняется своим предикатом. 11о в отличие от ветвления, цикл ориентирован на многократное повторение, причем в данном случае повторения могут идти по разным телам. Поэтому требования к набору предикатов снижаются. Отказ всех предикатов цикла в отличие от ветвления не приводит к аварийному завершению, а всего лишь прекращает выполнение цикла. («с1то русскому хорошо, то немпу смерть>.) Если напор прсдикатов цикла противоречив и при каком-либо повторении цикла соответствующими предикатами открыто для выполнения более одного тела, то выполняется любое из этих тел. То сеть в данном случае программируется педетерминированное выполнение, выводящее нас за, пределы алгоритма в традициош|ом понимании.

В простейшем случае прямого исполнения такого цикла на последовательном компьютере может быть выполнено первое в порядке написания тело. Таким образом пикл никогда не отказывает. При реализации цикла необходимо учитывать его двойственную природу: стремление продолжать выполнение цикла с запрограммированным завершением, т. е. предикаты р, должны зависеть от результатов вычисления функций дг, на предыдущих итерациях так, чтобы они постепенно закрывали тела цикла, приводя к его завершению. Ведь цикл работает «до последнего прсдиката»! для описания программ МТ технику диаграмм '1'ьюринга, то имеется принципиальная возможность испОЕ!ьзОвания ранее сконструи110ванньЕХ М 1 Н1еи 1еазрабо"1'ке е10вых тн1ягре1мм Тьюринга.

Это обстоятельство упрощает процесс конструирования новых МТ, но, .к сожалению, лишь несущественно, так как для использования МТ Т в диаграмме, описываннцей МТ 111, необходимо, чтобы функция ЕКЕ., вычисляемая маЕпиной Я, выражалась через функцию Ет, которую вычисляет мшпина 7", что справедливо далеко не для всех пар машин ЛЕ и Т. Нормирование Тьюринговых вычислений и теоремы о сочетаниях алгоритмов, доказанныс в п. 2.б', позволяют разработать и обосновать процедуру, которая обеспечивает систематическое и целенаправленное сведение задачи конструированная некоторой МТ к нескольким задачам конструирования более простых МТ.

Эта процедура называется конструированием «сверху вниз» и состоит в следующем. Пусть поставлена задача конструирования М'1' Т, вычисляющей функцию Е'. Выражаем функцию 7' через функции ~,,7'„,..., Д и составляем диаграмму машины 7, включаи1шую символы машин 7', вычисляющих функции 11 О = 1, 2,..., 11). Каждую из функций 1 выражаем через новые функции 1 „..., /; и составляеъл диаграммы машин Т, включающие символы машин ДЕ Т~,, в1.1числяющих функции 1, (в = 1, 2,...,1,; е = 1, 2,..., А;).

Продолжая процесс до тех пор, пока на каком-то уровне не получатся диаграммы, включающие только символы элементарных МТ; получим диаграмму мгипины Т, которую требовалось сконструировать. Следует отметить, что, выражая одни функЕНЕи через другие. можно использовать лишь т1' Операции (сочетания функций) котОрью были указае1ы В тс01)смйх О сос11'тяниях алгоритмов, т. с.

последовательную композицин1 функций, ветвление (альтернативное вычисление функций) и цикл еитерапию функций). То есть правила сочетания алгоритмов применяются в обратном направлении как правила декомпозиции. Процесс конструирования МТ «сверху вниз» поясним на следующем примере. Пример 2.7.1. Сконструируем машину Тьюринга Х, реализующую алгоритм Евклида для вычисления наибольшего общего делителя (НОД) двух натуральных чисел в десятичной позиционной системе счисления. ЧЕлсла, будем представлять на ленте МТ в виде непустых слов и и г над алфавитом В = 10, 1,2, 3,4,5,6, 7,8,9), интерпретируя слово и = п„п„1...

ас длины и ! 1 как число фи) = ,'е, '1е«1а;) 10*. 1=0 Действие машины Х описывается следующей парой конфигураций: Х [ЛИЛ11(Л) Л > =~* [ЛИЛп ЛЕН(Л) Л > где ев слово над алфавитом!е, представляющее число НОД(р(и), .р(п)). Алгоритм Евклида состоит в сравнении чисел и замене большего из них разностью между большим и меньшим до тех пор, пока, оба числа не станут равны между собой. Как только числа сравняются, алгоритм Евклида заканчивается, причем каждое из полученных равных чисел равно НОД. Алгоритм Евклида сводит сложную мультипликативную операцию к последовательности простых аддитивных, выполняя вместо деления необходимое число вычитаний. Следовательно, для составления диаграммы машины Х нам, во-первых, потребуется машина С, сравнивающая два натуральных числа: [ЛиЛг(Л)Л>==»* [ЛиЛЕЕЛд(Л)Л>, причем если у(п) = ~д(п), если ~р(и) < р(п), >, если г(и) > ~р(п), и, во-вторых, машина —, вычисляющая разность чисел р(н) и,р(п) при условии д(и) > Ф'): (ЛиЛа(Л)Л>»' (ЛиЛнЛш(Л)Л>, — слово, представляющее десятичную позиционную запись числа р(и~) где ш Е й*- р(и) — р(и).