Главная Промышленная автоматика.

Код операции

Адрес

LOAD

операнд

STORE

операнд

операнд

операнд

MLLT

операнд

операнд

READ

операнд

WRITE

операнд

JUMP

метка

JGTZ

метка

JZERO

метка

HALT

Рис. 1.4. Таблица команд РАМ.

Чтобы описать действие команды, зададим значение v{a) операнда а:

v( = i) = i, v{i) = cii), v{u} = c(c{i)).

Таблица на рис. 1.5 определяет действие каждой команды из таблицы на рис. 1.4. Команды, действию которых не дано определения (такие, KaKSTORE =i), можно считать эквивалентными команде HALT. Аналогично деление на нуль останавливает машину.

При выполнении любой из первых восьми команд счетчик команд увеличивается на единицу. Поэтому команды в данной программе выполняются последовательно, до тех пор пока не встретится команда JUMP или HALT либо JGTZ при содержимом сумматора, большем нуля, либо JZERO при содержимом сумматора, равном нулю.

Вообще говоря, РАМ-программа определяет отображение из множества входных лент в множество выходных лент. Так как на некоторых входных лентах программа может не останавливаться, это отображение является частичным (т. е. для некоторых входов оно может быть не определено). Это отображение можно интерпретировать разными способами. Две важные интерпретации - интерпретация в виде функции и интерпретация в виде языка.

Предположим, что программа Р всегда считывает с входной ленты п целых чисел и записывает на выходную ленту не более одного



Команда

Действие

LOAD а

с(0)ч у(а)

STORE i

c(0 -c(0)

STORE *t

c(c(0)-c(0)

ADD a

c(0) -с(0) + ф)

SUB a

c(0)+-c(0)-t>(a)

MULT a

c{0)c{0)xv(a)

DIV a

c{0)- L)Ma)J)

READ i

c(i)<- очередной входной символ.

READ SI-

c(c(t))-«- очередной входной символ. В обоих случаях головка входной ленты сдвигается на одну клетку вправо.

8. WRITE а

v(a) печатается в той клетке выходной ленты,

которую в данный момент обозревает ее го-

ловка. Затем эта головка сдвигается на одну

клетку вправо.

JUMP b

Счетчик команд устанавливается на команду с меткой Ь.

JGTZ b

Если с(0)> 0, то счетчик команд устанавливается на команду с меткой Ь, в противном случае на следующую команду.

JZERO 6

Если с{0) = 0, то счетчик команд устанавливается на команду с меткой Ь, в противном случае на следующую команду.

HALT

Работа прекращается.

) Повсюду в этой книге Гх~\ (потолок х) обозначает наименьшее целое, большее или равное х, \ xj (дно, или целая часть х) обозначает наибольшее целое, меньшее или равное х.

Рис. 1.5. Действие команд РАМ. Операнд а есть =t, i или * (.

целого числа. Пусть Xi, х...... х„- целые числа, находящиеся

в п первых клетках входной ленты, и пусть программа Р записывает у в первую клетку выходной ленты, а затем через некоторое время останавливается. Тогда говорят, что Р вычисляет функцию/(xi, . . ., Хп)=у. Легко показать, что РАМ, как и всякая другая разумная



begin read г I;

if rl<0 then write 0 else begin r2r\; rSrl -1; wliile /-3 > 0 do begin г2г2*г1; гЗ гЗ-1 end; write г2 end

Рис. 1.6. Программа для n" на Упрощенном Алголе.

модель вычислительной машины, может вычислять в точности частично рекурсивные функции. Иными словами, для произвольной частично рекурсивной функции / можно написать РАМ-программу, вычисляюш,ую /, и для произвольной РАМ-программы можно указать эквивалентную ей частично рекурсивную функцию. (По поводу рекурсивных функций см. Дэвис [1958] или Роджерс [1967].)

Другой способ интерпретировать программу для РАМ - это посмотреть на нее с точки зрения допускаемого ею языка. Алфавит - это конечное множество символов, язык - множество цепочек (слов) алфавита. Символы алфавита можно представить целыми числами I, 2, . . ., k при некотором k. Данная РАМ допускает (воспринимает) язык в следующем смысле. Пусть на входной ленте находится цепочка s=aia2 . . . а„, причем символ ai расположен в первой клетке, Са- во второй и т. д., а в (я+1)-й клетке расположен О - символ, который будет использоваться в качестве концевого маркера, т. е. маркера конца входной цепочки.

Входная цепочка s допускается РАМ-программой Р, если Р прочитывает все ее символы и концевой маркер, пишет 1 в первой клетке выходной ленты и останавливается.

Языком, допускаемым программой Р, называется множество всех цепочек (слов), допускаемых ею. Для входных цепочек, не принадлежащих языку, допускаемому программой Р, она может напечатать на выходной ленте символ, отличный от 1, и остановиться, а может даже и не остановиться вообще. Легко показать, что язык





0 1 [2] 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021