隨機存取機

隨機存取機（random-access machine）是一種計算模型，可視為一種支援間接定址（indirect addressing）的抽象計算機器。本文簡介其定義，並以範例說明如何撰寫隨機存取機程式。

定義

隨機存取機

本文中，我們定義隨機存取機（random-access machine）是由一組指令（instruction）所構成的有限序列，其中每個指令是一個非負整數三元組 $(t, i, j) \period$

例如由 $n$ 個指令所構成的隨機存取機會形如 \[\begin{split} M = \left( \begin{pmatrix}t_0\\i_0\\\.\.j_0\end{pmatrix}, \begin{pmatrix}t_1\\i_1\\\.\.j_1\end{pmatrix}, \ldots, \begin{pmatrix}t_{n-1}\\i_{n-1}\\\.\.j_{n-1}\end{pmatrix} \right) \period \end{split}\]

指令

以下假設指令會操作在暫存器序列 $(R[k])_{k \geq 0}$ 上，每個暫存器中會存放一個整數。我們用 $R[k]$ 表示非負整數索引值 $k$ 所對應的暫存器。

我們定義指令 $(t, i, j)$ 的效果如下：

• 若 $t = 0 \comma$會執行 $R[i] \gets j \period$
• 若 $t = 1 \comma$會執行 $R[i] \gets R[\.j] \period$
• 若 $t = 2 \comma$會執行 $R[i] \gets R[i] + R[\.j] \period$
• 若 $t = 3 \comma$會執行 $R[i] \gets R[i] - R[\.j] \period$
• 若 $t = 4 \comma$會執行 $R[i] \gets R[R[\.j]]$（若 $R[\.j] < 0$ 則不動作）。
• 若 $t = 5 \comma$會執行 $R[R[i]] \gets R[\.j]$（若 $R[i] < 0$ 則不動作）。
• 若 $t = 6 \comma$會在 $R[i] > 0$ 時，使下一個指令跳轉到指令 $j$（若隨機存取機沒有指令 $j \comma$則會直接終止）。
• 若 $t \geq 7 \comma$則不動作。

我們也使用以下記號簡記各個指令。

• $\textsc{Set}\ i, j$ 表示 $R[i] \gets j \period$
• $\textsc{Mov}\ i, j$ 表示 $R[i] \gets R[\.j] \period$
• $\textsc{Add}\ i, j$ 表示 $R[i] \gets R[i] + R[\.j] \period$
• $\textsc{Sub}\ i, j$ 表示 $R[i] \gets R[i] - R[\.j] \period$
• $\textsc{Ld}\ i, j$ 表示 $R[i] \gets R[R[\.j]] \period$
• $\textsc{St}\ i, j$ 表示 $R[R[i]] \gets R[\.j] \period$
• $\textsc{Jgt}\ i, j$ 表示 $R[i] > 0$ 時，跳轉到指令 $j \period$

執行流程

隨機存取機會從指令 0 開始執行。每個非跳轉指令執行完就會接著執行下一個指令；若最後一個指令不是跳轉指令，則執行完該指令後就會停機。若一個指令跳轉時目標不存在（即目標指令的索引值大於或等於指令總數），則該跳轉也會導致停機。

例子

我們使用以下的例子說明如何將演算法轉換為隨機存取機程式。

演算法

考慮以下求最大值所在的索引值的演算法。

演算法 A（求最大值的索引值）　給定整數陣列 $A[0 \twodots n \varminus 1] \comma$其中 $n \geq 1 \period$

$\textsc{IndexOfMax}(A, n)$ 會回傳 $i \in [0 \twodots n \varminus 1] \comma$使 $A[i]$ 是 $A[0 \twodots n \varminus 1]$ 中的最大值。

1. 設 $i \gets 0$ 與 $j \gets 0 \period$
2. 若 $j \geq n \comma$則終止演算法並回傳 $i \period$
3. 若 $A[\.j] - A[i] > 0 \comma$則設 $i \gets j \period$
4. 設 $j \gets j + 1 \comma$並回到步驟 2。

隨機存取機程式

接著我們說明如何將演算法 A 轉換為隨機存取機程式。

我們配置暫存器如下：

• $R[0 \twodots 5]$ 存放暫時變數。
• $R[6]$ 存放陣列最大值的索引值 $i \comma$為程式的輸出。
• $R[7]$ 存放陣列 $A$ 的長度 $n \period$
• $R[8 \twodots n \varplus 7]$ 存放陣列 $A[0 \twodots n \varminus 1] \period$

其中暫時變數的用途如下：

• $R[0]$ 記作 $e \comma$用於存放常數 1。
• $R[1]$ 記作 $c \comma$用於存放迴圈的剩餘迭代次數。
• $R[2]$ 記作 $j \comma$用於存放索引值。
• $R[3]$ 記作 $q \comma$用於存放位址，即 $q = j + 8 \period$
• $R[4]$ 記作 $m \comma$用於存放最大值。
• $R[5]$ 記作 $d \comma$用於存放目前陣列元素減去最大值的差值。

則我們可以將演算法 A（求最大值的索引值）轉換為以下程式：

參考資料

1. Stephen A. Cook and Robert A. Reckhow. Time-bounded random access machines. In Proceedings of the 4th Annual ACM Symposium on Theory of Computing, pages 73–80, 1972. doi:10.1145/800152.804898.