第1章 上一章註釋[001](3 / 3)

μ^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語句的功能。

——————————————————

下一章是正常內容

本站所有小說均來源於會員自主上傳,如侵犯你的權益請聯絡我們,我們會盡快刪除。
本站所有小說為轉載作品,所有章節均由網友上傳,轉載至本站只是為了宣傳本書讓更多讀者欣賞。
Copyright © 2024 https://www.zhongzhuxsw.tw All Rights Reserved