1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 19
Текст из файла (страница 19)
Таким образом, программа останавливается тогда и только тогда, когда протокол ее выполнения конечен. В противном слу- чае программа зацилливаелдсл и реаультат ее выполнении не опре- делен. Заметим, что наше определение программы включает задание началъпых данных (начальное состояние памати). Понятна ин- терпретации впогда вводят таким образом, что интерпретируются только функциональные и преднкатаые символы, а начальные значения переменных задаются отдельно.
В этом случае програм- ма описывает алгоритм и определяет частичную функцию из Ю" в Ю», где Ю вЂ” область ввтерпрвтацви, и — количество перемен- ных в схеме (иакнм-либо образом упорядоченных), а Ю» — мно- жество последователъностей элементов нз Ю. Такой вариант определенна программы болыпе соответствует общепринатому раз- делениюнасобствеинопрограммуи исходные данные. Однако для неученая семантических свойств схем программ отделение исход- аых данных от программы несущественно, так как основным объ- ектом исследования остается схема, а поннтпе программы необ- ходимо как промежуточний объект для определения понятий, о которых пойдет речь в следующем параграфе.
В то же время принятое нами определение программы позволяет упростить тех- ническую сторону дела. 2.5. Примеры программ. Вернемса и известной стандартной схеме Бъд (см. п. 2.2 и 2.3), на примере которой пояспвм введен- ные попятив (см. рис. 4.2, а). Рассмотрим две программы (8«л, 1д) в (8«д, 1»), гдв 1д и 1« — интерпретацви, которые сейчас будут заданы формально, но неформально ужв обсудтдалвсь в $1 этой глави. Интерпретацва 1 задана следующим образом: область интерпретации Юд — множество всех целых неотри- цательных чисел; 1д (х) = 4; 1 (у) = О; 1 (а) = 1; 1д (») = О, где Од Ю«д». Юд — функция умножения чисел, т. е. СО(, ° д(,) = я, х („. 1д (Ч = Н~ где Н: Юд -«" Юд — функция вычитания единвдсдд т. е.
Н(д() = дд — 1; 1д (р) = Рд, гдв Рд: Юд -» (О, 1) — предикат «равно О», т. е. д(=О, Рд(~) =~ О Программа (Юс.в, 1) вычисляет 4!. Интерпретация 1в задана следующим обрааом: область интерпретацвн Рв = гв, где г = (а, Ь, с); 1в (л) = або~ 1, (у) = е, где е — пустое слово; 1в (а) = з; 1 [б) = СОЛГАВ, где СОЯБСАВ: Рв -с- Р— фуякция, приписывающая первую букву первого слова к началу второго слова, т.
е. СОДг8САВ (ссб,у) = ау, где сс Е г, 6 Е гв, р Е гв; 1 (Ь) = СРВ, где СРВ: Рв -с- Рв — функция, стирающая первую букву слова, т. е. СРВ [ссб) = 6, где И Е г', 6 я г'в; 1, (р) = Р, где Р: Рз- (О, Ц вЂ” предикат вравно сэ, т. е. /1, если а=а, ( О, если ачье. Протокол крогрвыыы (Ясс. 1Д, Коифкгурвцяя Ывтиа 3авчвкяя: У ив ис ис ив ис ив ис иг ис иэ им игг ип ип игс ига 0123423423423423 4 4 4 4 3 3 3 2 2 2 1 $ ! О О О О 4 4 4 4 4 $2$2422424 24 24 24 24 24 П р о т о к о л к р о г р в и ы ы (Яс.с 1с). Конфигурация Мотка Зяачввза: У 32 ив ис ив ив ис ив ив ис иа ис ип ип игв О $2 3 4 2 3 4 2 3 4 2 3 аЬсаЬсаЬсвЬсЬсбс Ьс с с с в в в в а а а а а Ьа Ьа Ьа сба сЬв сЬа сЬв Программа (Яс т, 1 ) преобразует слово ябс в слово сЬа. Заметим, что в обеих рассмотренных программах интерпретация переменной у (т.
е. ее начальное значение) несущественна: можно было бы 1, (у) взять проиавольпым числом, а 1в (у) — произвольным словом, причем первая программа по-прежнему будет вычислять 4(, а вторая — переворачивать слово аЬс. На рис. 4.2, б, в показаны обе программы в неформальной графовой форме. Неформальность етого представления программ состоит в том, что программа не показана как пара — схема в трафовой форме и ивтерпретацвя, а в схему вместо функцноналыпах и предикатных символов непосредственно подставлены общепринятые обозначения функций, полученных интерпретацией этих.
символов. Подобным неформальным, но наглядным представлением программ мы будем пользоваться и далее в првмерах. Протокол выполнения программы (Ю .в, 1,) конечен, результат программы — число 24. Протокол выполнения программы (Яв„т, 1г) тоже конечен, программа останавливается с результатом сЬа. ф 3. Эквивалентность и главные свойства стандартных схем 3.1. Эквивалентность, тоталъность, пустота, свобода. Говорят, что стандартная схема Я в базисе 33 к«столька, если для любой интерпретации 1 бааиса л) программа (о", 1) останавливается; стандартная схема Я луста, если для любой интерпретации 1 программа (Л, 1) зацикливается.
Отношение аквивалеятности вводится для стандартных схем в одном бааисе. Если схемы Я, и Я» построены в двух различных базисах Ж и э«», то можно их «приеестк к одному базису», в качестве которого ваять объединение базисов %» и М . Говорят, что стандартные схемы Я, и Я в бааисе л«функ«виояальио эквивалентны (Ю, — Ю ), если для любой интерпретации 1 бааиса Ю программы (о„Х) и (Юв, 1) либо обе зацикливаются. либо обе останавливаются с одинаковым результатом, т. е. ча1 (Ю„Х) ~ та1 (Я» Х)- Примеры тоталъных, пустых и эквивалентных схем приведены на рис, 4.3. Х(еиочкой стандкртной сквмм назовем: 1) конечный путь по вершинам схемы, ведущий от начальной вершины к заключительной, или 2) бесконечный путь по вершинам, начинающийся начальной вершиной схемы.
В случае, когда вершина о — распознаватель, условимсн снабжать каждое очередное вхождение о в цепочку дополнителъным верхним индексом Оили 1, в зависимости от того,по какой иа двух исходящих иа вершины и дуг продолжается построение цепочки. Таким образом, цепочку можно записывать как последовательность меток вершин, причем некоторые из атих меток имеют верхний индекс О или 1.
Прнмеры цепочек схемы Я«л (рнс. 4.2, а): (О, 1, 2', 5) (О, 1, 2«, 3, 4, 2«, 3, 4, 2', 5) (О, 1, 2', 3, 4, 2', ..., 2', ...). Х(елочкой оявракюров назовем последовательность операторов, метящих вершины некоторой цепочки схемы. Так, среди цепочек операторов схемы 8«есть следующие: (старт (к), у:= а, р' (к), стоп (у)) (старт (к), у := о, р' (к), у:= у (к, у), к:= й (к) ° р" (т). у:= у (к, у), := )» (к), рв ( ), ..., р' (к), ° ° )- Предикатные символы в цепочке операторов помечены теми же верхними индексами О или 1, которыми помечены соответствующие метки распознавателей в цепочке. (В отличие от индексов месткости, которые мы в этих случаях будем опускать, индексы О и 1 не заключены в скобки.) Пусть Ю вЂ” стандартная схема в базисе эв, 1 — некоторая интерпретация базиса Я, (О, 1, й», й,...) — последовательность меток инструкций схемы Я, выписанных в том порядке, в котором Ф З Рис.
4.3. Привары стаэхарганх стан: а — 8ьэ, 6 — Х~ ~; ю — 8ь, э — уэ'е эти метки входят в конфигурации протокола выполнении программы (о, Х). Ясно, что эта последовательность — цепочка схемы 8. Будем говорить, что интерпретация Х подтверждает (нлп лорождаевг) эту цепочку. Цепочку стандартной схемы в баэисе МВ нааовем дспуанамой, еслк она подтверждается хотя бы одной интерпретацией этого баэиса. 84 Не всякая цепочка стандартной схемы является допустимой. В схеме о«э, изображенной на рис. 4.3, о, цепочки (О, 1, 2«, 5, 6>, 7), (О, 1, 3, 3, 4«, 7) и все другие конечные цекочкн не подтвер>кдаются ни одной интерпретацией.
Различие между понятиями «цепочка» и «допустимая цепочка» схемы существенно. Первое понятие определено «синтаксически» без привлечения интерпретаций и поэтому про>це второго. У нас будет возможность убедиться, что свойство допустимости цепочек играет чрезвычайно важную роль в а«дачах, связанных с изучением введениыхв этом рааделе свойств схем программ. В частности, внимание исследователей привлекает класс так называемых свободных схем программ. Стандартная схема см>бедна, если все ее цепочки допустимы.
Допуспиилял >(евочка оя«ряторов — это цепочка операторов, соответствующая допустимой цепочке схемы. В тотальной схеме все допустимые цепочки (и допустимые цепочки операторов) конечны, в пустой схеме все допустимые цепочки (и допустимые цепочка операторов) бесконечны. В этом разделе иы дали формальные определения главных свойств стандартных схем; зтн же определения переносятся и на другие классы схем программ. Названные свойства и связанные с ними проблемы образуют опорные пункты схематологии, все опн вэаимоаависимы, и в то же время в каждой нз них отражаются специфические задачи (и трудности) теории и практики программирования.
Белее частные свойства схем будут введены далее по ходу. изложения, или останутся аа рамками атой книги, илн составят материал для самостоятельной работы, началом которого послужит аадание 4.3. Заданне 4.3. А. На рнс. 4.3 лавы прнмеры стандартных схем. Устаноапте, к«кне нэ пвх тот«льны, какпе — пусты. Канне п«ры схем фувкцнанельно экэнэелентвы) Укажете с»ободные схемы. Б. Покажите, что а«пошевне фукшжопэльной экэввэлентностн стандартных схем является м«темэтаческкм атношенпем экэкэелевтноств, т. е. оно рефлекснэно, спмжтрпчво в травэнтнэне.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
