Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 76
Текст из файла (страница 76)
у=! и=1 Расписать эти операции в виде последовательности элементарных логических действий можно образом, аналогичным примененному при конструировании макрооператора )1(1). Укажем здесь действия внутреннего цикла при данных значениях 1, й и 1. Удобно, чтобы 1 был внутренним индексом Если 1 — самый внешний, то при изменении Й выполняется действие р1: = е1р; Ь еуп1 г~; а затем для 1=1, 2, ..., п, п-(-1, ..., и+ т+3 р2:=ТаЬ,.„, йр1; Йее,: = Яез,3 р2.
Здесь при 1 1, 2, ..., п )1ея — это зф, при 1 и+1, п+2, ..., и+т — аут ач „; йезич.т+,— — Ц, йееи+тч.з —— 1т, Нее„+ +з=Я)ь При 1' 1 и й 1 во внутреннем цикле можно иметь одну команду— Яез,: =- ТпЬ... й р1; (1 = 1, 2, „,, п + т + 3). Общее количество элементарных логических операций в макрооператоре сотр (1) равно (пт — 1)(2 (и + т + 3) + 1) -1- п -)- т + 4 = = пт(2п+ 2т+ 7) — и — т — 3, т. е. зависит только от параметров машины Тьюринга Т.
Макрооператор (й'(1) состоит из элементарных логических операций: 366 р1:= )т;: Вап в:=Вап,. Йр1; р2: = вут ыв Ь т,; Вап.; = Вапв в '/ р2; (~ — 1+ 1, — 1+ (1=1,2, ..., т)) 0,1,...,1 — 1). Если на 1-м шаге вычислений из конфигурации С головка машины Тьюринга Т стоит над 1'-й ячейкой ленты, то в процессе интерпретации этого шага т~ =! и ъ~ О( — 1+1( ~1~! — 1, )чь)'), Поэтому в результате действий макро- оператора ((7(1) все значения Ваап« не изменятся, кроме Вапг,м которые станут равными в1т шв (й=1, 2,, т). Количество элементарных логических операций равно 2!в — 1+ (21 — 1)Ут (21 — 1) (Зт+!) = (бт+2)! — Зт — 1.
Макрооператор А(1+!) устанавливает новое внутреннее состояние, т. е, изменяет переменные вгр~ (1' 1, 2,..., п) и двигает головку, т. е. изменяет переменные т~(/= — й — 1+1, ..., 1). Отметим, что на предыдущих шагах переменных т; и тч не было. Значения вгр; просто делаются равными вф: в1рзп вЦ; (1 1, 2, ...
„п). Если должен произойти сдвиг головки влево, то новые значения т~ должны стать равными старым т;.ь1, если головка неподвижна, то значения т~ не изменяются, если она движется вправо, то т; станут равны старым значениям Однако необходимо учитывать «краевые эффекты» — отсутствие на предыдущем шаге переменных т ь Учитывая еще значения переменных Ц, )т и Яй, можно доказать, что новые значения т, определяются формулами: тв: = (т ь, й Ц) '~' (т.
ЬТт) ',' (т, с'Яп); (у — — — 1+ 2, —,1+3, ...,1 — 2); т,„,: =- (т,ь,йЦ) Ч(»,,Ыт)! т,.: = (ч,+, й Ц); ~ — 1' ( ~ — ! ) ' ( 1 — 2 )' ) т,: = (т,, ЬИ). Расписать эти операции в виде последовательности элементарных логических действий можно, например, следую- 367 щим образом: ( ), э:=-т! !Ы4 7! !!=т! !Ь(т; т!:= э! ! Ь)тй; т!-р! ~/7В (7' = — !+ 2, — ! + 3, „,,— 1, О, 1, ..., ! — 2) ту. 'т! ~/ бх,. ! †! ' 1! †! !-!' Их количество равно 1+2+3(2! — 3)+2+1:!-1+2(2! — 3)+ + 1 =10! — 7. В макрооператоре А (2) действия несколько иныа— Однако их 3, т. е.
тоже 10! — 7. Общее количество элементарных логических операций в макрооператоре А (!+1) равно и+101 — 7, а во всем макрооператоре з1ер (!) — (4л!! — Зт)+(лт(2п+2т+7) — и— — и! — 3+ ((6!и+ 2)! — Зп! — 1) + 10!' — 7 = (10!и+ 12)с+ +пт(2п+2т+7) — 7т — п — 11=В'1-1-С', где В' и С' — константы. Кодирование программы элементарных логических действий.
Мы могли бы занумеровать все переменные, которые вычисляются при работе интерпретатора!и!! (С"!!.), и получить программу, которую машина элементарных логических операций «поняла» бы и выполнила. При этом в каждой команде либо некоторой переменной присваивалось яв- 368 (1! !:=-т ЬЦ; 7!'. — — э! Ыт; бгь! —— т! б! М; ((= — !+2,— !+3, ..., — 1, О, 1, ..., ! — 2) т ! = тойЦ' то. эа 3!(л! э! = то й)~(! но указанное значение, либо оно вычислялось в результате операции с переменными, значения которых были ранее определены.
Таким образом, составленная нами программа предопределяет результаты своих вычислений. Однако она не удовлетворяет требованию однократной записи в ячейки памяти. Мы уже указывали, что такую программу можно перекодировать так, чтобы запись информации в каждую ячейку памяти производилась не более одного раза. Сейчас мы укажем способ перекодирования.
Наша программа до перекодирования имеет вид 1:д;:=У;; (1=1, 2, ..., т — 1) т:«конец»; где У> — зто выра>кения О, 1, иь 1 иь шйоь и,~/с„уь иь ш — номера введенных нами переменных (в том числе вспомогательных — р, р1, р2, используемых для промежуточных результатов); т(В( — длина программы, на 1 большая, чем количество злементариых логических операций в ней. Для каждых номера шага 1 работы машины Тьюринга Т от первого до г-го и номера переменной у=1, 2, ..., Ф определим величину»(> (1, д) как номер шага, предшествовавшего )-му, когда в последний раз было присвоено значение переменной у: >(>(1, у) =шах(1)1:д:= У>). г«> Если до)-го шага переменной у не было присвоено никакого значения, то»р (1, д) =О.
Не важно, сколько действий нужно для определения функции >(> (й у), надо только установить, что «правильныйя интерпретатор 1пт>(С"/ь) может быть записан. Правила перекодирования определяются следующей таблицей, где слева приведен вид команды до перекодирования, а справа — после него; 1,:у:= с;->-1,>1,: = с'; 1»>у:=и; 1,:1»>=»(>((„п); 1»>У> = ) н> '»з»»> = ) ')>(>а н)1 1,:у:=ийс; -э(,:1,> =>)>((е и)й»р(1,, и); 1.,: у: = и ~/ о; -»1»: 1» > = »р (1„и) Ч >(> ((„с).
Так как в правых частях (после знака присваивания = ) команд исходной программы имеются только номера переменных у, встречавшиеся в левых частях предыдущих 2 4 — 750 369 команд (перед знаком присваивания:=, т. е. им уже были присвоены какие-нибудь значения), после перекодирования в новых правых частях команд все номера будут меньше номеров самих команд (и равных им номеров переменных в левой части), но больше О.
Итак, мы закончили конструирование макрооператора !пг~(Стт/Е). Читателю предоставляется доказать по индукции, что элементарные логические операции исходной и перекодированной программ с одинаковыми номерами дают одинаковые результаты, хотя они записываются в разньге ячейки памяти (для доказательства справедливости индуктивного предположения, когда команды имеют номер 1, нужно воспользоваться тем, что это — команды вида д:= ='с'). Теорема 9.2.
Если трудоемкость задачи р относительно машины Тьюринга Т не больше 1, то ее можно решить при помощи не более чем ВР+Сг=О (Р) элементарных логических операций'. Доказательство. Если трудоемкость задачи р относительно машины Тьюринга Т не больше 1, то из некоторой частичной конфигурации С" машина Т не более чем за г шагов решит задачу р и остановится, При доказательстве теоремы 9.1 уже говорилось, что в этом случае машина Т.
при помощи интерпретатора уп)г(С"/1,) тоже решит задачу р. В частности, машина элементарных логических операций Е решит ее при помощи построенного выше интерпретатора уагг (С" /ь). Подсчитаем количество элементарных логических операций (последнее действие машины Т. — выполнение команды т: «конец»; — мы не считаем логической операцией): (В' 1+ С') +(В' 2+ С') + ... + (В'.)+ С') = в' г()+1), в', г в +С)= — 1+~ +С~» = 2 2 (, 2 = В)з+ Сг =-0()з), где В=В'/2, С=В'/2+С'. Б ' Напомним смысл обозначений 0(1) и о()), принятых в анализе: ~ д (л) я(л) 0 ()(л)), если знр ! ~=сола))0.
В этом случае гол г,в..) 7(л) зорят, что л(л) — величина того же порядка, что и )(л),я(л) =о(1(л)), а Ыь если Игп — О. В этом случае я(л) называют величнаой более Дл) низкого порядка, чем 1(л), 370 Полиномиальная интерпретируемость машин друг на друга. Аналогичным образом доказывается, что машина с произвольным доступом к памяти и «полным» набором команд — конечным набором операторов вычисления функций от конечного же количества двоичных переменных, условными и безусловными переходами и индексированными командами — полиномиальным образом интерпретируема на машине элементарных логических операций.
Однако в этом случае степень больше трех (сложнее всего интерпретация индексированных команд, особенно адресов, которые могут появиться в результате индексации). Обратная полиномиальная интерпретируемость машины элементарных логических операций Е на машине с произвольным доступом к памяти тривиальна, так как в системе команд последней машины есть все команды первой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
