非奇異矩陣提示您:看後求收藏(品書網www.vodtw.tw),接著再看更方便。

【寫在8月25日20:53,釋出後發現上下標給我全濾了?,我調整一下,過會兒再看】

硬核程度:☆☆☆☆☆

涉及領域:計算理論

大標題:三種函式外加三種操作怎樣解決所有可計算問題?為什麼偏遞迴函式可以製造無限迴圈?

可能是全網最不報菜名、最不裝比的解釋。

以下開始:

首先,什麼是可計算?

可計算就是指,有一個演算法,我們把它交付給計算機後,計算機可以像執行一個函式一樣,接受我們給它的輸入,然後返回輸出,這個輸出就是我們想要的答案。

為了方便描述,先行約定一下數學符號。

假設我們有一個乘法器,叫做mult,它可以接受一對整數作為輸入,把它們相乘後輸出一個整數。

比如,輸入(3,4)輸出12

輸入(6,2)輸出12

輸入(0,6)輸出0

這時,我們把這些輸入數對叫做domain,輸出的一個數叫做codomain。如果我們用Z來代表全體整數集,那麼這個平平無奇的乘法器就可以用數學符號表示為:

mult:Z^2→Z

中間的這個→表示這個mult是一個total function,也許可以稱作“全函式”吧,意思是每一個domain裡的輸入,都能對應一個codomain裡的輸出。

與全函式相對應的是,是“偏函式”。對於偏函式,對於有些輸入,它並不能給出輸出。比如一個除法器,當我們給它(6,0)時,它輸出不了任何東西。這個除法器可以表示為:

div:Z^2—Z

這裡的單橫線代表這是一個偏函式(其實應該用半箭頭表示,但在這裡打不出來)

好了,定義好符號之後,就可以清爽地描述我們的三種基本函式:後繼函式、零函式、投影函式。

後繼函式:succ:N→N,succ(x)=x+1,N代表自然數集。我們給它2,它輸出3;給它3它輸出4。總之就是往上+1.

零函式:zero:Nn→N,zero=0。不管給它什麼,它都輸出0.

投影函式:projn:Nn→N,projin(x1,...,xn)=xi。它接受長度為n的輸入,輸出第i個自然數。比如,proj22(1,3)=3。

好了,蓋大樓的磚塊一共就這麼三種,接下來把它們組合在一起就行了。

我們定義一個叫“組合”的函式f,它的功能是把n個函式組合在一起:

f:Nn—N

具體的,如果每一個被組合的函式g都可以接受同一組引數(x1,...,xm),那麼組合n個g函式的操作可以被表示為:

f·[g1,...,gn]:Nm—N

展開為:

f·[g1,...,gn](x1,...,xm)=f(g1(x1,...,xm),...,gn(x1,...,xm))

舉個栗子:

我們構造一個函式one,one(x)=1,即:不論給它什麼輸入,它都輸出為1,那麼:

one(x)=succ(0)=succ(zero(x))

即:succ·[zero]=one

驗證一下:

succ·[zero](x)=succ(zero(x))=succ(0)=1

succ和zero兩個基本函式組成了我們要的one,完美。

如果栗子再複雜一點,我們想要一個

科幻靈異推薦閱讀 More+
末世投資,女神給我打工

末世投資,女神給我打工

飛星無月
關於末世投資,女神給我打工: 末世降臨,秩序崩壞!前世的江源,舔狗舔到一無所有,不僅舔的女神是破鞋,女神肚子裡的孩子還不是自己的,最後更是被姦夫殘忍殺害。重生後的江源,發誓此生絕不做舔狗,他只為自己而活。萬萬想不到,系統竟然逼他當舔狗!……舔狗!真香!
科幻 連載 185萬字
偽裝高嶺花失敗後

偽裝高嶺花失敗後

昭昭宵宵
江晝是清霄門首屈一指的天才,出了名的興致高雅,清冷寡言。每日除了養花育草就是練劍修行,不論誰來搭話,他要麼不理,要麼回答永遠只有那幾個字。“嗯。”“行。”“好。”“可以。”但其實他有個不可告人的秘密..
科幻 連載 151萬字
快穿黑心蓮:惡毒女配撩瘋了

快穿黑心蓮:惡毒女配撩瘋了

扒個葡萄去
關於快穿黑心蓮:惡毒女配撩瘋了: 花玥繫結雙系統。一個要求她扮演惡毒女配,一個讓她乾死男女主。選哪一個?花玥興奮扛起大錘。這不是順手的事嘛。一起幹!……世界一:太后娘娘與她的替身小情郎原主對男主愛而不得,卻意外都給女主做了嫁衣裳,成為他們愛情的推動者,最後死無葬身之地。花玥:愛而不得?為解相思之苦,她找個替身小情郎紓解一下合理吧?替身年輕貌美活又好。花玥甚慰之。幹掉男主的念頭越發深刻,一不小心就
科幻 連載 174萬字
吞天墓

吞天墓

黑白仙鶴
關於吞天墓: 為宗門出生入死抵禦異族邪魔,換來的卻是背叛和汙衊。直到皇朝母族尋來,面對蘇錚強大的背景,所有人都後悔了。爺爺是仙界的頂級仙帝!父親是縱橫天地的一代殺神!外公號稱人屠,建立魔焰軍橫掃蠻荒!外婆是人人懼怕的毒美人,一怒萬骨枯!還有奶奶,母親,舅舅個個都是極其極其恐怖的存在。擁有逆天背景,蘇錚從此踏上吞天弒神的無敵之路,神擋殺神,魔阻滅魔!“抱歉!在我這裡沒有你們後悔的機會,我!來自地獄
科幻 連載 179萬字