§1.3　URM-可計算性函數

定義1.3.1　設f：?n→?為部分（部分有定義）函數.

（a）P（a1，a2，a3，…）↓收斂于b，如果P（a1，a2，a3，…）↓且P（a1，a2，a3，…）停機時，第一個存儲單元R1中的數為b，記為P（a1，a2，a3，…）↓ b；

（b）P是URM-可計算f，如果?a1，a2，a3，…，an，b有P（a1，a2，a3，…）↓ b當且僅當（a1，a2，a3，…，an）∈dom（f）且f（a1，a2，a3，…，an）=b，記P計算的函數為fP，則它們的關系為

（解讀：要注意的是，一個程序P可計算函數f，指的是對f定義域中的數都是可計算的.對于f定義域外的數它是不用可計算的.）

（c）f為 URM-可計算函數，如果存在一個程序P，它可以URM-可計算f.

（解讀：這段教材表明我們通常認為可計算的離散函數都可以編成一個程序，或者編成一個編碼在計算機中運行，一個無窮函數的信息與編碼的信息量是等價的.）

例1.3.1　已知初始結構為（8，3），程序P為I1：J（3，2，5）；I2：S（1）；I3：S（3）；I4：J（1，1，1），求fP（8，3）.

解：模擬計算如下：

所以fP（8，3）=11.

程序P其實計算的是fP（x，y）=x+y.通過把y個1加到x上，就可得到x+y，將x，y分別存儲在R1，R2中，將R3做成一個計數器.即

例1.3.2

我們將x存儲在R1中，將R2做成一個計數器．即

其程序為I1：J（1，4，9）；I2：S（3）；I3：J（1，3，7）；I4：S（2）；I5：S（3）；I6：J（1，1，3）；I7：T（2，1）.

例1.3.3

我們將x存儲在R1中，將R3做成一個計數器．即

其程序為 I1：J（1，2，7）；I2：S（3）；I3：S（2）；I4：S（2）；I5：S（2）；I6：J（1，1，1）；I7：T（3，1）.

例1.3.4　f（x，y）=xy的程序為I1：J（1，4，10）；I2：J（2，5，10）；I3：J（1，4，7）；I4：S（3）；I5：S（4）；I6：J（1，1，3）；I7：S（5）；I8：Z（4）；I9：J（1，1，2）；I10：T（3，1）.