非奇異矩陣提示您:看後求收藏(八零中文www.80zw.tw),接著再看更方便。

加法器add,add(x,y)=x+y,怎麼用那三種基本函式組合?

也很簡單,從具體輸入入手:

add(3,2)=succ(add(3,1))=succ(succ(add(3,0)))=succ(succ(3))

似乎只需要組合多個後繼函式就可以了呢。

當然,這裡面有一個毛病,在於我們在沒有定義好add的前提下,先入為主地認為add(3,0)=3.

所以我們不能認為自己就這麼簡單地構造了add,只能退而求其次地得到以下關係:

add(x,y+1)=succ(add(x,y)),這個式子是十分嚴謹的。

更具體地,要想算出add(x,y+1),就要知道add(x,0)=x,我們稱add(x,0)=x為基準條件;add(x,y+1)=succ(add(x,y))為遞迴條件。

看起來就差臨門一腳了,只要我們能用三種基本函式構造出add(x,0)=x,就能得到add(x,y+1),也就能構造出我們想要的加法器。

也很顯然,add(x,0)=x=proj11

於是,我們的加法器有了。

這種看起來很像左腳踩右腳登天的構造方式叫做“原始遞迴”,它的定義是這樣的:

基準函式f:Nn—N

遞迴函式g:Nn+2—N

使用f和g的原始遞迴h=pn(f,g):Nn+1—N

對於h:

基準條件:h(x1,...xn,0)=f(x1,...,xn)

遞迴條件: h(x1,...,xn,y+1)=g(x1,...,xn,y,h(x1,...,xn,y))

回到我們的加法器add:

add:N2→N

add(x,y)=x+y=p1(f,g)

基準條件:add(x,0)=f(x)=proj11

遞迴條件:add(x,y+1)=g(x,y,add(x,y))=succ(add(x,y)),g=succ·[proj33]

add=p1(proj11,succ·[proj33])

完美無瑕。

類似地,乘法器mult=p1(zero,add·[proj13,proj33])

前繼函式,減法器等等基本運算都可以據此定義,只需要proj,zero,succ三種原始函式和組合·,原始遞迴p這兩種基本操作。所有完全函式都可以據此構造。

那麼“偏函式”呢?

構造偏函式還需要額外的一個操作:最小化。

如果我們有一個函式f:N^n+1—N (這裡^代表上標,雖然不好看,但實在是敲得太麻煩沒有耐心了),具體的f(a1,...an,x),其中a1,...an是固定引數,x是可變引數。

那麼最小化操作為:μ^nf:N^n—N它會找到給它輸入的n個引數裡,最小的一個,並輸出

比如f(5,4,3,2,1,0)=0

如果遇到重複引數,那麼就輸出第一個最小的。

比如f(5,4,3,2,1,1)=1

假設我們有一個投影函式長這樣:

proj21:N2—N (proj21中的2是上標,1是下標,下同,寫不動擺爛了)

那麼μ^1proj21:N—N

舉個栗子:

假如我們給proj21弄一個最小化操作:

科幻靈異推薦閱讀 More+
民間傳說集合

民間傳說集合

秀麗江湖
關於民間傳說集合: 這本民間故事集猶如一扇通往恐怖世界的大門。在這裡,有被詛咒的森林,每到深夜便會傳出詭異的聲響,彷彿有看不見的生物在穿梭。有神秘的古井,井水倒映出的不是人影,而是令人毛骨悚然的未知存在。還有古老的廟宇,看似寧靜,卻在不經意間瀰漫出恐怖的氣息,彷彿有邪惡的力量在蟄伏。每一個故事都是一場恐怖之旅,帶你走進充滿驚悚與神秘的民間傳說世界,挑戰你的膽量極限。
科幻 連載 78萬字
路仁和瑪雅的謎語生活

路仁和瑪雅的謎語生活

比迪
關於路仁和瑪雅的謎語生活: 路仁和她相遇時,一個末日預言剛好在龍國流傳開來。一年後,地球將可能毀滅。而讓路仁奇怪的是,隨著預言的出現...充斥著救贖與死亡的...無所不能的和...神秘的與...如雨後春筍般出現在路仁的生活中...當2037年即將過去的鐘聲響起...路仁卻發現最初的預言竟與自己有著千絲萬縷的聯絡...
科幻 連載 94萬字
詭校禁地

詭校禁地

小倔驢
詭校禁地由作者(小倔驢)創作連載作品,該小說情節跌宕起伏、扣人心絃是一本難得的情節與文筆俱佳的好書,919言情小說免費提供詭校禁地全文無彈窗的純文字線上閱讀。
科幻 連載 32萬字
本店招牌菜

本店招牌菜

[美]斯坦利·艾林
本店招牌菜由作者([美]斯坦利·艾林)創作連載作品,該小說情節跌宕起伏、扣人心絃是一本難得的情節與文筆俱佳的好書,919言情小說免費提供本店招牌菜全文無彈窗的純文字線上閱讀。
科幻 連載 24萬字