§1.2　計(jì)算機(jī)模型——無界存儲(chǔ)機(jī)URM

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

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

定義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條指令，否則，進(jìn)入下一條指令.

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

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

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

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

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

（1）P（a1，a2，a3，…）表示程序P對(duì)輸入（a1，a2，a3，…）進(jìn)行計(jì)算.

（2）P（a1，a2，a3，…）↓表示計(jì)算P（a1，a2，a3，…）最終停機(jī).

（3）P（a1，a2，a3，…）↑表示計(jì)算P（a1，a2，a3，…）永不停機(jī).

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

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

通常一個(gè)程序在開始運(yùn)算時(shí)，變?cè)獂=（a1，a2，a3，…，an）中的數(shù)是依次放在存儲(chǔ)單元R1，R2，…，Rn中的，然后用程序P對(duì)輸入a1，a2，a3，…，an進(jìn)行運(yùn)算.

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

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

例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）

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