隨機存取機器模型

簡介

引進它是為了便於從理論上分析計算機串列程式所耗費的時間、空間等資源。

一個RAM由k個變址器I1,I2,…,Ik、無窮個普通暫存器R0,R1,R2,…和一個有窮長的程式所組成。變址器也是暫存器，每個暫存器中可以存放一個自然數，但只有變址器的內容可以作為間接地址。

RAM的程式使用兩種形式的地址。一種是直接地址，形式為Ij(j=1,2,…,k)或Ri(i=0,1,2,…);另一種是間接地址,形式為Ij(j=1,2,…,k)。如果Ij中存的自然數為i，則Ij代表地址Ri。

RAM的指令為下列形式之一:①A←a,表示把地址A的內容改為自然數a;

②A←B,表示把地址A的內容改為地址B的內容;

③A←B*C,表示把地址B中的內容和地址C中的內容作為運算*之後,送入地址A。

這裡*可以是自然數的加法、減法、乘法或整數除法。

減法的定義為：若a≥b則等於a-b,否則等於0；

④A←F(B,C)，此處F是一個可以用多帶圖靈機器在多項式空間和對數多項式的巡迴中實現的變換（見多帶圖靈機模型）。A、B、C可以是直接地址，也可以是間接地址。A是寫入地址,B、C是讀出地址。

RAM除了可以用以上的指令編程式外,還可以判斷某個暫存器或變址器的內容是否為0，以實現條件轉移。

變址器是用來實現間接地址的，所以要求在運算過程中變址器中所存的自然數不大於所用到的普通暫存器數目的某個常數倍。

RAM程式的一個例子是：設n個自然數a1,a2,…,an分別存放在R1,R2,…，Rn中，n存放在R0中,要求把這n個數的和計算出來,結果放在R0中。程式如圖：

RAM的資源耗費有兩種定義方式,即均勻耗費和對數耗費。

是指計算中曾經使用過的暫存器的總數。均勻的時間耗費是指自始至終被執行的指令和轉移的總條數。均勻耗費常用於算法分析中。

此時空間耗費指計算中普通暫存器存過的自然數的最大長度之和。時間耗費則指被執行的每條指令的時間耗費之和。而一條指令的時間耗費則被認為與被運算的自然數的長度成正比的。

對於RAM,還可以定義巡迴（虛擬的並行時間）。它是計算中周相的總數，而一個周相則是 RAM工作的一個階段，在此階段中，沒有任何一個普通暫存器先被寫入然後又被讀出。