可计算性与计算复杂性 联系客服

发布时间 : 星期一 文章可计算性与计算复杂性更新完毕开始阅读

第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文档可自由复制编辑