发布时间 : 星期四 文章可计算性与计算复杂性更新完毕开始阅读
第14页 （4）f(x)= [log2x]
字母表∑={1,B,a,b,c } 状态集Q={q1,q2,q3,q4,q4’,q5,q6,q7,q}
算法：十进制数x的二进制位数为[log2x]+1
用a、b分别表示二进制的0和1，在左端从0开始，做加1的二进制加法，高位在右，低位在左 每做一次二进制加法，就用一个c替换一个1
当所有1被c替换时，带上a和b的总数就是[log2x]+1，最后把c改为B，把a和b改为1
q1 1 a q4 写a，开始右移
q4 a R q4
q4 b R q4
q4 c R q4 右移至1改为c，开始左移 q4 1 c q2
q4 B L q4’
q4’ a R q4 x=0，不停机
q2 c L q2 q2 b L q2
q2 a L q2 左移至最左端 q2 B R q3
q3 a b q4 最低位为0，则改为1 q3 b a q5 最低位为1，则向右进位 q5 a R q3 q3 c b q4
q4 B L q6 q6 c B q7 q7 B L q6
q6 b 1 q6 c改为B，a和b改为1 q6 a 1 q6 q6 1 L q6 q6 B R q
word文档可自由复制编辑
第15页 （5）f(x)= [log3(1+x)] 字母表∑={1,B,a,b,c,d } 状态集Q={q0,q1,q2,q3,q3’,q4,q5,q6,q7,q8,q9,q} 算法：类似（4），用a、b、c分别表示三进制的0、1和2
q0 1 L q1
q1 B 1 q2 加1，写a，开始右移 q2 1 a q3
q3 a R q3 q3 b R q3
q3 c R q3 右移至1改为d，开始左移 q3 d R q3 q3 1 d q4
q3 B L q3’
q3’ a R q3 x=0，不停机
q4 d L q4 q4 c L q4
q4 b L q4 左移至最左端 q4 a L q4 q4 B R q5
q5 a b q3 最低位为0，则改为1 q5 b c q3 最低位为1，则改为2 q5 c a q6 最低位为2，则向右进位 q6 a R q5 q5 d b q3
q3 B L q8 q8 d B q9 q9 B L q8
q8 c 1 q8 d改为B，a、b、c改为1 q8 b 1 q8 q8 a 1 q8 q8 1 L q8 q8 B R q
3、用五元组Turing机计算谓词P(x, y)?(3x=2y)的特征函数。
0 ，x/2=y/3 δ(x,y)= 1 ，否则
算法：① 把x前的B改为a，y后的B改为b
② 从x和y中间的B开始扫描，每当x减去两个1，y减去三个1，转③ ③ 重复②，直到下面情况
如果某次扫描x后遇到a且扫描y后遇到b，在带上写一个1；否则，在带上写两个1
word文档可自由复制编辑
第16页
第五章 半可计算性
f(x1,x2,...,xn)↓：f对(x1,x2,...,xn)有定义。 f(x1,x2,...,xn)↑：f对(x1,x2,...,xn)无定义。
半可计算谓词：对于谓词P (x1,x2,...,xn)，如果存在一个部分可计算函数g (x1,x2,...,xn)，使得
P(x1,x2,...,xn)?g (x1,x2,...,xn)↓，则称P为半可计算谓词。
半可计算集合：对于集合S，如果存在一个部分可计算函数g (x1,x2,...,xn)，使得
(x1,x2,...,xn)?S?g (x1,x2,...,xn)↓，则称S为半可计算集合。
X= x1,x2,...,xn
可判定谓词：对于谓词P(X)，如果存在一个算法A，使得对任给X 能在有限步内回答P(X)是否为真，则称P为可判定谓词。
半可判定谓词：对于谓词P(X)，如果存在一个算法A，使得对任给X
如果P(X)为真，则在有限步内回答是，否则不能给出回答，则称P为半可判定谓词。
递归集合：对于集合S，如果存在一个算法A，使得对任给X 能在有限步内回答是否X?S，则称S为递归集合。
递归可枚举集合：对于集合S，如果存在一个算法A，使得对任给X
如果X?S，则在有限步内回答是，否则不能给出回答，则称S为递归可枚举集合。
谓词的可计算性?可判定性，半可计算性?半可判定性 集合的可计算性?递归性，半可计算性?递归可枚举性
定理：若谓词P和Q是半可计算的，则P?Q、P?Q是半可计算的。 若集合S1和S2是半可计算的，则S1S2、S1S2是半可计算的。
若谓词H(v,X)是半可计算的，则(?v)H(v,X)、(?v)?zH(v,X)是半可计算的。
范式定理：H(X)是半可计算谓词，当且仅当存在可计算谓词C(y,X)，使H(X)?(?y)C(y,X)。 Post定理：P(X)是可计算的，当且仅当P(X)和～P(X)半可计算的。
一元谓词K(X)：K(X)??(X,X)?。表示：K(X)为真，当且仅当歌德尔数为X的P-T程序对输入X停机。 定理：K(X)是半可计算的，但不是可计算的。 推论：～K(X)不是半可计算的。
非半可计算
半可计算 K(X)
可计算 ～K(X)
word文档可自由复制编辑 (1) 第17页
图形定理：函数f(x1,x2,...,xn)部分可计算?谓词V=f(x1,x2,...,xn)是半可计算的。
集合WZ：使得歌德尔数为Z的P-T程序停机的所有那些x的集合。 习 题
1. 举出一种运算，可计算谓词对这个运算是不封闭的（说明理由）
半可计算谓词对这个运算是封闭的（不必说明理由）。
①存在量词运算?，对可计算谓词不是封闭的。
设C(y,X)为可计算谓词，对于(?y)C(y,X)逐次对y=0,1,2,...验证C(y,X)是否为真， 若存在y，则过程可终止，否则不终止。故(?y)C(y,X)是半可计算的。 ②存在量词运算?，对半可计算谓词是封闭的。
有定理：若谓词H(v,X)是半可计算的，则(?v)H(v,X)是半可计算的。
2. 举出一个不可计算的全函数。
1 ，若K(X)
f(X)= 其中一元谓词K(X)??(X,X)? 0 ，若～K(X)
(1)word文档可自由复制编辑