【寫(xiě)在8月25日20:53，發(fā)布后發(fā)現(xiàn)上下標(biāo)給我全濾了?，我調(diào)整一下，過(guò)會(huì)兒再看】
【寫(xiě)在8月25日21:03，上下表示例：^上標(biāo)，_下標(biāo)，連續(xù)兩個(gè)數(shù)字前一個(gè)是上標(biāo)后一個(gè)是下標(biāo)】
硬核程度：☆☆☆☆☆
涉及領(lǐng)域：計(jì)算理論
大標(biāo)題：三種函數(shù)外加三種操作怎樣解決所有可計(jì)算問(wèn)題？為什么偏遞歸函數(shù)可以制造無(wú)限循環(huán)？
可能是全網(wǎng)最不報(bào)菜名、最不裝比的解釋。
以下開(kāi)始：
首先，什么是可計(jì)算？
可計(jì)算就是指，有一個(gè)算法，我們把它交付給計(jì)算機(jī)后，計(jì)算機(jī)可以像執(zhí)行一個(gè)函數(shù)一樣，接受我們給它的輸入，然后返回輸出，這個(gè)輸出就是我們想要的答案。
為了方便描述，先行約定一下數(shù)學(xué)符號(hào)。
假設(shè)我們有一個(gè)乘法器，叫做mult，它可以接受一對(duì)整數(shù)作為輸入，把它們相乘后輸出一個(gè)整數(shù)。
比如，輸入(3，4)輸出12
輸入(6，2)輸出12
輸入(0，6)輸出0
這時(shí)，我們把這些輸入數(shù)對(duì)叫做domain，輸出的一個(gè)數(shù)叫做codomain。如果我們用Z來(lái)代表全體整數(shù)集，那么這個(gè)平平無(wú)奇的乘法器就可以用數(shù)學(xué)符號(hào)表示為：
mult:Z^2→Z
中間的這個(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—Z
這里的單橫線代表這是一個(gè)偏函數(shù)（其實(shí)應(yīng)該用半箭頭表示，但在這里打不出來(lái)）
好了，定義好符號(hào)之后，就可以清爽地描述我們的三種基本函數(shù)：后繼函數(shù)、零函數(shù)、投影函數(shù)。
后繼函數(shù)：succ:N→N，succ(x)=x+1，N代表自然數(shù)集。我們給它2，它輸出3；給它3它輸出4。總之就是往上+1.
零函數(shù)：zero:N^n→N，zero()=0。不管給它什么，它都輸出0.
投影函數(shù)：projn:N^n→N，proj^n_i(x1，...，xn)=xi。它接受長(zhǎng)度為n的輸入，輸出第i個(gè)自然數(shù)。比如，proj22(1，3)=3。
好了，蓋大樓的磚塊一共就這么三種，接下來(lái)把它們組合在一起就行了。
我們定義一個(gè)叫“組合”的函數(shù)f，它的功能是把n個(gè)函數(shù)組合在一起：
f:N^n—N
具體的，如果每一個(gè)被組合的函數(shù)g都可以接受同一組參數(shù)(x1，...，xm)，那么組合n個(gè)g函數(shù)的操作可以被表示為：
f·[g1，...，gn]:N^m—N
展開(kāi)為：
f·[g1，...，gn](x1，...，xm)=f(g1(x1，...，xm)，...，gn(x1，...，xm))
舉個(gè)栗子：
我們構(gòu)造一個(gè)函數(shù)one，one(x)=1，即：不論給它什么輸入，它都輸出為1，那么：
one(x)=succ(0)=succ(zero(x))
即：succ·[zero]=one
驗(yàn)證一下：
succ·[zero](x)=succ(zero(x))=succ(0)=1
succ和zero兩個(gè)基本函數(shù)組成了我們要的one，完美。
如果栗子再?gòu)?fù)雜一點(diǎn)，我們想要一個(gè)加法器add，add(x，y)=x+y，怎么用那三種基本函數(shù)組合？
也很簡(jiǎn)單，從具體輸入入手：
add(3，2)=succ(add(3，1))=succ(succ(add(3，0)))=succ(succ(3))
似乎只需要組合多個(gè)后繼函數(shù)就可以了呢。
當(dāng)然，這里面有一個(gè)毛病，在于我們?cè)跊](méi)有定義好add的前提下，先入為主地認(rèn)為add(3，0)=3.
所以我們不能認(rèn)為自己就這么簡(jiǎn)單地構(gòu)造了add，只能退而求其次地得到以下關(guān)系：
add(x，y+1)=succ(add(x，y))，這個(gè)式子是十分嚴(yán)謹(jǐn)?shù)摹?/p>
更具體地，要想算出add(x，y+1)，就要知道add(x，0)=x，我們稱add(x，0)=x為基準(zhǔn)條件；add(x，y+1)=succ(add(x，y))為遞歸條件。
看起來(lái)就差臨門(mén)一腳了，只要我們能用三種基本函數(shù)構(gòu)造出add(x，0)=x，就能得到add(x，y+1)，也就能構(gòu)造出我們想要的加法器。
也很顯然，add(x，0)=x=proj11
于是，我們的加法器有了。
這種看起來(lái)很像左腳踩右腳登天的構(gòu)造方式叫做“原始遞歸”，它的定義是這樣的：
基準(zhǔn)函數(shù)f:N^n—N
遞歸函數(shù)g:N^n+2—N
使用f和g的原始遞歸h=ρ^n(f，g):N^n+1—N
對(duì)于h:
基準(zhǔn)條件：h(x1，...xn，0)=f(x1，...，xn)
遞歸條件:h(x1，...，xn，y+1)=g(x1，...，xn，y，h(x1，...，xn，y))
回到我們的加法器add：
add:N^2→N
add(x，y)=x+y=ρ^1(f，g)
基準(zhǔn)條件：add(x，0)=f(x)=proj11
遞歸條件：add(x，y+1)=g(x，y，add(x，y))=succ(add(x，y))，g=succ·[proj33]
add=ρ^1(proj11，succ·[proj33]）
完美無(wú)瑕。
類似地，乘法器mult=ρ^1(zero，add·[proj13，proj33])
前繼函數(shù)，減法器等等基本運(yùn)算都可以據(jù)此定義，只需要proj，zero，succ三種原始函數(shù)和組合·，原始遞歸ρ這兩種基本操作。所有完全函數(shù)都可以據(jù)此構(gòu)造。
那么“偏函數(shù)”呢？
構(gòu)造偏函數(shù)還需要額外的一個(gè)操作：最小化。
如果我們有一個(gè)函數(shù)f:N^n+1—N(這里^代表上標(biāo)，雖然不好看，但實(shí)在是敲得太麻煩沒(méi)有耐心了)，具體的f(a1，...an，x)，其中a1，...an是固定參數(shù)，x是可變參數(shù)。
那么最小化操作為：μ^nf:N^n—N它會(huì)找到給它輸入的n個(gè)參數(shù)里，最小的一個(gè)，并輸出
比如f(5，4，3，2，1，0)=0
如果遇到重復(fù)參數(shù)，那么就輸出第一個(gè)最小的。
比如f(5，4，3，2，1，1)=1
假設(shè)我們有一個(gè)投影函數(shù)長(zhǎng)這樣：
proj21:N^2—N(proj21中的2是上標(biāo)，1是下標(biāo)，下同，寫(xiě)不動(dòng)擺爛了)
那么μ^1proj21:N—N
舉個(gè)栗子：
假如我們給proj21弄一個(gè)最小化操作：μ^1proj21(1)，其中1是固定參數(shù)。
如果我們窮舉一下可變參數(shù)，就會(huì)發(fā)現(xiàn)：
proj21(1，0)=1
proj21(1，1)=1
我們永遠(yuǎn)也拿不到0，也就不存在最小化。也就是說(shuō)，對(duì)于μ^1proj21而言，并不是每一個(gè)輸入都對(duì)應(yīng)一個(gè)輸出，所以應(yīng)用最小化操作，我們成功地構(gòu)建了一個(gè)偏函數(shù)。
加減乘三種操作都在上文構(gòu)建過(guò)了，現(xiàn)在就只剩下一個(gè)除了。除法div需要用最小化操作來(lái)構(gòu)建。
假設(shè)，我們收到兩參數(shù)a和b，想求a/b，那么其中存在如下關(guān)系：
a=q×b+r，其中0≤r＜b
我們想要的就是滿足式子q×b≤a的最大的q，這等同于滿足(q+1)×b＞a，于是帶余除法被轉(zhuǎn)化為了一個(gè)最小化問(wèn)題：
找到最小的q使其滿足(q+1)×b＞a
也就是構(gòu)造一個(gè)函數(shù)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]
其中l(wèi)essthanequal=iszero·sub
iszero=sub·[succ·zero，proj11]
sub是減法器
對(duì)f進(jìn)行最小化操作即可得到我們想要的結(jié)果。
驗(yàn)證一下：
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沒(méi)錯(cuò)，十分完美。
如果我們想計(jì)算一下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不是輸出。
無(wú)論我們給f(8，0，x)傳入什么x，都找不到最小的x，所以div(8，0)=8//0無(wú)解，符合現(xiàn)實(shí)。
如果把最小化操作運(yùn)用在原始遞歸函數(shù)上，得到的新函數(shù)就叫做偏遞歸函數(shù)。
好了，現(xiàn)在加減乘除我們都有了，只要是可計(jì)算的算法，我們都能執(zhí)行。
至于無(wú)限循環(huán)怎么制造出來(lái)，從μ^1proj21(1)和div的栗子都可以看出來(lái)，如果最小化操作找不到最小值，就永遠(yuǎn)不會(huì)給出輸出，這相當(dāng)于while語(yǔ)句的功能。
——————————————————
下一章是正常內(nèi)容