数媒1204陈志伟1030512402计算理论论文

《数媒1204陈志伟1030512402计算理论论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、我对计算复杂性的一些理解（论文）——数媒1204陈志伟指导老师：张军一、浅谈图灵机1、图灵机基本模型基本图灵机有一条带作为存储装置和一个控制器，控制器带一个读写头（又叫做带头）。带的两端是无穷的，被划分成无穷多个小方格，每个小方格内可以存放一个符号，控制器有有穷个状态。在计算的每一步，控制器总处于某个状态，读写头可左移或右移扫描一个方格，根据控制器当前所处的状态和读写头扫描的方格内的符号。控制器完成下列三个动作中的其中一个：1.改写被扫描方格的内容，控制器转换到一个新的状态；2.读写头向左移动一格，控制器转换到

2、一个新的状态；3.读写头向右移动一格，控制器转换到一个新状态；结构如图所示：左右无穷的带读写头控制器2、图灵机形式化定义，图灵机的接受过程及接受语言过程定义：一个基本图灵机M定义为一个七元组TM={Q,C,δ,A,B,q1,F}。Q是状态集，一个非空有穷集合，标示图灵机的所有状态；C是带字母表，（放在带方格中的符号集合）非空有穷集；δ是动作函数，包括控制函数或过程转换函数（定义控制器），是QxCàQxC∪（R,L）的部分函数；A是输入字母表，A⊆C-{B}；B是空白符，B∈C；q1是初始状态，q1∈Q；F是接收

3、状态集，F⊆Q，F中的元素叫做接收状态图灵机的每一步计算由动作函数δ确定，设当前状态q,被扫描的符号为sδ（q，s）=（q’,s’），把被扫描的方格的内容改写成s’并且转换到状态q’，读写头的位置保持不变。δ（q，s）=(q’,R)，读写头左移一格并且转换到状态q’，带的内容保持不变。δ（q，s）=(q’,L)，读写头右移一格并且转换到状态q’，带的内容保持不变。δ（q，s）无定义，则停止计算。图灵机的格局包括带的内容、读写头的位置和控制器的状态，可表示成σ：a1a2a3…aj-1qajaj+1…其中q∈Q，a

4、i∈C；它表示的内容是a1a2a3……ak，两端其余部分全是B，读写头正在扫描aj，控制器处于状态q。如果δ（q，aj）↑，则称这个格局是停机格局。如果停机格局中的状态是接收状态，则称这个格局是接受格局。定义图灵机接受过程：如果从初试格局q1Bx开始计算，图灵机最终停机在接受格局，则称图灵机接收x。图灵机接收的所有字符串组成的集合称作图灵机接收的语言，或图灵机识别的语言。3、图灵机其他形式（1）五元图灵机五元图灵机的一步要做四元图灵机两步做的事情，改写一个符号并且左移一格，或者改写一个符号并且右移一格。（2）单

5、向无穷带图灵机单项无穷带图灵机的带仅在一个方向上是无穷的，有一个最左方格#被固定在带的左端，他左边的方格永远不会被使用。（3）多带图灵机多带图灵机有k个读写头，没个读写头扫描一条带，可以改写被扫描方格内的符号、左移一格或者右移一格。读写头的动作由当前的状态和k个读写头从k条带上读到的k个符号决定。（4）离线图灵机离线图灵机有一条输入带和k条工作带，输入带的带头只读不写，工作带的带头是和普通多带图灵机一样的读写头。#$分别表示输入带的左端和右端。4、各种图灵机之间关系定理：四元图灵机与五元图灵机是等价的。定理：单

6、向图灵机与四元机是等价的。定理：多带图灵机与单带图灵机是等价的。定理：离线图灵机与单带图灵机是等价。总结：图灵机都是等价的。二、不可判定问题及相关结论，图灵机停机判定问题，文法不可判定问题1、不可判定问题及结论设判定问题π，使π为真的实例的集合为Yπ，实例的全体集合为Dπ，这样一个判定问题就可以这样描述π=（Dπ，Yπ）。通过二元组编码和谓词对应来讨论。通过编码建立判定问题与谓词的对应关系设编码为e，Dπ—>A*(谓词)。对于I∈Dπ，Dπ（I）<=>I∈Yπ，其中e（I）=x对于同一个判定问题，其编码e1与e

7、2得谓词P1与P2，根据chuuring-Turing命题，若e1与e2是可计算的，则有可计算函数f1:A*—>A*;f2:A*—>A*使得P1(x)<=>P2(X)P2(X)<=>P1(x)。定义：如果谓词π是可计算的，则称判定问题是可判定的，如果谓词π是半可判定的，则称判定问题是半可判定的，否则是不可判定的。定义：设π1与π2两个判定问题，若有函数f：Dπ1—>Dπ2满足：(1)f是可计算的；(2)对于每个实例I∈Dπ1总有I∈Yπ<=>f（I）∈Yπ2则称f为判定问题π1到π2的规约。定理：设判定问题π1

8、可规约为判定问题π2，则π2是可判定的，蕴含π1是可判定的；π2是不可判定的，蕴含π1是不可判定的。（1）图灵机停机判定问题定义：图灵机的停机问题——任给图灵机和格局σ，从格局σ开始，图灵机是否最终停机？定理：图灵机的停机问题是不可判定的。（2）文法不可判定问题引理：如果u∈L(M),则L()={},如果u不属于L(M),则L()=空集定理：下述问题是不可判定的：任给一个文法G，是否L