nba总决赛掘金vs热火,欧洲杯直播时间,cba门票在哪儿买

001 上一章注釋[001]（1 / 2）

【寫在8月25日20:53，發(fā)布后發(fā)現(xiàn)上下標(biāo)給我全濾了，我調(diào)整一下，過會(huì)兒再看】

硬核程度：☆☆☆☆☆

涉及領(lǐng)域：計(jì)算理論

大標(biāo)題：三種函數(shù)外加三種操作怎樣解決所有可計(jì)算問題？為什么偏遞歸函數(shù)可以制造無限循環(huán)？

可能是全網(wǎng)最不報(bào)菜名、最不裝比的解釋。

以下開始：

首先，什么是可計(jì)算？

可計(jì)算就是指，有一個(gè)算法，我們把它交付給計(jì)算機(jī)后，計(jì)算機(jī)可以像執(zhí)行一個(gè)函數(shù)一樣，接受我們給它的輸入，然后返回輸出，這個(gè)輸出就是我們想要的答案。

為了方便描述，先行約定一下數(shù)學(xué)符號(hào)。

假設(shè)我們有一個(gè)乘法器，叫做mult，它可以接受一對(duì)整數(shù)作為輸入，把它們相乘后輸出一個(gè)整數(shù)。

比如，輸入(3，4)輸出

輸入(6，2)輸出

輸入(0，6)輸出

這時(shí)，我們把這些輸入數(shù)對(duì)叫做domain，輸出的一個(gè)數(shù)叫做codomain。如果我們用z來代表全體整數(shù)集，那么這個(gè)平平無奇的乘法器就可以用數(shù)學(xué)符號(hào)表示為：

mult:z^2→

中間的這個(gè)→表示這個(gè)mult是一個(gè)totalfunction，也許可以稱作“全函數(shù)”吧，意思是每一個(gè)domain里的輸入，都能對(duì)應(yīng)一個(gè)codomain里的輸出。

與全函數(shù)相對(duì)應(yīng)的是，是“偏函數(shù)”。對(duì)于偏函數(shù)，對(duì)于有些輸入，它并不能給出輸出。比如一個(gè)除法器，當(dāng)我們給它(6，0)時(shí)，它輸出不了任何東西。這個(gè)除法器可以表示為：

div:z^2—

這里的單橫線代表這是一個(gè)偏函數(shù)（其實(shí)應(yīng)該用半箭頭表示，但在這里打不出來）

好了，定義好符號(hào)之后，就可以清爽地描述我們的三種基本函數(shù)：后繼函數(shù)、零函數(shù)、投影函數(shù)。

后繼函數(shù)：s:n→n，s(x)=x+1，n代表自然數(shù)集。我們給它2，它輸出3；給它3它輸出4。總之就是往上

零函數(shù)：zero:nn→n，zero=0。不管給它什么，它都輸出

投影函數(shù)：projn:nn→n，projin(x1，...，xn)=xi。它接受長度為n的輸入，輸出第i個(gè)自然數(shù)。比如，proj22(1，3)=3。

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

我們定義一個(gè)叫“組合”的函數(shù)f，它的功能是把n個(gè)函數(shù)組合在一起：

f:nn—