§1.2　計算機模型——無界存儲機URM

要研究算法，不可能只在直覺上研究，必須形式化給出定義.從現(xiàn)在開始，我們會接觸很多種理論計算機，這些都是我們研究算法的基礎、基石.這節(jié)我們來介紹無界存儲機.1963年，Shepherdson 與Surgis設計了無界存儲機（the unlimited register machine，簡稱為URM）.

它是一個單向的帶子，由無窮多個存儲單元構成，記為R1，R2，R3….每個存儲單元在任意時刻只能存一個自然數(shù).每個存儲單元Rn中的數(shù)記為rn.每個無界存儲機均有一個程序.它根據(jù)輸入依程序自動運行.程序由有窮條指令組成.

定義1.2.1　指令種類：

（1）Z（n）稱為零指令，用0替換rn；

（2）S（n）稱為后繼指令，用rn+1替換rn；

（3）T（m，n）稱為傳遞指令，用rm替換rn；

（4）J（m，n，q）稱為躍指令、條件轉(zhuǎn)移指令，如果rm=rn，則執(zhí)行第q條指令，否則，進入下一條指令.

定義1.2.2　P=I1I2…In稱為程序.程序的指令按照下標的次序執(zhí)行，除非碰到躍指令J（m，n，q）.一旦遇到躍指令J（m，n，q）且滿足rm=rn，則執(zhí)行第q條指令，否則進入下一條命令.如果q>n，則此時沒有任何指令可以執(zhí)行，機器停機.此時，將第一個存儲單元中的內(nèi)容作為輸出.

例1.2.1　程序P為I1：S（1）；I2：S（1）；I3：Z（1）；I4：J（1，1，1）.如果在第一個存儲單元R1中的數(shù)據(jù)r1=a，我們就會看到下面的運行結(jié)果：

這里出現(xiàn)了一個死循環(huán)！此時當?shù)谝粋€存儲單元R1中的數(shù)據(jù)r1=a時，程序P對它不可計算.

為了方便計算，我們引入一些符號以表示各種計算狀態(tài).

定義1.2.3　符號規(guī)定：P為一程序，（a1，a2，a3，…）為N中一個無窮序列.

（1）P（a1，a2，a3，…）表示程序P對輸入（a1，a2，a3，…）進行計算.

（2）P（a1，a2，a3，…）↓表示計算P（a1，a2，a3，…）最終停機.

（3）P（a1，a2，a3，…）↑表示計算P（a1，a2，a3，…）永不停機.

進一步規(guī)定：如果（a1，a2，a3，…，an）為N中一個有窮序列.

（1）P（a1，a2，a3，…，an）表示P（a1，a2，a3，…，an，0，0，0，…）.

通常一個程序在開始運算時，變元x=（a1，a2，a3，…，an）中的數(shù)是依次放在存儲單元R1，R2，…，Rn中的，然后用程序P對輸入a1，a2，a3，…，an進行運算.

（2）P（a1，a2，a3，…，an）↓表示計算P（a1，a2，a3，…，an，0，0，0，…）↓.

（3）P（a1，a2，a3，…，an）↑表示計算P（a1，a2，a3，…，an，0，0，0，…）↑永不停機.

例1.2.2　程序由下面的指令組成

I1：J（1，2，6）；I2：S（2）；I3：S（3）；I4：J（1，2，6）；I5：J（1，1，2）；I6：T（3，1）

則運行結(jié)果如下：