Document

Report
数理逻辑 (6)
递归论
什么是计算?
一般递归函数显然被认为是可计算的。
丘奇
1903-1995,美国
λ-演算。
定理:一个函数是λ-可计算的当且仅当它是递归的。
丘奇论题:一个函数是可计算的当且仅当它是λ-可计算的。
图灵
1912-1954,英国
图灵机:
• 双边无穷的工作带(tape),磁带上或者
是空(B),或者是0,或者是1(令S={B,0,1});
• 读头;
• 有限状态集(states)Q={q0,…,qn}。
图灵机的运行:
• 从一个状态到另一个状态;
• 从一个符号扫描到另外一个符号;
• 左右移动读头。
一条指令是一个5元组Q×S×Q×S×{R,L}。
一个程序就是一个有限指令集。
图灵机的运行
图灵机的输入:工作带初始状态。
计算的开始:初始状态q1并且读头扫描到1。
图灵机的停机:到达状态q0。
图灵机的输出:停机后的工作带上1的个数。
约定:当输入数字x时,工作带上出现x+1个连续的1。
几个例子
程序{(q1,1,q1,1,R), (q1,B,q2,1,R), (q2,B,q0,1,R)}计算x+3。
程序{(q1,1,q2,0,R), (q2,1,q3,1,R), (q3,1,q3,1,R), (q3,B,q3,1,R),
(q2,B,q0,0,R)}算一个函数f使得f在x定义当且仅当x=0并且输出0。
丘奇-图灵论题
一个函数f是图灵可计算的,如果存在一台图灵机使得当输入x时,输出是
f(x)。
定理:一个函数是图灵可计算的当且仅当它是递归的。
丘奇-图灵论题:一个函数是可计算的当且仅当它是图灵可计算的。
可计算性
• f是(部分)可计算的如果存在一台图灵机使得对于所有的输入x,它的
输出(如果有)是f(x)。
• 一个自然数集合是可计算的当且仅当它的特征函数是可计算的。
• 一个自然数集合是可计算可枚举的,如果它是某个部分可计算函数的值
域。
定理:每一个可计算集合都是可计算可枚举的。
图灵机的枚举
令#(B)=1,#(0)=2,#(1)=3,#(R)=4,#(L)=5,#(qi)=6+qi。
通过<>将一个程序编码为一个自然数。因此我们有一个扩展的函数#从ω
到程序集合。
通过这个函数我们获得图灵机的一个枚举{Me}e∈ω。
这是一个能行的枚举:函数p(<e,n>)=Me(n)是部分可计算的。
因此存在一台通用的图灵机U。
c.e.集的能行枚举{We}
e∈ω。
停机问题
因此我们有一台通用图灵机U(<e,n>)=Me(n)。
令K={e|U(<e,e>)停机}。
定理:K是可计算可枚举的但不是可计算的。
证明:显然K是可计算可枚举的。
假设K是可计算的。令f(e)为一个函数使得如果e∈K,那么f(e)=Me(e)+1,
否则f(e)=0。则f是可计算的,因此它有一个编码e。那么f(e)=Me(e)+1,
矛盾!
QED
正则定理
对于每一个部分可计算函数φ,都存在一个完全可计算函数f,g使得
φ(n)=f(μ(m)(g(n,m)=1))。
证明:给定一个部分可计算函数φ,令
g(n,<i,j>)=0如果φ(n) 运行到第j步时不等于i。否则g(n,<i,j>)=1。
令f(<i,j>)=i。
QED
s-m-n定理
定理:对于任何部分可计算函数φe(x0,…,xm,y0,…,yn),
存在一个完全递归可计算函数s使得
φe(x0,…,xm,y0,…,yn)=φs(e,y0,…,yn)(x0,…,xm)。
证明:对于y0,…,yn,我们可以能行地找到编码为
s(e,y0,…,yn)的图灵机计算x0,…,xm。 QED
填充引理
• (padding引理)定理:对于每一个部分可计算函数φ,
存在一个完全的1-1的可计算函数f使得对于所有的e,
φ=φf(e)。
• 证明:固定一台图灵机M计算φ,我们对M加入一些
“空语句”。于是我们能行地获得了一系列图灵机它
们计算同一个函数φ。
QED
可计算可枚举(c.e.)集
定理:一个集合是可计算可枚举的当且仅当它是某个可
计算函数的值域。
证明:如果A是某个φ的定义域。假定A非空,固定A的
一个元素x。定义f(s)=n,如果φ(n)在第s步有定义。
否则f(s)=x。
QED
定理:一个无穷集合是可计算当且仅当它和它的补集都
是c.e 当且仅当它是某个严格单调可计算函数的值域。
可计算可枚举集(2)
定理:每一个无穷c.e.集合都有一个无穷的可计算子集。
定理:一个无穷集合是c.e.当且仅当它是某个1-1可计
算函数的值域。
定理:一个集合是c.e.当且仅当它可以被一个公式Σ1
公式定义。
如果#(T)={#(φ)|φ∈T}是c.e.,则{#(φ)|T┠φ}也
是c.e.
极限引理
定理:一个函数f(n)是Δ02的当且仅当存在一个可计算
函数g(n,s)使得f(n)=limn->∞g(n,s)。
模型不可判定性
定理:{#(φ)|(ω,+,×,<,0,1)ㅑφ}不
是可计算的。
证明:n∈K可以被一个公式Σ1公式φ(n)定义。QED
给定一个语言L以及一个被编码的可数结构M,我们称
一个公式φ是可判定的,如果{#(m)|Mㅑφ(m)}
是可计算的。
希尔伯特第十问题
定理:{#(p)|p是整系数多项式并且(Z,+,,<,0,1) ㅑ
n0… ni(p(n0,…,ni)=0)}是不可计算的。
语法不可判定性
由表示定理,如果n∈K,则PA┠φ(n)。
如果PA是ω-协调的,则PA┠φ(n)蕴含n∈K。
因为{#(φ(n))|n∈ω}是可计算的。因此{#(ψ)
|PA┠ψ}不是可计算的。
因为K不是可计算的,必定存在一个m∉K,使得¬φ(m)是
不可证的。如果PA是ω-协调的,则φ(m)也是不可证
的。
归约
A多一归约于B(≤m),如果存在一个可计算函数f使得对
于所有的n,n∈A当且仅当f(n) ∈B。
如果f是单射,则A-一归约于B(≤1)。
这些关系是传递等,因此我们可以定义一个等价类,每
一个等价类我们称为一个度。
定理:可计算集合与c.e.集合的m-度是向下封闭的。
对于所有的集合A,B, A⊕B={2n|n∈A}∪
{2n+1|n∈B}是它们的m-度最小上界。
停机问题
定理:对于所有的c.e.集A,A≤1K。
证明:A是某个φe的定义域,定义部分可计算函数
p(<e,n>,m)=φe(n),则存在某个可计算函数s使得
φs(<e,n>)(m)=φe(n)。令f(n)=s(<e,n>)。由填充引理,
我们可以让f为单射。
QED
递归定理
递归定理:对于所有的可计算函数f,存在一个e 使得
φe=φf(e)。
证明:令p(u)=φu(u)。则由s-m-n定理存在一个完全可计算
函数d使得φd(u)=φp(u)。因此存在一个v使得φv=fd)。
令e=d(v),于是φe=φd(v)=φp(v)=φf(d(v))=φf(e)。 QED
递归定理的应用
(Quine)定理:存在一个打印自己的程序。
证明:存在一个递归函数f使得对所有的n,φf(e)(n)=e。由递
归定理,存在e使得φe的输出是φe的程序代码。 QED
递归不可分离(1)
定义:给定两个不相交的自然数集合A,B,如果不存在递归集合C使
得C⊇A并且C∩B=Ø,则它们称为递归不可分离的。
令K0={n|ϕn(n)=0}, K1={n|ϕn(n)=1}。则K0, K1是不相交的c.e.集。
定理:K0, K1是递归不可分离的。
证明:如果存在递归集合C分离K0, K1,则对于某个e, χC=ϕe。如果
ϕe(e)=0,则e∈K0。否则e∈K1。矛盾!
QED
递归不可分离(2)
定义:给定两个不相交的自然数集合A,B,如果存在一个可计算函
数f(i,j)使得对于任何不相交的Wi ⊇A, Wj ⊇B, f(i,j) ∉Wi∪Wj。
则A,B称为能行递归不可分离的。
定理:K0, K1是能行递归不可分离的。
证明:如果令φs(e,i,j)(n)=0,n∈Wj; φs(e,i,j)(n)=1,n∈Wi; φe(n)
无定义,否则。f(i,j)=s(e,i,j).
QED
产生集与创造集
定义:一个集合A是产生的,如果存在一个部分可计算函数p使得对
于所有的A⊇Wx,p(x) ∈A-Wx。
定义:一个c.e.集合A是创造的,如果它的补集是产生的。
如果c.e.集合A,B是能行递归不可分离的,则A是创造的。
定理:p可以是可计算的单射。
证明:存在一个可计算函数g使得Wg(x)=Wx,如果p(x)收敛;否则
Wg(x)=Ø。令q(x)=p(x)或者p(g(x)),依赖于哪个先收敛。则q是
可计算的。令h使得Wh(x)=Wx∪{q(x)}。令r(0)=q(0),r(x+1)为序
列q(x+1),…,q(h(n)(x+1)),…中第一个不与前面r重复的或者重
复的。后者必然Wx+1不是A的子集。
产生集与创造集(2)
定理:如果A是创造集,则K≤mA。
证明:假定P=ω-A是产生的。令f为相应的可计算单射。令
Wg(x,y)={f(x)},如果y∈K;否则Wg(x,y)=Ø。由递归定理,存在一个
可计算函数h使得对所有y,Wg(h(y),y))=Wh(y)。则y∈K蕴含
Wh(y)={f(h(y))}蕴含f(h(y)) ∈A;否则Wh(y) =Ø,因此f(h(y))
∈P。 QED
哥德尔-罗瑟不完备性
令R0(n,y)为可计算关系使得n∈K0当且仅当yR0(n,y)。
同样对于R1(n,y)。
令S0(n)为yR0(n,y) ∧ z≤y¬R1(n,z)。
同样对S1(n)。
则S0(n)蕴含PA证明S0(n)。同样对于S1(n)。
(*)而且PA证明S0(n)蕴含PA证明¬S1(n)。
由(*),c.e.集D0={n|PA证明S1(n)} ⊇K1并且D1={n|PA证明¬S1(n)} ⊇K0。
由协调性, D0∩D1=Ø。因此必然有一个n使得n∉D0∪D1。
则S1(n)独立于PA。
进一步,D0, D1是能行递归不可分离的。
PA的复杂性
定理:K≤mD0。
证明:由能行递归不可分离性, D0是创造的。
QED
因此{#(φ)|PA┠φ}是c.e.集中m-度最大的。
波斯特
1897-1954, USA
"The conclusion is unescapable that even for such a fixed,
well defined body of mathematical propositions,
mathematical thinking is, and must remain, essentialy
creative."
带谕示的图灵机
带谕示(Oracle)的图灵机。
如果图灵机M的谕示是A,则用MA表示。
如果B的特征函数能被某台MA计算,则称B图灵归约于A,记为B≤TA。
A≡TB,如果B≤TA并且A≤TB。
≡T等价类称为一个图灵度。
康托空间
2ω上的基本开集是[σ]={x|σ≺x}, σ∈2<ω。对于每一个基本开
基[σ],它的测度μ([σ])=2-|σ|。
寇尼引理:康托空间是紧致的。
数学刻画
给定一个可计算可枚举集合M⊆2<ω×2<ω,如果对于任何
σ0≺σ1∈2<ω,(σ0,τ0) ∈M并且(σ1,τ1) ∈M,那么τ0≺τ1
或者τ0=τ1,则称M为一个可计算归约函数。
我们称A可计算归约于B,如果存在一个可计算归约函数M使得对于
所有的n,存在一个m,使得(B|m,A|n) ∈M。
定理:A≤TB当且仅当A可计算归约于B。
每个可计算归约可以看成一个部分连续函数的图像。实际上每一个
连续函数都可以看成一个相对化的可计算归约。
图灵度的基本性质
A≤mB蕴含A≤TB。
A≤Tω-A。
所有可计算集合形成一个图灵度0。
有连续统多个图灵度。
每一个图灵度下面至多可数多个图灵度,但是有连续统多个图灵度
在它上面。
记停机问题的图灵度为0’。
相对化
给定集合A,KA={x|x∈WxA}。它的图灵度记为A’。
定理:A≤TB当且仅当KA≤mKB。
证明:如果A≤TB,则KA是B-c.e.。因此KA≤mKB。
如果KA≤mKB,则A和ω-A都是B-c.e.。
QED
低度
定理:存在不可计算的集合A使得A’≤TK。
证明:对角线法。
QED
实数的计算能力
定理:如果μ({B|A≤TB})>0,则A是可计算的。
可计算二叉树
一棵树T是指一个2<ω子集,它在初始段下是封闭的。
如果T是可计算的,则T称为可计算二叉树。
给定一个二叉树T,实数x∈2<ω是一条无穷长道路,如果它的每个
有穷初始段都在T中。
定理:存在可计算的无穷二叉树没有可计算的无穷长道路。
低基定理
定理:对于任意可计算的无穷二叉树T,存在无穷长道路x使得Kx
≤TK。
证明:本质上是力迫法。
QED
完备性的可能的度
定理:存在可计算的无穷二叉树T使得它的每条无穷道路都计算PA
的一个完备扩张
推论:存在PA的一个完备扩张T使得T’ ≤TK。
习题
• 如果A,B是c.e.并且A∪B=ω,那么存在可计算集合C使
得A⊇C并且B⊇ω-C。
• 如果A是创造集,则K≤1A。
• 证明存在一个图灵度集合使得它们在图灵归约下的序
型是ω1。
• 是否存在更长的序型?
• 证明如果T是PA的扩张,则每一个可计算无穷二叉树
都有一条无穷道路图灵归约于T。
阅读材料
• 《Computability》,N.J. Cutland, 1980.
University of Cambridge
• 《Theory of Recursive Functions and Effective
Computability》, Hartley Rogers,1987. The MIT
press.

similar documents