Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 74
Текст из файла (страница 74)
Интерпретация ' машинных действий. Конфигурация 1п1(См,(М~), моделирующая на некоторой машине М1 вычисления из конфигурации См, машины Мщ называется интерпретатором второй машинй на первой: при вычислении из этой конфигурации машина М1 выдает, т. е. получает определенным образом закодированные результаты, которые выдала бы машина М, при втпчислении из конфигурации См„и, может быть, дополнительную информацию. Интерпретаторы, выдающие промежуточные результаты вычисления, полезны при отладке программ (обычно они моделируют машину на самой себе), а при проектировании новой машины они дают возможность заранее приготовить некоторые программы для массовых вычислений и обслуживания работы будущей машины, а также проверить, как будут работать ее устройства в ситуациях, которые удается предвидеть. Не менее важно теоретическое значение интерпретации.
Так, описание алгоритма в терминах некоторой алгоритмической модели сводят к его описанию в виде конфигурации машины Тьюринга при помощи построения интерпретатора модели на последней. В частности, приведенное в $5.2 доказательство возможности решить любую алгоритмически разрешимую задачу на одной и той же универсальной машине Тьюринга У состояло в указании способа интерпретации произвольной машины Тьюринга Т ' Здесь н далее термины «интерпретация» и «интерпретатор» используются а программистском смысле, ие имеющем отношения к тому смыслу, а котором ати понятия испольаоаалнсь а гл. В н 7.
на машине О. Мы будем заниматься интерпретацией для установления связи между сложностями данной задачи относительно разных машин и разных задач. Интерпретация элементарных действий. Процесс вычисления из любой конфигурации См, машины Ми является последовательностью шагов зр(1), зр(2),...,зр(1)... Соответственно процесс интерпретации можно осуществить как последовательность мпогошаговых операций з1ер(1), е1ер(2) ..., Мер(1)... интерпретации шагов машины Мь Если интерпретирующая машина М1 является машиной с произвольным доступом к памяти, то интерпретацию каждого шага может осуществлять одна и та же подпрограмма ИерЯ, пользующаяся информацией о номере шага и расположении в памяти машины М~ описания элементарного действия, которое должно выполняться на этом шаге.
Блоксхема такого интерпретатора !п1(См,(М,) изображена на рис. 9.1. 'Рис. 9.! Нас, в частности, будет интересовать интерпретация работы произвольной машины М на машине ул для любых конфигураций См машины М и натурального числа 1 будем строить интерпретатор !п1~(См/!.) вычисления первых 1 шагов, причем вычисления машины М будут полностью проинтерпретированы, если на 1-м шаге или раньше М останавливается. Интерпретатор !пгс(См/Ь) можно конструировать в виде последовательности макрооператоров — подпоследовательностей логических операций. Эти макрооператоры выполняют функции блока Иер(1) из блок-схемы 9.1 при 1= 1, 2, ...,1. Программа !п1,(См(!.) — это последовательность макрооператоров 1п1,(См(!.): з1ер(1); з1ер(2); ..., в1ер(1); 11п.
Макрооператоры ИерЯ, з1ер(2), ..., ИерЯ осуществляют интерпретацию шагов вычисления, 11п состоит из одной команды «конец». Блок егер('1) из блок-схемы 9.1, в свою очередь, состоит из подблоков, интерпретирующих «микродействия», выпол- 367 няемые во время одного шага. Аналогичным образом каждый макрооператор Мер(1) в программе Уа1~(См/ь) элементарных логических операций (1=1, 2, ..., Е) состоит из «более мелких» макрооператоров, имеющих те же функции (не пользуясь языком макрооператоров, практически невозможно описывать программы элементарных логических операций). Одно из представлений блока имеет вид 81ер(1): : Р(1); сотр(Г); М7(1). Блок 1«Я имитирует чтение информации из памяти машины Е, необходимой для выполнения 1-го шага, и настраивает следующие блоки на интерпретацию собственно элементарного действия и запись его результата; блок сов«р(1) осуществляет это действие; Ч7(1) записывает результаты по-.
следнего по вычисленным ранее адресам. Частичные конфигурации и их кодирование. Если интерпретируемая машина М из конфигурации См кончает работу через 1 шагов или раньше или интерпретируются только 1 первых шагов работы машины М, то можно полностью не описывать конфигурацию См, а ограничиться только состояниями читаемых на этих шагах з ячеек памяти (з(р1).
Это основано на следующем очевидном утверждении. Лемма 9.1. Пусть конфигурации С и С' машины М отличаются только состояниями устройств, не используемых, и ячеек памяти, не читаемых в процессе иычисления из первой конфигурации. Тогда машина М «не заметит разницы» между С, и С'„т.е. в процессах вычисления из них перед шагами с одинаковыми номерами состояния всех устройств М будут одинаковыми, будут прочитаны одни и те,же ячейки и произведены одни и те же действия. Д о к а з а т е л ь с т в о.
На первом шаге для конфигураций См и С„*, читаются одни и те же ячейки, выполняются одни и те же действия. Следовательно, одинаковым образом меняются состояния одних и тех же ячеек памяти машины М и ее устройств. Таким образом, перед вторым шагом состояния «задействоваиных» на нем ячеек памяти и устройств для обеих конфигураций будут одинаковы. П Назовем частичной конфигурацией С", определяющей данный процесс вычисления и, набор начальных состояний устройств и ячеек памяти, используемых машиной М в процессе я. Рассмотренным в лемме конфигурациям С и С; соответствует одна и та же конфигурация С".
Для интерпретации процесса я вычисления из частичной конфигурации См, машины М«на машине Мь продолжаю- 358 щегося не более г шагов, илн первых 1 шагов процесса, в машину М, нужно ввести описания состояний Иь Им ... ..., зс1» устройств машины Мд и зть з>из, ..., зв4 ее ячеек памяти, где з(р(, ц — максимальное число ячеек памяти машины Мз, которые могут понадобиться при выполнении одного ее шага. Пусть |~(1'=1, 2,„„й) — количества возможных состояний этих устройств и 1 — количество возможных состояний ячеек памяти, 1= гпах ((ь( )+2.
Упоря>'=ь2,...,» дочим некоторым образом устройства машины М» и ее ячейки памяти и рассмотрим описания номеров команд н адресов данных в виде слов алфавита, состоящего не более чем из 1 — 2 символов. Состояние каждого устройства и каждой ячейки памяти можно обозначить символом такого алфавита.
Добавим еще разделители «;» для состояний устройств и ячеек памяти и «:» для номеров команд, адресов данных и параметров для вычисления номеров или адресов. Каждое описание адреса должно встретиться среди возможных состояний устройств, определяющих чтение из памяти; значит, его длина не превосходит й н оно должно быть повторено либо начальным состоянием устройств, либо данными, записанными в читаемых ячейках памяти. Частичная конфигурация С„, может быть описана словом, имеющим длину не более чем 2(й+з), в алфавите, состоящем не более чем из (разных символов: з,в., Ы,; ...; Ы»; А:А,: ...: зт~зт» ...; Ах: ... : зш» ... Ин„. Будем называть это слово описанием частичной конфигурации См, в самой машине Мм а число символов в нем— длиной описания С", и обозначать (С" ~.
Можно считать, что интерпретирующая машина М~ «понимает» символы 0 и 1. Каждому символу аут«(я=1, 2,... ..., 1), используемому для описаний частичных конфигураций Смм, в машине Мь можно поставить в соответствие слово 0 0 ... 010 ... 0 длины(в алфавите 0,1. Заменим каждый к-ь г-я символ таким подсловом и получим слово в том же двух- символьном алфавите, также определяющее частичную конфигурацию Смм,— с,с»...с, с»н см см~ь......,с,ь Есть более экономный способ кодирования, в котором д-му символу соответствует изображение натурального числа д в двоичной позиционной системе с добавлением, если потребуется,сле- 359 ва символов 0 так, чтобы длины всех подолов были одинаковыми, но порядок длины описания конфигурации См от этого не меняется. Итак, длина описания конфигураций С в алфавите 0,1, «понятном» любой интерпретирующей машине М и, в частности, машине элементарных логических операций 1, имеет длину г1, где г= (См, (<2(й+з) <2(/г+1) р1= =А'1.
Полиномиальная интерпретируемость. Пусть для любых частичной конфигурации С." машины Мд и натурального ма числа 1=1, 2... возможна интерпретация первых 1 шагов вычисления из частичной конфигурации С" интерпретатором 1п1~(С~,/М~), состоящим из блоков (макрооператоров) з|ер(1), 1(п, и при каждом 1=1, 2, ..., и интерпретация 1-го шага зрЯ машины Мр производится не более чем за В'1с ' шагов, где В' и С вЂ” положительные константы, причем С= 1. Тогда машина М, называется полиномиальным образом со степенью С, интерпретируемой на машине М,. Теорема 9.1. Пусть машина Мз полиномиальным образом со степенью С интерпретируема на машине М„и задача р решается на машине Мз из частичной конфигурации См, не более чем за 1 шагов, после чего машина останавливается.
Тогда задача р может быть решена на машине М~ не более чем за В1с шагов, где  — положительная константа, т. е. ее сложность относительно машины М, не больше В1с Доказательство. Будем производить интерпретацию процесса и решения задачи р на машине М~ интерпретатором /п1~(См,/М~), о котором идет речь в определении понятия полнномиальной интерпретируемости.
Работа блоков (макрооператоров) з1ер(1) при 1=1, 2, ...,1 требует не более чем В ° 1с +В 2~ '+... +В 1~ '< /+! < В ~т 'а'г = — ((1+ 1) — 1) < С 1 (21)с н,2~ 1с В ~с шагов. Блок (макрооператор) 1(п состоит нз конечного количества действия 1) (одного действия может не хватить: 360 у современных машин конец работы программы — это ряд действий). Общее количество шагов работы интерпретатора )пЬ~(См'/М,) не больше чем В"ге+В((В"+О)!с=Вгс, так как С~)! и Г)!. Работа машины Мз из частичной конфигурации С" продолжается не более г шагов, после чего машина останавливается.
Значит, она будет полностью проинтерпретирована, и не более чем за В!с шагов на машине М, будет решена рассматриваемая задача р. Таким образом, сложность последней относительно машины М~ не больше, чем В!с. П Перейдем к конкретным машинам М, и М,. Прежде всего рассмотрим интерпретацию произвольной машины Тьюринга Т элементарными логическими операциями. При этом будут продемонстрированы основные приемы конструирования интерпретаторов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
