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