UA MATH577 逻辑与可计算性1 递归函数
UA MATH577 邏輯與可計算性1 遞歸函數
- 三種基礎函數
- 三類創造可計算的新函數的方法
- 復合函數
- Primitive Recursive
- Minimization
寫在前面
這個系列是我上課的筆記,這個課是Jan Wehr老教授的Logic and Computation,用的教材是Boolos,Burgess,Jeffrey的Computability and Logic。Jan的研究領域是隨機微分方程和數學物理,對具體的算法并不熟悉,再加上這是一個topic course,不是regular course,所以不會嚴格按照教材的敘述進行。這個課程的主要目標是闡述Goedel不完備定理的證明,為此需要先引入三種可計算性的定義:Turing機與Turing可計算性、Abacus可計算性與遞歸可計算性,以及兩套形式邏輯系統:一階邏輯與二階邏輯。在完成這個主要目標后,會介紹一些計算理論的其他專題,比如算法復雜性、P/NP問題等。
我們先從遞歸可計算性開始,這一講介紹遞歸函數。第一個概念是effectively computable function,這類函數指的是有明確的計算規則、表達式的函數,既然計算規則都可以明確寫出來,那么這類函數當然是可計算的。基于這種函數定義可計算性的話就太狹隘了,因為并不是所有不能寫出表達式、計算規則的函數都是不能計算的。所以Church用遞歸的思想擴展了effectively computable function的概念,定義遞歸函數(recursive function),這是遞歸可計算性(recursive computability)的基礎。Church是Turing的老師,他們二人是計算理論最重要的奠基人。下面我們介紹Church定義遞歸函數的思路。
三種基礎函數
Church在定義遞歸函數的時候,首先定義了三種基礎函數。
第一個基礎函數是zero function,記為z(x)z(x)z(x),不論什么輸入x∈N∪{0}x \in \mathbb{N} \cup \{0\}x∈N∪{0},輸出都是0,即
z(x)=0,?xz(x)=0,\forall xz(x)=0,?x
需要注意的是這里的自然數公理體系是Peano公理下的自然數的序數理論體系。自然數有兩種公理系統,基數理論與序數理論。
第二個基礎函數是successor function,記為s(x)s(x)s(x),
s(x)=x+,?x∈N∪{0}s(x)=x^+,\forall x \in \mathbb{N} \cup \{0\}s(x)=x+,?x∈N∪{0}
上標+^++的含義是后繼,這是Peano公理引入的一個運算,它表示某個自然數的下一個自然數,比如1+=21^+=21+=2,2+=32^+=32+=3,但函數s(x)s(x)s(x)的定義域是自然數集加0,所以我們額外再定義0+=10^+=10+=1。
第三個基礎函數是identity function,記為idinid^n_iidin?,它滿足
idin(x1,?,xn)=xiid^n_i(x_1,\cdots,x_n)=x_iidin?(x1?,?,xn?)=xi?
這個函數也叫projection function;這三個函數叫基礎函數,因為他們都只需要一次運算就能得到結果。
三類創造可計算的新函數的方法
上面三種基礎函數的作用是與現在要介紹的函數操作一起用于擴展effectively computable function。
復合函數
復合是我們非常熟悉的函數操作,它可以用我們熟悉的函數合成新的函數。如果用effectively computable function通過復合組成新的函數,那么新的函數也是可計算的。我們用下面的記號表示復合,
h=Cn[f,g1,?,gm]h=Cn[f,g_1,\cdots,g_m]h=Cn[f,g1?,?,gm?]
它的含義是
h(x1,?,xn)=f(g1(x1,?,xn),?,gm(x1,?,xn))h(x_1,\cdots,x_n)=f(g_1(x_1,\cdots,x_n),\cdots,g_m(x_1,\cdots,x_n))h(x1?,?,xn?)=f(g1?(x1?,?,xn?),?,gm?(x1?,?,xn?))
例1 常值函數
用constn(x)=nconst_n(x)=nconstn?(x)=n表示常值函數,它把任意輸入xxx映射為nnn,我們可以用復合的思路說明所有常值函數是可計算的:
const0=zconst1=Cn[s,z]?constn+1=Cn[s,constn]const_0=z \\ const_1 = Cn[s,z] \\ \cdots \\ const_{n+1} = Cn[s,const_n]const0?=zconst1?=Cn[s,z]?constn+1?=Cn[s,constn?]
第一個等式非常直接,我們驗證一下第二個等式,
Cn[s,z]=s(z)=s(0)=0+=1C_n[s,z]=s(z)=s(0)=0^+=1Cn?[s,z]=s(z)=s(0)=0+=1
我們驗證一下最后一個等式,
Cn[s,constn]=s(constn)=n+=n+1Cn[s,const_n]=s(const_n)=n^+=n+1Cn[s,constn?]=s(constn?)=n+=n+1
于是通過復合的手段,我們可以用基礎函數說明常值函數可計算。
Primitive Recursive
Primitive Recursion指的是下面的遞歸過程:
h(x,0)=f(x)h(x,y+)=g(x,y,h(x,y))h(x,0)=f(x) \\ h(x,y^+)=g(x,y,h(x,y))h(x,0)=f(x)h(x,y+)=g(x,y,h(x,y))
我們記h=Pr[f,g]h=Pr[f,g]h=Pr[f,g]。可以用Primitive Recursive得到和、積、階乘等運算:
例2 Primitive Recursive的應用
證明
1、在序數理論中,定義加法的思路是引入兩個方程:a+1=a+,a+b+=(a+b)+a+1=a^+,a+b^+=(a+b)^+a+1=a+,a+b+=(a+b)+,這里的自然數包含了0,因此定義加法需要a+0=a,a+b+=(a+b)+a+0=a,a+b^+=(a+b)^+a+0=a,a+b+=(a+b)+,所以要驗證第一個等式只需要驗證加法對這兩個等式成立:
a+0=sum(a,0)=id11(a)=aa+b+=sum(a,b+)=Cn[s,id33](a,b,sum(a,b))=s(id33(a,b,sum(a,b)))=s(sum(a,b))=s(a+b)=(a+b)+a+0=sum(a,0)=id_1^1(a)=a \\ a+b^+=sum(a,b^+)=Cn[s,id_3^3](a,b,sum(a,b)) \\=s(id_3^3(a,b,sum(a,b))) =s(sum(a,b))=s(a+b)=(a+b)^+a+0=sum(a,0)=id11?(a)=aa+b+=sum(a,b+)=Cn[s,id33?](a,b,sum(a,b))=s(id33?(a,b,sum(a,b)))=s(sum(a,b))=s(a+b)=(a+b)+
2、在敘述理論中,定義乘法的思路是引入兩個方程:a?1=a,a?b+=a?b+aa \cdot 1=a,a \cdot b^+=a \cdot b+aa?1=a,a?b+=a?b+a,這里的自然數包含了0,所以我們需要額外說明a?0=0a \cdot 0=0a?0=0,所以要驗證第二個等式只需要說明它滿足這三個方程:
a?0=prod(a,0)=z(a)=0a?1=prod(a,1)=Cn[sum,id13,id33](a,0,prod(a,0))=Cn[sum,id13,id33](a,0,0)=sum(id13(a,0,0),id33(a,0,0))=sum(a,0)=aa?b+=prod(a,b+)=Cn[sum,id13,id33](a,b,prod(a,b))=sum(id13(a,b,prod(a,b)),id33(a,b,prod(a,b)))=sum(a,prod(a,b))=a+a?ba \cdot 0=prod(a,0)=z(a)=0 \\ a \cdot 1 = prod(a,1)=Cn[sum,id^3_1,id_3^3](a,0,prod(a,0)) \\ = Cn[sum,id^3_1,id_3^3](a,0,0)=sum(id_1^3(a,0,0),id_3^3(a,0,0)) \\ = sum(a,0)=a \\ a \cdot b^+ = prod(a,b^+)=Cn[sum,id^3_1,id_3^3](a,b,prod(a,b)) \\ = sum(id_1^3(a,b,prod(a,b)),id_3^3(a,b,prod(a,b))) \\ = sum(a,prod(a,b))=a+a \cdot ba?0=prod(a,0)=z(a)=0a?1=prod(a,1)=Cn[sum,id13?,id33?](a,0,prod(a,0))=Cn[sum,id13?,id33?](a,0,0)=sum(id13?(a,0,0),id33?(a,0,0))=sum(a,0)=aa?b+=prod(a,b+)=Cn[sum,id13?,id33?](a,b,prod(a,b))=sum(id13?(a,b,prod(a,b)),id33?(a,b,prod(a,b)))=sum(a,prod(a,b))=a+a?b
階乘的構造就留給讀者自行證明了,需要只需要按定義說明:
0!=fac(0)=1n!=fac(n)=n?(n?1)!0!=fac(0)=1 \\ n! = fac(n)=n \cdot (n-1)!0!=fac(0)=1n!=fac(n)=n?(n?1)!
即可。
Minimization
Minimization的作用是減少輸入的個數,假設fff是一個有n+1n+1n+1個輸入的函數,記h=Mn[f]h=Mn[f]h=Mn[f],其中
h(x1,?,xn)={y,iff(x1,?,xn,y)=0or?t<y,?f(x1,?,xn,t)≠0undefined,ifnosuchyh(x_1,\cdots,x_n)=\begin{cases} y,\ if\ f(x_1,\cdots,x_n,y)=0\ or\\ \forall t<y,\exists f(x_1,\cdots,x_n,t) \ne 0 \\ \\ undefined,\ if \ no\ such\ y \end{cases}h(x1?,?,xn?)=??????????y,?if?f(x1?,?,xn?,y)=0?or?t<y,?f(x1?,?,xn?,t)?=0undefined,?if?no?such?y?
如果fff可計算,那么hhh是可計算的。
總結
以上是生活随笔為你收集整理的UA MATH577 逻辑与可计算性1 递归函数的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: R语言数据可视化 ggplot2基础1
- 下一篇: 偏微分方程I PDE的例子1 一维波动与