Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 75
Текст из файла (страница 75)
Ассемблер элементарных логических операций. Пусть Т вЂ” произвольная машина Тьюринга. Интерпретаторы !пЬ(Ст/Е) — это программы, а при создании любых программ легче сначала определить, какие надо производить действия, а потом — адреса ячеек памяти, где будут находиться данные для них и куда будут записываться их результаты. Таким ячейкам будут сначала даны имена. Постараемся выбирать их так, чтобы они были выразительными, т.
е. напоминали, о чем идет речь. Программу !п6(С5Ц будем писать на ассемблере или автокоде элементарных логических операций, а затем укажем, как ее закодировать, т. е. перейти к указанному выше способу изображения элементарных логических операций..Ассемблер элементарных логических операций отличается от широко применяемых программистами ассемблеров для реальных машин следующим. !. Одно и то же имя в разных командах программы можно заменять при кодировании разными адресами. 2. Алфавит символов, из которых состоят слова-имена, для большей выразительности имен не фиксирован в отличие от ассемблеров реальных машин.
3. Будем неформально пользоваться аналогиями, например заменять многоточием части программы, если из не- опущенных команд видно, что оно заменяет. Указанные отличия не имеют принципиального значения и введены ради удобства изложения. Описание машины Тьюринга Т. Как было указано 361 в 5 5.2, машина Тьюринга Т определяется следующими параметрами: количеством внутренних состояний и, количеством т символов алфавита, употребляемого для изображения информации в ячейках ленты машины Т, и таблицей переходов ТаЬ, которую изобразим несколько иначе, чем в $ 5.2, Она будет состоять из элементов ТаЬу,,~ (1=1, 2,...,в; Ь=1, 2,...,т; 1=1, 2,...,п+ль+3), принимающих значения 0 или 1.
Если в таблице, приведенной в 5 5.2, есть переход зг~ зуть- Иг аут«тоэеь (топе, Ц, топе,=1т, топе»=КЬ), то Табьмг=ТаЬ;,,«=ТаЬь»„ь .ьь=1, а при остальных значениях ! ТаЬ!в~=О. Время работы интерпретатора!пй (Ст/ь), который мы будем конструировать, — ВР, причем константа  — не лучшая, а степень полиномиальной интерпретируемости машины Тьюринга на машине элементарных логических операций Т. равна 2. Сложнее устроен интерпретатор, выполняющий свою работу за О (1!п1) действий ь'-машины.
Представление параметров процесса вычисления и машины Т, принятое нами прн описании интерпретатора на языке ассемблера, аналогично предложенному выше представлению таблицы переходов. !. Представление ленты. Занумеруем ячейки ленты машины Тьюринга Т так, чтобы в начале вычисления читающая и пишущая головки находились над ячейкой с номером О.
Так как на каждом шаге она либо переходит к ближайшей ячейке, находящейся справа или слева, либо остается на месте, на 1-м шаге (1= 1, 2, , 1) головка находится над ячейкой с номером ч, где — 1+1(ч(! — 1, а на первых 1 шагах она находится над ячейками с номерами от удим (1) до 7тах (1), где — 1(члм (1) (~0, 0(~~щах (1) < 0 Су щественной для работы интерпретатора Тл1~ (СтЯ,) части лепты соответстнуют идентификаторы Валь», где 1=0, ч 1, ~2, ..., + (1 — 1), а Ь=1, 2...,т.
Если в ячейке с номером 1' записан Ь.й символ ьут», то Вал,л — — 0 при 6=1, 2, ...,й — 1, /г+1, ..., ш и Вал!л=!. Можно иметь информацию только о «нетривиальной» части ленты, вне которой во всех ячейках стоят одинаковые символы пробела ),, это важно для конструирования «бесконечного» интерпретатора 1п1 (Т(Т.), но тогда макрооператоры з1ер (1) должны быть более сложными, Мы не будем заниматься такой интерпретацией. 2. Представление внутреннего состояния м а ш и н ы Т. Текущее внутреннее состояние описывается переменными еур», а внутреннее состояние на следующем шаге, вычисляемое при помощи таблицы переходов Тау,— переменными зф (1=1, 2, ..., л).
Если машина Т находится в 1-м состоянии, то з(р,=згрх=...=з(рг-1=а(ргь =- ...=з(р =О, з(р~=1. Аналогичные значения имеют переменные з(В. 3. Представлен и я символов, читаемых машиной Тьюринга из ячеек ленты, над которой находится головка машины, и записываемых в эти ячейки в конце 1-го шага. Рассматриваемые символы описываются соответственно переменными зут г~ и зут ге~ (1=1, 2, ..., т) с аналогичными значениями, например, если прочитан 1-й символ, то зут г~=зут гз=...=аут гг 1=зутч.,=.„=аут г„,= =О и зут г~ 1. 4. Представление номера ячейки ленты, над которой расположена головка (текущего номера т). Длина представления зависит от номера шага.
На 1-м шаге текущий номер» описывается переменными т ~~.ь »-~+э,..., »-ь то. »ь ..., т~-м»; ь Все опи должны быть равны О, кроме одной переменной»х, соответствующей ячейке машины Т с номером я, над которой расположена головка. Так как перед началом счета головка стоит над нулевой ячейкой и после каждого шага сдвигается на одну ячейку вправо, влево или остается на месте, — 1+1(й<1— — 1. 5.
Представление движения головки посл е ш а г а. Оно описывается переменными Ц, Тт, )»л. Если головка должна двинуться влево, то Ц=1, остаться на месте — Тт=1, двинуться вправо — )хл 1. Остальные переменные равны О. Макрооператоры Мер(1). Шаг работы машины Тьюринга Т состоит в том, что оиа читает символ из ячейки ленты, определяет новое внутреннее состояние машины, символ на ленте н движение головки, пишет в ячейку ленты новый символ, производит движение головки и переходит в новое состояние. Аналогичные действия, но уже многошаговые, производят макрооператоры егер (1): з1ер (1): )г (1); сотр (1); Му (1); А (1 + 1). Рассмотрим макрооператоры, выполняющие отдельные функции шага„.
Р(1):зут гд. = Вал Как без условных действий найти информацию о нужной 363 Ячейке на ленте — пеРеменные Валь! с тем значением 1, для которого т!=1? Т!рименим прием, который и в даль. нейшем будет применяться многократно: нужные значения умножим, на 1, ненужные — па О и все сложим (умножение и сложение могут быть арифметические — Х, + — или логические — Й, !/; машина элементарных логических операций Е, естественно, предпочтет вторые). Таким образом, нам предстоят вычисления по формулам: ! — ! яут г: = '/ (Вап яхт!) й= 1 2 " и с= — Н-! Эту запись можно считать определением макрооператора Р(!) в нашем ассемблере.
Она расписывается на элементарные логические операции следующим образом: )г (!);яут г: = / (Вап! й т,.):яут г,: =Вал, /=-Ю+! !' — !+! ' (1= — !+1, у=1) р: = Ваг!,+,, 8!т !ч,, ~ 0 = — !+2 й=!) яут г,:=аут г!~/р; р:=Вап,,стт !; (1 = — 1, й = 1) яут г,: = яут г, !/ р;~ р: = Вал! .. й т! !; (1=!' — 1, й=1) яут г,: = яут г! !/ р;! ЯУт г,:=Вап !+,,с!т ьь!, (1 = — !'+1, й=2) р: = Вап, с'! т -'+сп '+' 1(1 = — !+ 2, й = 2) яуп! г,: = яут г,'/ р; 364 р: = Вал!,! У!т,; яут г,: = яут г, !/ р; р: = Валь! й т!; яут г,: = яугп г! !/ р; ~()=О, й= 1) ! (1=1, й=1) р: = Вааг, сг тг аут г:=аут г ~/р; зут г»: = Вал „+,, й ч,+г, р: = Ваи, г,г сгт,+г,' р: =- Вал,, сг тг зут г:г кут г ~/р. Формулы, которыми мы будем пользоваться в дальнейшем, расписываются аналогичным образом.
Поэтому не давая такого развернутого описания макрооператоров, будем иногда выписывать только типичный <внутренний цикл» и указывать, как изменяются индексы. Нужно еще подсчитать число элементарных логических операций в макрооператоре Я(1). Оно равно т(1+2 (2г — 2)) =4тг — Зт. Макрооператоры сотр(г), (гг(г) и Л(г+1), Собственно элементарное действие машины Тьюринга Т состоит в определении внутреннего состояния машины на следующем шаге, символа, который надо записать в ячейку ленты, и движения головки.
Макрооператор сотр(г) интерпретирует определение этих параметров при помощи таблицы Тай. Пусть на гьм шаге вычисления из частичной конфигурации С" машина Тьюринга Т находится в 1'-м состоянии (1< <1'<а) и читает с ленты й'-й символ (1<й'<и). Тогда в процессе работы макрооператора з(ер (1) переменные згр;=ОЦМ1'), з1ргч =1, а после работы макрооператора В(г) переменные зут г,=О(1гчьй'), зут г»=1. Если машина Т должна перейти в 1-е состояние, записать гга ленту д-й символ и произвести й-е движение головки (й= — 1 означает движение влево, В=Π— неподвижность,6=1 — движение вправо), то Табг,ма=Табг'.м, чх=ТаБ~'», » чу+а= 1, а при остальных значениях 1 ТаЬг,» г=О. Внутреннее состояние машины Т на следующем (г+ +1)-м шаге описывается переменными з(гг= (1=1, 2,..., а), символ, который надо записать, — переменными зут юг (1= =1, 2, ..., т), движение головки — Ц, Тт, Дгг.
Перенести в них табличные значения можно при помощи логических действий: з(гг: = ~/ '/ (Та(гг ь г сгз1р Ь зут г ) = Тай, г-1 ь=г 365 (1=1,2, ..., п); и зут а,: = '/ ~/ (ТаЬ,. „, 3 з1 р, 3 аут г ) = ТаЬи и „+,, Ьм ь-1 (1=1,2, ...,т); И:= '/ '/ (ТаЬ1 „+~ч,йе(р,.реут г Д =-ТаЬ, „,„+ +,', !'=1 ь 1 и т .(т:= Ч '/ (ТаЬ,. „+ + 3|1р,алеут г ) =ТаЬ, +,, и т РЛ: = '/ / '(ТаЬ,. „и+ „. 3 з!рт й аут г ') = ТаЬг и и+ + .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
