【寫在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，完美。

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