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

　　【寫在8月25日21:03，上下表示例:^上標，_下標，連續兩個數字前一個是上標後一個是下標】

　　硬核程度:☆☆☆☆☆

　　涉及領域:計算理論

　　大標題:三種函數外加三種操作怎樣解決所有可計算問題?為什麽偏遞歸函數可以製造無限循環?

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

　　以下開始:

　　首先，什麽是可計算?

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

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

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

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

　　輸入(6，2)輸出12

　　輸入(0，6)輸出0

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

　　mult:Z^2→Z

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

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

　　div:Z^2—Z

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

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

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

　　零函數:zero:N^n→N，zero()=0。不管給它什麽，它都輸出0.

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

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

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

　　f:N^n—N

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

　　f·[g1，...，gn]:N^m—N

　　展開為:

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

　　舉個栗子:

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

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

　　即:·[zero]=one

　　驗證一下:

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

　　和zero兩個基本函數組成了我們要的one，完美。

　　如果栗子再複雜一點，我們想要一個加法器add，add(x，y)=x+y，怎麽用那三種基本函數組合?

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

　　add(3，2)=(add(3，1))=((add(3，0)))=((3))

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

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

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

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

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

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

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

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

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

　　基準函數f:N^n—N

　　遞歸函數g:N^n+2—N

　　使用f和g的原始遞歸h=ρ^n(f，g):N^n+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:N^2→N

　　add(x，y)=x+y=ρ^1(f，g)

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

　　遞歸條件:add(x，y+1)=g(x，y，add(x，y))=(add(x，y))，g=·[proj33]

　　add=ρ^1(proj11，·[proj33])

　　完美無瑕。

　　類似地，乘法器mult=ρ^1(zero，add·[proj13，proj33])

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

　　那麽“偏函數”呢?

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

　　如果我們有一個函數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:N^2—N (proj21中的2是上標，1是下標，下同，寫不動擺爛了)

　　那麽μ^1proj21:N—N

　　舉個栗子:

　　假如我們給proj21弄一個最小化操作:μ^1proj21(1)，其中1是固定參數。

　　如果我們窮舉一下可變參數，就會發現:

　　proj21(1，0)=1

　　proj21(1，1)=1

　　我們永遠也拿不到0，也就不存在最小化。也就是說，對於μ^1proj21而言，並不是每一個輸入都對應一個輸出，所以應用最小化操作，我們成功地構建了一個偏函數。

　　加減乘三種操作都在上文構建過了，現在就只剩下一個除了。除法div需要用最小化操作來構建。

　　假設，我們收到兩參數a和b，想求a/b，那麽其中存在如下關系:

　　a=q×b+r，其中0≤rb

　　我們想要的就是滿足式子q×b≤a的最大的q，這等同於滿足(q+1)×ba，於是帶余除法被轉化為了一個最小化問題:

　　找到最小的q使其滿足(q+1)×ba

　　也就是構造一個函數f:N^3—N

　　f(a，b，q)=1如果(q+1)b≤a，=0如果(q+1)ba

　　f(a，b，q)=lessthanequal(mult((q)，b)，a)

　　f=lessthaneual·[mult·[·[proj33]，proj32]，proj31]

　　其中lessthanequal=iszero·sub

　　iszero=sub·[·zero， proj11]

　　sub是減法器

　　對f進行最小化操作即可得到我們想要的結果。

　　驗證一下:

　　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沒錯，十分完美。

　　如果我們想計算一下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不是輸出。

　　無論我們給f(8，0，x)傳入什麽x，都找不到最小的x，所以div(8，0)=8//0無解，符合現實。

　　如果把最小化操作運用在原始遞歸函數上，得到的新函數就叫做偏遞歸函數。

　　好了，現在加減乘除我們都有了，只要是可計算的算法，我們都能執行。

　　至於無限循環怎麽製造出來，從μ^1proj21(1)和div的栗子都可以看出來，如果最小化操作找不到最小值，就永遠不會給出輸出，這相當於while語句的功能。

　　——————————————————

　　下一章是正常內容