1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 51
Текст из файла (страница 51)
Две сравнимые схемы Янова Функционально вквивалентны тогда и только тогда, когда они эквивалентны окерационно. В сторону от операционной эквивалентности к функциональной доказательство непосредственно вытекает из определений: поскольку'последовательность операторов в операционной истории в точности такова, каков их порядок применения к памяти при выполнении интерпретированных схем, а исходное состояние одно и то же, то на любом шаге применения операторов операционно эквивалентных схем мы будем иметь одинаковые состояния памяти, в том числе и после перехода к астапову. В обратную сторону доказательство более сложно и существенно опирается на то, что схемы эквивалентны для любой интерпретации. Принципиальная идея доказательства заключается в том, что подыскивается особая интерпретация У, которая в памя- » х».
эквивллвнтность схим янОВА 249 ти накапливает операционную историю выполнения схемы. В зависимости от выбранного исходного состояния формируется та или иная история вычислений. Разнообразия исходных состояний достаточно, чтобы создать в процессах выполнения схемы все возможные ее операционные истории. Оказывается, что если одна схема вырабатывает некоторую операционную историю, то другая схема не может выработать другую, так как в атом случае нарушилась бы эквивалентность в интерпретации Р.
Состояния памяти изображаются двумя словами, Ь н ш, где Ь вЂ” слово в алфавите логических значений и операторных символов: оно будет накапливать операционную историю выполнения интерпретированной схемы. В свою очередь ш — это бесконечная последовательность логических значений: оно будет источником наборов текущих значений предикатных переменных при очередном шаге выполнения программы. Назовем пару наборов логических значений (Л, Л') допустимой для оператора А(Р), если множество номеров компонент, в которых наборы Л и Л' отличаются друг от друга, является подмножеством номеров предикатных символов, принадлежащих сдвигу Р.
По определению, оператор А(Р) может прн своем срабатывании перевычислить только те предикатные переменные, которые входят в сдвиг Р. Таким образом, допустимая пара — это такие Л и Л', что Л может быть «сдвинут» до Л' с помощью А(Р). ()пределим теперь точно интерпретацию у. Пусть функционалцно эквивалентные схемы Сд и 6» даны над пРеднкатными символами р„..., рь и содерн«ат вместе операторы А,(Р,), ..., А„(Р„);<рд(Ь, ш) определена и равна(Ь, ш') тогда, когда ш =- ЛЛ'1«, где (Л, Л') — любая допустимая пара для оператора Ад(Рд), а 1« — «остаток» слова ш. В этом случае Ь' = ЬЛАд, ш' = Л'Я.
Для остальных состояний памяти цд не определена (1 = 1,..., и). я,(Ь, ш) определена всегда и равна д-й букве слова ш (д = 1, ..., Ь). Напомним, что Я обозначает пустое слово. Л е м м а 1. Если в интерпретации У схемы 6(ры..., рь) Ро,у (Я, ш) = (Ь', ш'), Ь'Л Я = Но,у (й», ш)"), где Л вЂ” первые Ь букв слова ш'. е) Для того чтобы конструкции были формально сравнимы, мы полагаем, что в Н верхкял в нижняя последовательности слиты в едву; Л«А«,Л,А«, мт.
д. Глг К ОПРЕДЕЛЕНИЕ СХЕМ ЯНОВА' Точное доказательство этой леммы, которое предоставляется читателю, требует индукции по числу шагов выполнения схемы 6 в интерпретации г' на исходном состоянии памяти (Я, и). Г7 Итак, рассмотрим любую интерпретацию Х и любое исходное состояние памяти о(, для которых определено выполнение хотя бы одной из схем 61 и 6 и, стало быть, го,,г(1() = рс„г("). Рассмотрим операционную историю данного вычисления любой из этих схем, скажем, 61: бл На,.г(1() = А,.
А, Е Воаьмем в интерпретации г' исходное состояние памяти (йо П1о) ГДЕ )Ло = К1, и о ~ой1 '" Лл~ где ло — любая бесконечная последовательность логических значений, а Я вЂ” пустое слово. Утверждается, что в этом случае Ро„г(йо п1о) =(йоАцйл-. 411 йФ). Доказательство этого утверждения практически совпадает с доказательством леммы, с одной лишь разницей: в лемме мы доказываем, что в интерпретации (г схема в слове й фиксирует историю своей работы, какова бы она ни была, а в атом утверждении мы обнаруживаем, что выполнение воспроизведет именно ту историю, которая нас интересует, а именно Но„г (д). Так как схемы 6, и 6, эквивалентны в любой интерпретации, в том числе и в л', то мы получаем, что ро,,г(йо юо) = (боА1 йл".-411 ба~2) ° В силу леммы мы заключаем, что На„г(йо юо) ='~оАЬЛ1" А1лбл ' Теперь нам осталось показать, что и история вычисления Роьг будет той же самой.
Поскольку мы рассматриваем совместную интерпретацию схем 61 и 61, то начальное -значение предикатных переменных р, ..., рл для 61 на начальном состоянии памяти Ы будет то же самое,что и для 61, т. е. Ло. История работы 6, в интерпретации г' показывает нам, что на входном наборе Ло первым выполняемым оператором в 6, будет оператор А... т, е. тот же, что ив исто-, $7.3. эквивллкнтность схем яыовл рии На„д(дд). Опять-таки в силу совместности интерпретации после срабатывания оператора Ад, в схеме Сг мы получим то жв состояние памяти гУ = юд, (д) и тот же набор значений предикатпых переменных Лд, что и в На,д(дд). Повторив только что проведенное рассуждение шаг за шагом, мы получим, что На.л(д() = Нс.,ъ (йо* идо) = «сед (д)1 что н требовалось доказать.худ С л е д с т в и е.
Если две схемы 6, и 6, эквивалентны в интерпретации дд, то они эквивалентны в любой интерпретации. Действительно, пусть для некоторой интерпретации 1 и исходного состояния памяти И определены ро„д(д() и соответствующая операционная история Но,л(а). В интерпретации дд существует начальное состояние памяти (Йо, юо), вычисляющее зту историю. Так как С, иС эквивалентны в дд, зто же состояние памяти создает такую же историю для Со. Повторив заключительное рассуждение теоремы, мы убедимся, что зта же история будет получена при вычислении по схеме в интерпретации 1 для исходного состояния памяти г).с7 Посмотрим повнимательнее, чем замечательна интерпретация дг. Множество аначений ()д, и>) = Ра,г (О, и~о) дает множество г(й) всех операционных историй схемы 6, которое, как мы выяснили, полностью характериаует вычислительные возмонсности схемы.
Только что доказанное следствие можно сформулироватьеще одним способом. Л е м и а 2. Две схемы С„и С, функционально эквивалентны тогда и только тогда, когда множества их операционных историй совпадают. Формальная эквивалентность. Самое интересное в схемах Янова зто то, что множество операционных историй можно извлечь из схемы, не прибегая к понятию интерпретации. Опишем процедуру построения некоторых конструкций, которые мы нааовем конфигурациями, для любой схемы Янова 6(р„..., р„).
Конфигурации по внешнему виду неотличимы от операционных историй, хотя строиться будут принципиально иным методом. П а ч а л ь н ы й ш а г. Верхняя и нижняя последовательности пусты. Воаьмем л ю б о й набор Ло = (и„..., оь) в качестве значений переменных р„..., рь, занесем его в верхнюю последовательность и перейдем к начальной вершине. 0 ч е р е д н о й ш а г. Пусть с набором Л перешли к вершима д: а) если о' — помеченный распоанаватель, то мы попали в пустой цикл, построение конфигурации обрывается безрезультатно; Гл.
7. Опэеделенне схем янОВА б) если ' Я вЂ” непомеченный распознаватель Л с условием г(р„..., рь), то помечаем Л, вычисляем г(й) и с тем >ке набором переходим к преемнику вершины г! в соответствии со значением г(Л); в) если 3 — останов, ставим в нижнюю последовательность символ останова Я; построение конфигурации завершено; г) если 8 — оператор А>(Р!), то помещаем А! в нижнюю последовательность, а в верхнюю последовательность помещаем п р о и з в о л ь и ы й набор й', образующий с набором Ь допустимую пару (й, й') для оператора А>(Р!).
Снимаем разметку распознавателей и с набором с>' переходим к единственному преемнику оператора А!. Только что описанный процесс является частным случаем важной общематематической конструкции, называемой порождающим процессом. Описание порождающего процесса очень похоже на описание алгоритма, и сам порождающий процесс похож на процесс вычисления. Важным отличием является то, что в некоторых местах порождающего процесса есть точки неопределенности (недетермииизма), в которых однозначный вычислительный акт заменяется актом произвольного выбора, правда, из некоторого точно описанного (в нашем случае даже конечного) множества.
Из-за наличия точек неопределенности порождающий процесс создает (епорождаеть) целое множество своих возможных исходов. Множество, задаваемое порождающим процессом, считается аффективно заданным множеством, так как возможность осуществить любой выбор в точках недетерминизма по соглашению признается бесспорной. Легко понять, что алгоритм является частным случаем порождающего процесса, у которого единственная точка неопределенности — зто произвольный выбор начальных данных для алгоритма. Вернемся к множеству К(6) конфигураций схемы Янова С.
Л е м м а 3. Множество конфигураций любой схемы Янова совпадает со множеством ее операционных историй. Включение в одну сторону следует из определения операционной истории, а в другую сторону вытекает вз еитерлретации >> и относящейся к ней лемме 1.~ Определение. Две схемы Янова ь'т(р>, ..., р„) и б (р„..., рь) формально эквивалентны, если К(а,) = К(а,).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
