μ^1proj21(1),其中1是固定引數。
如果我們窮舉一下可變引數,就會發現:
proj21(1,0)=1
proj21(1,1)=1
我們永遠也拿不到0,也就不存在最小化。也就是說,對於μ^1proj21而言,並不是每一個輸入都對應一個輸出,所以應用最小化操作,我們成功地構建了一個偏函式。
加減乘三種操作都在上文構建過了,現在就只剩下一個除了。除法div需要用最小化操作來構建。
假設,我們收到兩引數a和b,想求a\/b,那麼其中存在如下關係:
a=qxb+r,其中0≤r<b
我們想要的就是滿足式子qxb≤a的最大的q,這等同於滿足(q+1)xb>a,於是帶餘除法被轉化為了一個最小化問題:
找到最小的q使其滿足(q+1)xb>a
也就是構造一個函式f:N^3—N
f(a,b,q)=1如果(q+1)b≤a,=0如果(q+1)b>a
f(a,b,q)=lessthanequal(mult(succ(q),b),a)
f=lessthaneual·[mult·[succ·[proj33],proj32],proj31]
其中lessthanequal=iszero·sub
iszero=sub·[succ·zero,proj11]
sub是減法器
對f進行最小化操作即可得到我們想要的結果。
驗證一下:
f(8,5,0)=lessthanequal(mult(1,5),8)=1不等於0,所以0不是輸出。
f(8,5,1)=lessthanequal(mult(1,5),8)=0,最小,所以1是輸出。
div(8,5)=8\/\/5=1沒錯,十分完美。
如果我們想計算一下8\/\/0:
f(8,0,0)=lessthanequal(mult(1,0),8)=1不等於0,所以0不是輸出。
f(8,0,1)=lessthanequal(mult(2,0),8)=1不等於0,所以0不是輸出。
無論我們給f(8,0,x)傳入什麼x,都找不到最小的x,所以div(8,0)=8\/\/0無解,符合現實。
如果把最小化操作運用在原始遞迴函式上,得到的新函式就叫做偏遞迴函式。
好了,現在加減乘除我們都有了,只要是可計算的演算法,我們都能執行。
至於無限迴圈怎麼製造出來,從μ^1proj21(1)和div的栗子都可以看出來,如果最小化操作找不到最小值,就永遠不會給出輸出,這相當於while語句的功能。
——————————————————
下一章是正常內容