计算理论复习题

《计算理论复习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算理论复习题1、什么是图灵机，图灵机的构造技术以及三种描述方式是什么？(1)图灵机：一个图灵机是一个7元组（，，，，，，，），其中都是有穷集合，并且是状态集；是输入字母表，不包括特殊空白符号︼；是字母表，其中：︼；；是起始状态；是接受状态；是拒绝状态，且。(2)构造技术：有限控制器的存储构造TM，检查第一个输入是不是出现在输入的其他地方；多道；查询符号（打标记）；移动：如把一个字符串整体后移;调用子程序。(3)描述方式：形式描述，即详尽地写出图灵机的状态、转移函数等，这是最低、最详细程度的描述；实现描述,这种方法使用日常语言来描述图灵机的运行，如怎么移动读写头，怎么

2、在带上存储数据等，没有给出状态和转移函数的细节；高水平描述，它也是使用日常语言来描述算法，但忽略了实现的模型，不再需要提及机器是怎么管理它的带子或读写头。2、什么是图灵机的格局，图灵可识别，图灵可判定？(1)图灵机计算过程中，当前状态、当前带内容和读写头当前位置组合在一起，称为图灵机的格局，也即是瞬间状态。(2)如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的。(3)如果一个语言能被某一图灵机判定，则称它是图灵可判定的。3、什么是多带图灵机，非确定型图灵机，枚举器，递归可枚举语言？(1)多带图灵机很像普通图灵机，只是有多个带子，每个带子都有自己的读写头，用于读

3、和写。开始时，输入出现在第一个带子上，其它的带子都是空白。转移函数改为允许同时进行读、写和移动读写头，其形式为：δ：QQ此处k是带子的个数。表达式δ（，，，）=（，，，，L，R，，L）指的是：若机器处于状态，读写头1到k所读的符号分别是，，，则转移到状态，写下符号，。，，且按此式所指示的那样移动每个读写头。推论1：每个多带图灵机都有一个与之等价的单带图灵机。推论2：一个语言是图灵可识别的，当且仅当有多带图灵机识别它。(2)非确定型图灵机：非确定型图灵机在计算的任何时刻，机器可以在多种可能性中选择一种继续进行。它的转移函数具有如下形式：δ：QГ(QГ{L，R，S})其计

4、算是一棵树，不同分枝对应着机器不同的可能性。如果计算的某个分枝导致接受状态，则接受该输入。推论1：每个非确定型图灵机都有一个与之等价的确定型图灵机。推论2：一个语言的是图灵可识别的，当且仅当有非确定型的图灵机识别它。推论3：一个语言是可判定的，当且仅当存在非确定型图灵机判定它。(2)枚举器：它是图灵机的一种变形，是带有打印机的图灵机。每当图灵机想在打印序列中增加一个串时，就把串送到打印机。推论：一个语言是图灵可识别的，当且仅当有枚举器枚举它。(3)递归可枚举语言：能够被图灵机识别的语言称为递归可枚举语言。4、什么是丘奇-图灵论题,可判定语言，接受计算历史？(1)丘奇-

5、图灵论题：丘奇使用演算的记号系统定义算法，图灵使用机器定义算法，这两个定义是等价的，算法的非形式概念和精确定义的联系被称为丘奇-图灵论题，即算法的直接概念等于图灵机算法。(2)可判定语言：如果一个语言，存在某图灵机判定它，则称这个语言是图灵可判定的或可判定的。(3)接受计算历史：设M是一个图灵机，是一个串。M在上的一个接受计算历史是一个格局序列，，，其中：是M在上的起始格局，是M的一个接受格局，且每个都是的合法结果。5、判断下列语言是否可判定，证明其中一个？注：(i)有时称为停机问题真正的停机问题是(ii)不是图灵可识别的。(1)可判定(2)可判定(3),,不可判定(

6、4)可判定(5)不可判定(6)不可判定(7)E，REGULAR,，都是不可判定的。(8)可判定(9)可判定(10)可判定(11)可判定(12)可判定(13)不可判定(14)证明是不可判定的。证明：假设是可判定的。设H是的判定器。令M是一个TM，是一个串。在输入上，如果M接受，则H就停机且接受；如果M不接受ω，则H也会停机，但拒绝。即H是一个TM使得：H()=现在来构造一个新的图灵机D，它以H作为子程序。当M被输入它自己的描述时，TMD就调用H，以了解M作什么。一旦得到这个消息，D就反着做，即：如果M接受，它就拒绝；如果M不接受，它就接受。下面是D

7、的描述：D=“对于输入,其中M是一个TM：1）在输入>上运行H。2）输入H输出的相反结论，即，如果H接受，就拒绝；如果H拒绝，就接受。”得出：D()=当以D的描述作为输入来运行D自身时，得到：D()=不论D做什么，它都被迫相反地做，这显然是一个矛盾。6、证明一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。证明：(i)必要性：如果A是可判定的，任何可判定语言都是图灵可识别的，且任何可判定语言的补也是可判定的，所以A和它的补都是图灵可识别的(ii)充分性：令是A的识别器，是的识别器。下列图灵机M是A