WikiSysop: 1 версия

2008-10-23T16:47:49Z

1 версия

Новая страница

==Определение==
'''Random Access Machine''' («машины со произвольным доступом») — теоретическая модель вычислителя (см. например [[машина Тьюринга]]),
напоминающая современный компьютер, программируемый непосредственно в терминах инструкций процессора (или на языке Assembler) (в теории сложности вычислений под ''машинами'' традиционно понимают ''single-purpose machines''), т. е. машины, созданные для решения какой-либо одной фиксированной задачи, а в терминах программиста это скорее программы).

RAM-машина состоит из (См. Рисунок):
* Конечная входная read-only лента, куда записываются входные данные.
* Полубесконечная выходная write-only лента, куда записываются результат работы машины.
* Бесконечное число регистров <m>r_0,r_1,r_2,\ldots,</m>, каждый из которых может хранить целое число, причем регистр <m>r_0</m> является выделенным, и называется «сумматором» — этот регистр используется при арифметических операциях как накопитель, т. е. как второй операнд и место хранения результата.
* Программа, состоящая из конечного числа инструкций, каждая из которых содержит адрес и команду с операндом. Таблица со списком команд приведена ниже.
Важный, характеристический момент — в качестве операнда можно использовать как произвольный регистр, так и регистр, номер которого храниться в другом регистре — так называемая косвенная адресация.
* Регистр-счетчик «PC», указывающий на текущую команду.

Обратите внимание, что несмотря на «примитивный ассемблер», RAM-машины потенциально мощней любых существующих компьютеров, и физически нереализуемы — т. к. оперируют бесконечной памятью, доступ к любой ячейке-регистру которой осуществляется мгновенно, при выполнении соответствующей инструкции, и каждая ячейка этой памяти может содержать произвольное целое число (т. е. неограниченна по размеру). Но эта модель уже дает возможность вводить более-менее формальные определения времени выполнения программы, и соответственно, сложности алгоритма.

==Иллюстрация==
<latex>
%Created by jPicEdt 1.x
%Standard LaTeX format (emulated lines)
%Wed Aug 24 21:22:49 MSD 2005
\unitlength 1.3mm
\begin{picture}(120.31,90.00)(0,0)

\linethickness{0.15mm}
%Rectangle(10.00,10.00)(90.00,20.00)
\put(10.00,10.00){\line(1,0){80.00}}
\put(10.00,10.00){\line(0,1){10.00}}
\put(90.00,10.00){\line(0,1){10.00}}
\put(10.00,20.00){\line(1,0){80.00}}
%End Rectangle

\linethickness{0.15mm}
%Polygon 0 0(20.00,20.00)(20.00,10.00)
\put(20.00,10.00){\line(0,1){10.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(30.00,20.00)(30.00,10.00)
\put(30.00,10.00){\line(0,1){10.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(40.00,20.00)(40.00,10.00)
\put(40.00,10.00){\line(0,1){10.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(50.00,20.00)(50.00,10.00)
\put(50.00,10.00){\line(0,1){10.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(60.00,20.00)(60.00,10.00)
\put(60.00,10.00){\line(0,1){10.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(70.00,20.00)(70.00,10.00)
\put(70.00,10.00){\line(0,1){10.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(80.00,20.00)(80.00,10.00)
\put(80.00,10.00){\line(0,1){10.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(90.00,20.00)(95.00,20.00)
\put(90.00,20.00){\line(1,0){5.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(90.00,10.00)(95.00,10.00)
\put(90.00,10.00){\line(1,0){5.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(95.00,20.00)(95.00,20.00)

%End Polygon

\linethickness{0.15mm}
%Bezier 0 0(95.00,20.00)(98.75,13.28)(98.75,13.13)
\qbezier(95.00,20.00)(98.75,13.28)(98.75,13.13)
%End Bezier

\linethickness{0.15mm}
%Bezier 0 0(98.75,13.13)(98.75,12.97)(95.00,10.00)
\qbezier(98.75,13.13)(98.75,12.97)(95.00,10.00)
%End Bezier

\linethickness{0.15mm}
%Rectangle(50.00,30.00)(90.00,60.00)
\put(50.00,30.00){\line(1,0){40.00}}
\put(50.00,30.00){\line(0,1){30.00}}
\put(90.00,30.00){\line(0,1){30.00}}
\put(50.00,60.00){\line(1,0){40.00}}
%End Rectangle

\linethickness{0.15mm}
%Rectangle(10.00,50.00)(40.00,60.00)
\put(10.00,50.00){\line(1,0){30.00}}
\put(10.00,50.00){\line(0,1){10.00}}
\put(40.00,50.00){\line(0,1){10.00}}
\put(10.00,60.00){\line(1,0){30.00}}
%End Rectangle

\linethickness{0.15mm}
%Rectangle(20.00,70.00)(50.00,80.00)
\put(20.00,70.00){\line(1,0){30.00}}
\put(20.00,70.00){\line(0,1){10.00}}
\put(50.00,70.00){\line(0,1){10.00}}
\put(20.00,80.00){\line(1,0){30.00}}
%End Rectangle

\linethickness{0.15mm}
%Polygon 0 0(40.00,80.00)(40.00,70.00)
\put(40.00,70.00){\line(0,1){10.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(50.00,80.00)(55.00,80.00)
\put(50.00,80.00){\line(1,0){5.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(50.00,70.00)(55.00,70.00)
\put(50.00,70.00){\line(1,0){5.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(105.00,90.00)(105.00,90.00)

%End Polygon

\linethickness{0.15mm}
%Bezier 0 0(55.00,80.00)(58.75,73.28)(58.75,73.13)
\qbezier(55.00,80.00)(58.75,73.28)(58.75,73.13)
%End Bezier

\linethickness{0.15mm}
%Bezier 0 0(58.75,73.13)(58.75,72.97)(55.00,70.00)
\qbezier(58.75,73.13)(58.75,72.97)(55.00,70.00)
%End Bezier

\linethickness{0.15mm}
%Rectangle(70.00,70.00)(80.00,80.00)
\put(70.00,70.00){\line(1,0){10.00}}
\put(70.00,70.00){\line(0,1){10.00}}
\put(80.00,70.00){\line(0,1){10.00}}
\put(70.00,80.00){\line(1,0){10.00}}
%End Rectangle

\linethickness{0.15mm}
%Bezier 0 0(65.00,80.00)(65.47,73.28)(66.88,73.13)
\qbezier(65.00,80.00)(65.47,73.28)(66.88,73.13)
%End Bezier

\linethickness{0.15mm}
%Bezier 0 0(66.88,73.13)(68.28,72.97)(65.00,70.00)
\qbezier(66.88,73.13)(68.28,72.97)(65.00,70.00)
%End Bezier

\linethickness{0.15mm}
%Polygon 0 0(65.00,70.00)(70.00,70.00)
\put(65.00,70.00){\line(1,0){5.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(70.00,80.00)(65.00,80.00)
\put(65.00,80.00){\line(1,0){5.00}}
%End Polygon

\put(35.00,75.00){\makebox(0,0)[cc]{$x_2$}}

\put(35.00,65.00){\makebox(0,0)[cc]{}}

\put(45.00,75.00){\makebox(0,0)[cc]{$x_3$}}

\put(75.00,75.00){\makebox(0,0)[cc]{$x_n$}}

\put(25.00,55.00){\makebox(0,0)[cc]{Program Counter}}

\put(15.00,55.00){\makebox(0,0)[cc]{}}

\put(15.00,55.00){\makebox(0,0)[cc]{}}

\put(0.00,60.00){\makebox(0,0)[cc]{}}

\linethickness{0.15mm}
%Polygon 0 0(30.00,80.00)(30.00,70.00)
\put(30.00,70.00){\line(0,1){10.00}}
%End Polygon

\put(25.00,75.00){\makebox(0,0)[cc]{$x_1$}}

\put(70.00,55.00){\makebox(0,0)[cc]{{\Large RAM--Program}}}

\put(15.00,15.00){\makebox(0,0)[cc]{$y_1$}}

\put(25.00,15.00){\makebox(0,0)[cc]{$y_2$}}

\put(35.00,15.00){\makebox(0,0)[cc]{$y_3$}}

\put(45.00,15.00){\makebox(0,0)[cc]{$y_4$}}

\put(55.00,15.00){\makebox(0,0)[cc]{$y_5$}}

\put(65.00,15.00){\makebox(0,0)[cc]{$y_6$}}

\put(75.00,15.00){\makebox(0,0)[cc]{$y_7$}}

\put(85.00,15.00){\makebox(0,0)[cc]{$y_8$}}

\put(60.00,80.00){\makebox(0,0)[bc]{входная read-only лента}}

\put(25.00,85.00){\makebox(0,0)[cc]{}}

\put(55.00,10.00){\makebox(0,0)[tc]{выходная write-only лента}}

\linethickness{0.15mm}
%Bezier 0 0(40.00,55.00)(43.44,54.38)(45.00,50.00)
\qbezier(40.00,55.00)(43.44,54.38)(45.00,50.00)
%End Bezier

\linethickness{0.15mm}
%Bezier 0 1(45.00,50.00)(46.56,45.63)(50.00,45.00)
\qbezier(45.00,50.00)(46.56,45.63)(50.00,45.00)
\put(50.00,45.00){\vector(4,-1){0.12}}
%End Bezier

\linethickness{0.15mm}
%Bezier 0 0(60.00,60.00)(58.44,66.25)(47.50,65.00)
\qbezier(60.00,60.00)(58.44,66.25)(47.50,65.00)
%End Bezier

\linethickness{0.15mm}
%Bezier 0 1(47.50,65.00)(36.56,63.75)(35.00,70.00)
\qbezier(47.50,65.00)(36.56,63.75)(35.00,70.00)
\put(35.00,70.00){\vector(-1,4){0.12}}
%End Bezier

\linethickness{0.15mm}
%Bezier 0 0(60.00,30.00)(60.47,24.69)(39.38,28.75)
\qbezier(60.00,30.00)(60.47,24.69)(39.38,28.75)
%End Bezier

\linethickness{0.15mm}
%Bezier 0 1(39.38,28.75)(18.28,32.81)(15.00,20.00)
\qbezier(39.38,28.75)(18.28,32.81)(15.00,20.00)
\put(15.00,20.00){\vector(-1,-4){0.12}}
%End Bezier

\put(110.00,45.00){\makebox(0,0)[cc]{}}

\put(105.00,85.00){\makebox(0,0)[cc]{}}

\linethickness{0.30mm}
%Rectangle(110.00,70.00)(120.00,80.00)
\put(110.00,70.00){\line(1,0){10.00}}
\put(110.00,70.00){\line(0,1){10.00}}
\put(120.00,70.00){\line(0,1){10.00}}
\put(110.00,80.00){\line(1,0){10.00}}
%End Rectangle

\put(115.00,75.00){\makebox(0,0)[cc]{$r_0$}}

\linethickness{0.15mm}
%Rectangle(110.00,60.00)(120.00,70.00)
\put(110.00,60.00){\line(1,0){10.00}}
\put(110.00,60.00){\line(0,1){10.00}}
\put(120.00,60.00){\line(0,1){10.00}}
\put(110.00,70.00){\line(1,0){10.00}}
%End Rectangle

\put(115.00,65.00){\makebox(0,0)[cc]{$r_1$}}

\linethickness{0.15mm}
%Rectangle(110.00,50.00)(120.00,60.00)
\put(110.00,50.00){\line(1,0){10.00}}
\put(110.00,50.00){\line(0,1){10.00}}
\put(120.00,50.00){\line(0,1){10.00}}
\put(110.00,60.00){\line(1,0){10.00}}
%End Rectangle

\put(115.00,55.00){\makebox(0,0)[cc]{$r_2$}}

\linethickness{0.15mm}
%Rectangle(110.00,40.00)(120.00,50.00)
\put(110.00,40.00){\line(1,0){10.00}}
\put(110.00,40.00){\line(0,1){10.00}}
\put(120.00,40.00){\line(0,1){10.00}}
\put(110.00,50.00){\line(1,0){10.00}}
%End Rectangle

\put(115.00,45.00){\makebox(0,0)[cc]{$r_3$}}

\linethickness{0.15mm}
%Rectangle(110.00,30.00)(120.00,40.00)
\put(110.00,30.00){\line(1,0){10.00}}
\put(110.00,30.00){\line(0,1){10.00}}
\put(120.00,30.00){\line(0,1){10.00}}
\put(110.00,40.00){\line(1,0){10.00}}
%End Rectangle

\put(115.00,35.00){\makebox(0,0)[cc]{$r_4$}}

\linethickness{0.15mm}
%Rectangle(110.00,20.00)(120.00,30.00)
\put(110.00,20.00){\line(1,0){10.00}}
\put(110.00,20.00){\line(0,1){10.00}}
\put(120.00,20.00){\line(0,1){10.00}}
\put(110.00,30.00){\line(1,0){10.00}}
%End Rectangle

\put(115.00,25.00){\makebox(0,0)[cc]{$r_5$}}

\linethickness{0.15mm}
%Polygon 0 0(110.00,20.00)(110.00,15.00)
\put(110.00,15.00){\line(0,1){5.00}}
%End Polygon

\linethickness{0.15mm}
%Polygon 0 0(120.00,20.00)(120.00,15.00)
\put(120.00,15.00){\line(0,1){5.00}}
%End Polygon

\linethickness{0.15mm}
%Bezier 0 0(110.00,15.00)(117.19,11.72)(118.75,13.13)
\qbezier(110.00,15.00)(117.19,11.72)(118.75,13.13)
%End Bezier

\linethickness{0.15mm}
%Bezier 0 0(118.75,13.13)(120.31,14.53)(120.00,15.00)
\qbezier(118.75,13.13)(120.31,14.53)(120.00,15.00)
%End Bezier

\linethickness{0.15mm}
%Bezier 0 0(90.00,45.00)(93.13,47.34)(96.25,61.88)
\qbezier(90.00,45.00)(93.13,47.34)(96.25,61.88)
%End Bezier

\linethickness{0.15mm}
%Bezier 0 1(96.25,61.88)(99.38,76.41)(110.00,75.00)
\qbezier(96.25,61.88)(99.38,76.41)(110.00,75.00)
\put(110.00,75.00){\vector(4,-1){0.12}}
%End Bezier

\put(51.25,51.25){\makebox(0,0)[cl]{{\tiny 0: LOAD $r1$}}}

\put(50.00,50.00){\makebox(0,0)[cc]{}}

\put(51.25,48.75){\makebox(0,0)[cl]{{\tiny 1: ADD 3}}}

\put(51.25,46.25){\makebox(0,0)[cl]{{\tiny 2: STORE $r7$}}}

\put(51.25,43.75){\makebox(0,0)[cl]{{\tiny 3: LOAD 77}}}

\put(51.25,41.25){\makebox(0,0)[cl]{{\tiny 4: STORE $*r7$}}}

\put(51.25,38.75){\makebox(0,0)[cl]{{\tiny 5: JUMP 100}}}

\put(60.00,36.25){\makebox(0,0)[cc]{$\ldots$}}

\linethickness{0.30mm}
%Rectangle(10.00,10.00)(20.00,20.00)
\put(10.00,10.00){\line(1,0){10.00}}
\put(10.00,10.00){\line(0,1){10.00}}
\put(20.00,10.00){\line(0,1){10.00}}
\put(10.00,20.00){\line(1,0){10.00}}
%End Rectangle

\linethickness{0.30mm}
%Rectangle(30.00,70.00)(40.00,80.00)
\put(30.00,70.00){\line(1,0){10.00}}
\put(30.00,70.00){\line(0,1){10.00}}
\put(40.00,70.00){\line(0,1){10.00}}
\put(30.00,80.00){\line(1,0){10.00}}
%End Rectangle

\end{picture}

</latex>

==Список команд==

<latex>
\begin{tabular}{|l|l|l|}
\hline
\textbf{LOAD} OP & $r_0 \leftarrow OP$ & Загрузить операнд в сумматор \\
\hline
\textbf{STORE} OP & $r_{OP} \leftarrow r_0$ & Сохранить сумматор в регистре\\
\hline
\textbf{ADD} OP & $r_0 \leftarrow r_0 + OP$ & Прибавить операнд к сумматору\\
\hline
\textbf{SUB} OP & $r_0 \leftarrow r_0 - OP$ & Вычесть операнд из сумматора\\
\hline
\textbf{READ} OP & $r_{OP} \leftarrow input $ & Загрузить ячейку из входной ленты в $r_{OP}$ и перейти к следующей.\\
\hline
\textbf{WRITE} OP & $OP \rightarrow output $ & Записать $OP$ в текущую ячейку выходной ленты и перейти к следующей.\\
\hline
\textbf{JUMP} OP& $PC \leftarrow OP $ & Установить счетчик команд в $OP$.\\
\hline
\textbf{JGTZ} OP& $PC \leftarrow OP :r_0>0 $ & Установить счетчик команд в $OP$, если $r_0>0$\\
\hline
\textbf{JZERO} OP& $PC \leftarrow OP :r_0=0 $ & Установить счетчик команд в $OP$, если $r_0=0$\\
\hline
\textbf{HALT}& & Остановить работу.\\
\hline
\end{tabular}
</latex>

[[Category:Теория сложности]]
{{replicate-from-custiswiki-to-lib}}

Random Access Machine - История изменений

WikiSysop: 1 версия