资源描述：
《 计算复杂性理论总结报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算复杂性理论总结报告一、图灵机（1）图灵机基本模型图灵机是由图灵（AlanMathisomTuring）在1936年提出的，它是一个通用的计算模型。通过图灵机，来研究递归可枚举集和部分递归函数，对算法和可计算性进行研究提供了形式化描述工具。图灵机的基本模型包括一个有穷控制器，一条含有无数个带方格的输入带和一个读写头。其直观物理模型如下图1所示。基本图灵动作有以下三种：（1）改写被扫描带方格内容，控制器转化为下一状态。（2）读写头向左移一个带方格，控制器转化为下一状态。（3）读写头向左移一个带方格，控制器转化为下一状态。图1图灵机（2）图灵机形式化定义，图灵机演算过程及语言描述定义：一个
2、基本图灵机定义为一个七元组TM={Q,C,δ,A,B,q1,F}。其中Q是状态集合，（图灵机所有的状态）非空有限集；C是带符号表，（放在带方格中的符号集合）非空集；δ是控制函数或过程转换函数（定义控制器）δ：QxCàQxC∪（R,L）；A是输入字母表，A⊆C；B是空白符，B∈C；q1是初始状态，q1∈Q；F是终态集，F⊆Q.TM的扫描符号串主要由δ来确定：（1）δ（q，s）=（q’,s’）;（2）δ（q，s）=(q’,R);（3）δ（q，s）=(q’,L);（4）δ（q，s）无效，对应无定义时图灵机终止。TM的工作用“格局”的转换来描述。格局：σ：a1a2a3…aj-1qajaj+1…其
3、中q∈Q，ai∈C；（1）若δ（q，ai）无定义，称σ为停机格局；（1）若q∈F，称σ为接受格局；（2）若q为初始状态，称σ为初始格局；格局σ到格局τ的转换σ├mτ若成立σ=σ1├m1σ2├m2σ…3├Mσk记为σ1├*σk（k>=0）（1）图灵机其他形式（1）五元机δ：QxCàQxCx{R,L}基本动作：qsq’s’即δ（q，s）=（q’,s’）；qsq’L即δ（q，s）=（q’,L）；qsq’R即δ（q，s）=（q’,R）。基本图灵机又称四元机，五元机是指把基本四元机的动作合并：qsq’Ls’即δ（q，s）=（q’,s’,L）；qsq’Rs’即δ（q，s）=（q’,s’,R）。定义基
4、本动作不同（2）单向无穷图灵机由单带单向所限制，必须δ（q0，#）=（q1,R）；δ（q0，#）=（q1,L）无意义，不存在。（3）多带图灵机δ：QxCàQxC1xC2xC3…Cnx{R,L}有多个读写头，一个控制器图2多带图灵机（4）离线图灵机离线图灵机是多带的，同时将带方格分为输入带和工作带，其中输入带始终不变，工作带是中间过程带。（2）各种图灵机之间关系定理：四元图灵机与五元图灵机是等价的。定理：单向图灵机与四元机是等价的。定理：多带图灵机与单带图灵机是等价的。定理：离线图灵机与单带图灵机是等价。总结：图灵机都是等价的。一、不可判定问题及相关结论，会图灵机停机问题，文法不可判定问题
5、判定问题主要讨论带参数的判定问题，比如X∈N，问X是素数吗？设判定问题π，使π为真的实例的集合为Yπ，实例的全体集合为Dπ，这样一个判定问题就可以这样描述π=（Dπ，Yπ）。例如：π=（N,P），如何处理？通过二元组编码和谓词对应来讨论。通过编码建立判定问题与谓词的对应关系设编码为e，Dπ—>A*(谓词)。对于I∈Dπ，Dπ（I）<=>I∈Yπ，其中e（I）=x对于同一个判定问题，其编码e1与e2得谓词P1与P2，根据chuuring-Turing命题，若e1与e2是可计算的，则有可计算函数f1:A*—>A*;f2:A*—>A*使得P1(x)<=>P2(X)P2(X)<=>P1(x)。定
6、义：如果谓词π是可计算的，则称判定问题是可判定的，否则是不可判定的。定义：设π1与π2两个判定问题，若有函数f：Dπ1—>Dπ2满足：（1）f是可计算的；（2）对于每个实例I∈Dπ1总有I∈Yπ<=>f（I）∈Yπ2则称f为判定问题π1到π2的规约。定理：设判定问题π1可规约为判定问题π2，则（1）π2是可判定的，蕴含π1是可判定的；（2）π2是不可判定的，蕴含π1是不可判定的。二、正则语言（1）chomsky文法分类文法的chomsky语言定义如下：文法为四元组G=（V，T，P，δ）其中，V为非终结符集合，T为终结符集合，P为规则集，δ为开始符号(1)0型文法对于规则不做任何限制，又称
7、关于结构文法，还称无限制文法(2)1型文法又称上下文有关文法，记为CSG。要求规则α—>β满足：
8、α
9、≤
10、β
11、，所形成的语言叫1型语言。(3)2型文法又称上下文无关文法，记为CFGA—>α其中A∈V，α∈（V∪T）*(2)若文法满足A—>aB或A—>w,其中A，B∈V，w∈A*，则称此种文法为右线型文法；若A—>Ba，A—>A—>w,其中A，B∈V，w∈A*,则称此种文法为左线型文法，或称为正则文法。举例：GS—>aA，A—>aA，
